Uva 11584划分回文串（动规）

dp[i]表示从从头到i划分最少的回文串数。 dp[i]=dp[j-1]+1 {i<=j,i-j是回文}

#include <iostream>#include <cstring>#include <cstdio>using namespace std;char s[1005];int dp[1005];int OK(int i,int j){   for(int k=0;k<=(j-i)/2;k++)if(s[i+k]!=s[j-k]) return 0;return 1;}int main(int argc, char *argv[]){int n,i,j;cin>>n;while(n--){scanf("%s",s);dp[0]=0;for(i=1;i<=strlen(s);i++)for(dp[i]=1005,j=1;j<=i;j++){if(OK(j-1,i-1)){dp[i]=min(dp[i],dp[j-1]+1);}}printf("%d\n",dp[strlen(s)]);}return 0;}