string A;
bool pallin(int i,int j)
{
while(i<=j)
{
if(A[i]!=A[j])
return false;
++i;
--j;
}
return true;
}
int lps(int i,int j,vector<vector> &dp)
{
if(dp[i][j]!=-1)
return dp[i][j];
if(i>=A.length() || j>=A.length() || i>j)
return dp[i][j]=0;
if(i==j)
{
return dp[i][j]=0;
}
int ans=INT_MAX;
for(int ii=i;ii<=j;++i)
{
if(pallin(i,ii))
{
ans=min(ans,1+lps(ii+1,j,dp));
}
}
return dp[i][j]=ans;
}
int Solution::minCut(string Ap)
{
A=Ap;
vector<vector> dp(A.length(),vector(A.length(),-1));
int p=lps(0,A.length()-1,dp);
return p;
}