题目描述
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s ="aab",
Return1since the palindrome partitioning["aa","b"]could be produced using 1 cut.
解题思路
本题所使用的方法是动态规划。用一个数组，mc[]来保存从第0个字符到当前字符的最小切割数，比如，mc[j]表示0到j之间的字符串的最小切割数。
注意以下几点：
- 当s[i..j]是回文串时，mc[j]=min(mc[i-1]+1,mc[j])。mc[i-1]+1，很好理解，就是前一个回文串的最小切割加上1个切割。可为什么要与mc[j]比较取最小值呢？因为，mc[j]中保存着到j这个字符的不同切割方法的最小切割数，也就是无论怎样，mc[j]中的值都是表示0到j之间的字符串的最小切割数（目前为止的），所以要和它比较，如果比它还小，就把mc[j]值更新成更小的。
- 当s[i...j]不是回文串时，那么mc[j]=min(mc[j-1]+1,mc[j])。mc[j-1]表示到上一个字符的最小切割，到下一个字符不是回文，就把下一个字符单独拿出作为回文，把到上一个字符最小切割数加上1，作为到这个字符的最小切割数。mc[j]的解释和上一点相同。
- 最后一个mc[s.size()-1]是整个串的最小切割数。
解题代码
class Solution {
bool isPal(string s,int left,int right){
for(int i=left,j=right;i<j;i++,--j){
//cout<<*i<<" "<<*j<<endl;
if(s[i]!=s[j]) return false;
}
return true;
}
public:
int minCut(string s) {
vector<int> mc(s.size(),0);
for(int i=0;i<s.size();++i){
//mc[i]=mc[i-1]+1;
for(int j=i;j<s.size();++j){
//mc[j]=m[i]+1;
if(i>0){
if(isPal(s,i,j)){
mc[j]=min(mc[j],mc[i-1]+1);
}else{
mc[j]=min(mc[j],mc[j-1]+1);
}
}else{
if(isPal(s,i,j)){
mc[j]=0;
}else{
mc[j]=mc[j-1]+1;
}
}
}
}
return mc[s.size()-1];
}
};
