Partitioning by Palindromes - UVa 11584

例题9-7 划分成回文串（Partitioning by Palindromes, UVa 11584）

#dp #线性dp #字符串回文 #T3

输入一个由小写字母组成的字符串，要求把它划分成尽量少的回文串。输出最少的个数。
如aaadbccb最少可以划分为3个：aaa,d,bccb

输入：
第一行输入一个n表示数据组数
接下来n行每行输入一个字符串s(1<=s<=1000)

输出：
输出一个数表示最少的个数

input

3
aaadbccb
ffgcc
juzi

output

3
3
4`

思路

状态表示： f[i] 是 1~i 中回文串个数
状态计算： f[i] = min(f[i], f[j] + 1 ) if i~j 是一个回文串

所以先用n^2把这个串中的所有回文字串标识出来。

bool is_palindrome(int i, int j)
{
	if(i >= j) return true;
	if(s[i] != s[j]) return false;

	if(st[i][j] == kase) return p[i][j];
	st[i][j] = kase;
	p[i][j] = is_palindrome(i+1,j-1);
	return p[i][j];
}

这里的 st 只是为了确保p数组中的值是当前数据组的情况, 正常的判断回文数也可以给st去掉然后每组数据重置一下p数组就行。建议记下来以后判断回文串除了双指针就用递归整。

代码

const int N = 1e3 + 10;
char s[N];
bool p[N][N];
int st[N][N];
int f[N];
int n, kase = 1;

int ispalind(int i, int j)
{
    if (i >= j)
        return 1;
    if (s[i] != s[j])
        return 0;

    if (st[i][j] == kase)
        return p[i][j];
    st[i][j] = kase;
    p[i][j] = ispalind(i + 1, j - 1);
    return p[i][j];
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        f[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            f[i] = i + 1;
            for (int j = 0; j < i; j++)
                if (ispalind(j + 1, i))
                    f[i] = min(f[i], f[j] + 1);
        }
        cout << f[n] << endl;
        kase++;
    }
    return 0;
}