Optimize this solution


#1

int static dp[502][502];
bool ispalindrome(string s,int l,int m)
{
if(l==m) return true;
if(l>m) return true;
while(l<m)
{
if(s[l]!=s[m])
{
return false;
}
l++;
m–;
}
return true;
}
int solve (string s,int i, int j)
{
if(i>=j) return 0;
if(ispalindrome(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-1;k++)
{
int temp=solve(s,i,k)+solve(s,k+1,j)+1;
if(temp<mn)
{
mn=temp;
}
}
return dp[i][j]=mn;
}
int Solution::minCut(string A) {
memset(dp,-1,sizeof(dp));
int n=A.size();
if (n==1)
{
return 0;
}
return solve(A,0,n-1);

}


#2

for checking palindrome, think about rolling hash. That will bring down the complexity to O(n^2).


#3
for(int k=i;k<=j-1;k++)
{
        int l = -1  , r = -1;
        if(dp[i][k] != -1)
        {
            l = dp[i][k];
        }
        if(dp[i][k] != -1)
        {
            r = dp[k+1][j];
        }
        int temp=(l == -1 ? solve(s,i,k) : l )+ (r == -1 ? solve(s,k+1,j) : r)+1;
        if(temp<mn){
            mn=temp;
        }
    }

replace your for loop with this