DP ： 132. Palindrome Partitioning II

痛定思痛。 2022-05-08 09:52 154阅读 0赞

#### 132. 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.

Example:

Input: “aab”  
Output: 1  
Explanation: The palindrome partitioning \[“aa”,“b”\] could be produced using 1 cut.

class Solution {
        
    public:
    
        int helper(vector<vector<int>>& dp,string& s,int x,int y) {
        
            int n = s.size();
            if(dp[x][y]>=0) 
                return dp[x][y];
    
            if(x==y)
                dp[x][y] = 1;
            else if(y-x==1)
                dp[x][y] = s[x]==s[y];
            else if(s[x]==s[y])
                dp[x][y] = dp[x+1][y-1] >= 0 ? dp[x+1][y-1] : helper(dp,s,x+1,y-1);
            else dp[x][y] = 0;
    
            return dp[x][y];
        }
    
    
        int helper2(vector<vector<int>>& dp,vector<int>& dp2,int x) {
        
            int n = dp2.size();
            
            if(dp[x][n-1]) {
        
                dp2[x] = 0;
                return 0;
            }
            
            for(int j=x;j<n-1;++j) {
        
            	if(dp[x][j])
            		dp2[x] = min(dp2[x], (dp2[j+1] != INT_MAX ? dp2[j+1] : helper2(dp,dp2,j+1)) + 1);
            }
            
            return dp2[x];
        }
    
        int minCut(string s) {
        
            int n = s.size();
            if(n<=1) return 0;
            if(n==2) return !(s[0]==s[1]);
            
            vector<vector<int>> dp(n,vector<int>(n,-1));
    
            for(int i=0;i<n;++i) {
        
                for(int j=i;j<n;++j) {
        
                    helper(dp,s,i,j);
                }
            }
            
            vector<int> dp2(n,INT_MAX);
            return helper2(dp,dp2,0);
    
        }
    };