【leetcode dp】132. Palindrome Partitioning II

https://leetcode.com/problems/palindrome-partitioning-ii/description/

【题意】

给定一个字符串，求最少切割多少下，使得切割后的每个子串都是回文串

【思路】

求一个字符串的所有子串是否是回文串，O(n^2) dp从后往前推

 1     vector<vector<bool> > p(len,vector<bool>(len));
 2     for(int i=0;i<len-1;i++){
 3         for(int j=0;j<len-1;j++){
 4             if(j!=i) p[i][j]=false;
 5             else p[i][j]=true;
 6         }
 7     }
 8     for(int i=len-1;i--;i>=0){
 9         for(int j=i+1;j<len;j++){
10             if(s[i]==s[j]&&((j==i+1)||p[i+1][j-1])){
11                 p[i][j]=true;
12             }else{
13                 p[i][j]=false;
14             }
15         }
16     }

View Code

然后再dp求最小切割

【AC】

class Solution {
public:
    const int inf=0x3f3f3f3f;
    
    int minCut(string s){
        int len=s.length();
        if(len==0 || len==1) return 0;
        vector<vector<bool> > p(len,vector<bool>(len));
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                if(j!=i) p[i][j]=false;
                else p[i][j]=true;
            }
        }
        for(int i=len-1;i--;i>=0){
            for(int j=i+1;j<len;j++){
                if(s[i]==s[j]&&((j==i+1)||p[i+1][j-1])){
                    p[i][j]=true;
                }else{
                    p[i][j]=false;
                }
            }
        }
        vector<int> dp(len);
        for(int i=0;i<len;i++) dp[i]=inf;
        for(int i=0;i<len;i++){
            if(p[0][i]) dp[i]=0;
        }
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                if(p[i+1][j]){
                    dp[j]=min(dp[j],dp[i]+1);
                }
            }
        }
        return dp[len-1];
    }
};