题目描述

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];
    }
};