题意：

看白书

要点：

回文串处理，传递边界，从左边界枚举到中心，如果出现不相等的说明不是回文串，否则为回文串。

DP：以d[i]存储第i个字符前划分成的回文串的个数的最小值，如果第i个字符和前面第j个字符之间的为回文串，那么d[i]=d[j-1]+1。因此状态转移方程就是d[i]=max(d[i],d[j-1]+1)。边界值d[0]=0，因为取最小值，一开始d数组赋值为一个比较大的数。

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int maxn = 1005;char str[maxn];int d[maxn];bool check(int left, int right)//回文串判断{	int mid = (left + right) / 2;	for (int i = left; i <= mid; i++)		if (str[i] != str[right + left - i])			return false;	return true;}int main(){	int t,i,j;	scanf("%d", &t);	while (t--)	{		scanf("%s", str+1);		int n = strlen(str+1);		for (i = 1; i <= n; i++)			d[i] = 3000;		d[0] = 0;		for (i = 1; i <= n; i++)			for (j = 1; j <= i; j++)				if (check(j, i))					d[i] = min(d[i], d[j - 1] + 1);//出现的最优解是与前面组成的回文串出现位置d+1的最小值		printf("%d\n", d[n]);	}	return 0;}