C++ DP


  • 0
    G
    class Solution {
    public:
        int minCut(string s) {
            vector<vector<bool> > isPal(s.size(),vector<bool>(s.size(),false));
            vector<int> dp(s.size() + 1,INT_MAX);
                                     
            for(int i = 0; i < s.size(); ++i){
                for(int j = i; j >= 0; j--){
                    if(s[i] == s[j]){
                        if(i == j || j + 1 == i){
                            isPal[j][i] = true;
                        }
                        else{
                            isPal[j][i] = isPal[j + 1][i - 1];
                        }
                    }
                }
            }
            
            dp[0] = 0;
            
            for(int i = 1; i <= s.size(); ++i){
                for(int j = i; j >= 1; j--){
                    if(isPal[j - 1][i - 1] && dp[j - 1] != INT_MAX){                    
                        dp[i] = min(dp[i],dp[j - 1] + (j - 1 == 0 ? 0 : 1));
                    } 
                }
            }
    
            return dp[s.size()];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.