bool ispalin(string s, int i,int j)
{
while(i<=j)
{
if(s[i]!=s[j])
{
return false;
break;
}
i++;
j–;
}
return true;
}
int dp[1002][1002];
void init()
{ for(int l=0;l<1002;l++)
{
for(int m=0;m<1002;m++)
{
dp[l][m]=-1;
}
}
}
int solve(string s,int i,int j)
{
if(i==j)
return 0;
if(ispalin(s,i,j)==true)
return 0;
if(dp[i][j]!=-1)
return dp[i][j];
int mn=INT_MAX;
for(int k=i;k<j;k++)
{ int left,right;
if(dp[i][k]!=-1)
left=dp[i][k];
else
left=solve(s,i,k);
if(dp[k+1][j]!=-1)
right=dp[k+1][j];
else
right=solve(s,k+1,j);
int temp=1+left+right;
mn=min(mn,temp);
}
return dp[i][j]=mn;
}
int Solution::minCut(string A) {
init();
int n=A.size();
int i=0,j=n-1;
return solve(A,0,n-1);
}