Lang: C++; Complexity[Time,Space]: [O(n^3), O(n^2)]


#1

Approach: DP; Type: Bottom up, Iterative

int Solution::minCut(string A) 
{
    int n=A.size();
    vector<vector<int>> dp(n, vector<int>(n,0));

    /*  Initialisation   */
    for(int i=0; i < n-1; i++)
        dp[i][i+1] = ((A[i]==A[i+1]) ? 0 : 1);
        
    for(int diff=2; diff<n; diff++)
    {
        for(int i=0; i+diff<n; i++)
        {
            int j = i+diff;

            /*  If Palindromic substring   */
            if(A[i]==A[j] && dp[i+1][j-1]==0)
                dp[i][j] = 0;
            else
            {
                int mn=INT_MAX;
                for(int k=i; k<j; k++)
                    mn = min(mn, dp[i][k]+dp[k+1][j]);
                dp[i][j] = 1+mn;
            }
        }
    }
    return dp[0][n-1];
}