My Dp solution using c++

  • 1
    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;
        for(int j=0; j<n; j++){
            for(int i=j; i>=0; i--){
                    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.