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];
}