leetCode

题意：给定一个字符串，要把他这个字符串分成若干个回文子串。问数目最小是多少。

题解：动态规划。用ans[j]表示以j结尾的回文子串数量，则如果s(0,j)是回文串，则ans[j]=1，否则 ans[j]=min(ans[i-1])+1，并且s(i,j)是回文串。

代码：

int minCut(string s) { int i,j,k,l=s.length(),left,right; vector<int> ans; vector<vector<bool> > is(l, vector<bool>(l, false)); for(i=0; i<l; i++) { is[i][i]=true; ans.push_back(i+1); } for(i=2; i<=l; i++) { for(j=0; j<l-i+1; j++) { left=j; right=j+i-1; if((i==2||is[left+1][right-1]==true)&&s[left]==s[right]) is[left][right]=true; } } for(i=0;i<l;i++) { for(j=0;j<=i;j++) { if(is[j][i]) { if(j==0) ans[i]=1; else ans[i]=min(ans[i],ans[j-1]+1); } } } return ans[l-1]-1; }