题目链接

解题报告：

dp[i] 表示 前i个字符最少划分的个数

dp[i]=min(dp[j]+1) j+1~i是回文串

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
#define Inf 0x3f3f3f3f
char a[1010];
int vis[1010][1010], d[1010];
int check( int l, int r ){if ( l > r ) return 1;if ( vis[l][r] != -1 ) return vis[l][r];if ( a[l] != a[r] ) {vis[l][r] = 0;return 0;}if ( check( l+1, r-1 ) == 1 ){vis[l][r] = 1;return 1;}}
bool check2(int l,int r)  
{  for(int i=l,j=r;i<=r;i++,j--)  if(a[i]!=a[j])return false;  return true;      
}
int main(){int T;scanf( "%d", &T);for ( int Case = 1; Case <= T; Case++){memset( vis, -1, sizeof(vis));scanf( "%s", a+1);int l = strlen(a+1);for ( int i = 1; i <= l; i++) d[i] = Inf, vis[i][i] = 1;for ( int i = 1; i <= l; i++)for ( int j = i; j <= i; j++){vis[i][j] = check( i, j );}d[0] = 0;for ( int i = 1; i <= l; i++)for ( int j = 1; j <= i ; j++)if ( check(  j, i) ) d[i] = min( d[i], d[j-1]+1 );printf( "%d\n", d[l]);}return 0;
}