给定一个字符串，问：最少能分割成几个子字符串，并且每个字符串都是回文串。
设：dp [ i ] 是前 i 个字符能分割的最少个数。
动态转移方程： dp [ i ] = max ( dp [ i ] , dp[ j ] +1) ;
其中 j 是 0 ~ i 之间的数 ，执行转移方程的条件是 j~i 的字符串是回文串
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1005
#define INF 1000000000
using namespace std;
//判断l~r字符串是否是回文串
bool is_p(int l,int r,char *s){while(l<=r){if(s[l]!=s[r]){return false;}l++;r--;}return true;
}char s[N];
int dp[N]; //前n个字符的回文最小个数
int n;
int main(){scanf("%d",&n);while(n--){memset(dp,0,sizeof(dp));scanf("%s",s);int len = strlen(s);for(int i=0 ;i<len ;i++){dp[i+1] = INF;for(int j=0 ;j<=i ;j++){if(is_p(j,i,s)){dp[i+1] = min(dp[i+1],dp[j]+1);}}}printf("%d\n",dp[len]);}
}