Understandable solution in c++


#1

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);

}


#2

I did the same thing but my solution is failing for “dVGAaVO25EmT6W3zSTEA0k12i64Kkmmli09Kb4fArlF4Gc2PknrlkevhROxUg”
could you please help?


#3

Kindly share any link containing your solution. That way I may be able to figure out the mistake.