DP ： 132. Palindrome Partitioning II

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);

    }
};