My Dp solution using c++


  • 1
    S
    int minCut(string s) {
        int n=s.size();
        bool p[n][n]; //p[i][j]=1 if s[i..j] is palindromic
        int cut[n+1]; //cut[i] is no. of cuts needed for the first i chars
        for(int i=0; i<=n; i++) cut[i]=n;
        cut[0]=-1;
        for(int j=0; j<n; j++){
            for(int i=j; i>=0; i--){
                if(s[i]==s[j]){
                    if(j-i<=1) p[i][j]=true;
                    else p[i][j]=p[i+1][j-1];
                    if(p[i][j]) cut[j+1]=min(cut[j+1], cut[i]+1);
                }
                else p[i][j]=false;
            }
        }
        return cut[n];
        
       
    }

Log in to reply
 

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