Leetcode---Palindrome Partitioning II

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",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Have you been asked this question in an interview?

得出最短的回文划分次数。
第一思路是动态规划，找最优子结构，假设f(i, j)是从i到j的最短回文划分次数，比较容易得出：

f(i,j)=0，s[i, j]是回文
f(i,j)=min{f(i,k)+f(k+1,j)}+1, 其中i<=ks[i, j]不是回文

为了便于求f(i,k)，需要求出字符串的所有可能子字符串组合是不是回文，需要一个dp[s.length()][s.length()]；
然后，为了保存f(i,k)和f(k+1,j)两次递归的成果，不重复计算，需要另一个dp2[s.length()][s.length()]；
写code如下，最后TLS了

vector<vector<bool>> dp;
vector<vector<int>> dp2;
void createdp(string& s){
    int n=dp.size();
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            dp[i][j]=true;
        }
    }
    for(int i=n-2;i>=0;i--){
        for(int j=i+1;j<n;j++){
            dp[i][j]=dp[i+1][j-1]&&(s[i]==s[j]);
        }
    }
}
int f(string& s, int i,int j){
    if(dp[i][j]){
        dp2[i][j]=0;
        return 0;
    }
    else if(dp2[i][j]!=-1){
        return dp2[i][j];
    }
    else{
        int min=0xFFFFFF;
        for(int k=i;k<j;k++){
            int cut=f(s,i,k)+f(s,k+1,j)+1;
            if(min>cut)
                min=cut;
        }
        dp2[i][j]=min;
        return min;
    }
}
int minCut(string s){
    dp.resize(s.length(),vector<bool>(s.length(),false));
    dp2.resize(s.length() ,vector<int>(s.length(),-1));
    createdp(s);
    /*for(vector<vector<bool>>::iterator it0 = dp.begin(); it0 != dp.end(); ++it0){
        for(vector<bool>::iterator it1 = (*it0).begin(); it1 != (*it0).end(); ++it1) {
            cout<<*it1<<" ";
        }
        cout<<endl;
    }*/
    //cout<<dp[4][7]<<endl;
    return f(s,0,s.length()-1);
}

思考了一下，我们计算了f(i,j)=min{f(i,k)+f(k+1,j)}+1，但其实只需要知道f(i,n-1)=min{f(i,k)+f(k+1,n-1)}+1 即可，所以导致了大量时间浪费。
当s[i, k]是回文时，f(i,k)=0，公式变为f(i,n-1)=min{f(k+1,n-1)}+1， k取值[i, n-1)
当s[i, k]不是回文时，肯定不是最小划分，所以直接abort这种情况
因为n-1是常量，所以公式可演化为：
f'(i)=min{f'(k+1)}+1， k取值[i, n-1)，s[i, k]是回文
code如下：

vector<vector<bool>> dp;
vector<int> dp2;
void createdp(string& s){
    int n=dp.size();
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            dp[i][j]=true;
        }
    }
    for(int i=n-2;i>=0;i--){
        for(int j=i+1;j<n;j++){
            dp[i][j]=dp[i+1][j-1]&&(s[i]==s[j]);
        }
    }
}
void createdp2(){
    int n=dp2.size();
    for(int i=n-1;i>=0;i--){
        if(dp[i][n-1])
            dp2[i]=0;
        else{
            int min=0xFFFFFF;
            for(int k=i;k<n-1;k++){
                if(dp[i][k]){
                    int cut=dp2[k+1]+1;
                    if(cut<min)
                        min=cut;
                }
            }
            dp2[i]=min;
        }
    }
}
int minCut(string s){
    dp.resize(s.length(),vector<bool>(s.length(),false));
    dp2.resize(s.length(),0);
    createdp(s);
    createdp2();
    return dp2[0];
}