Easy to understand c++ dp solution


#1

int Solution::solve(string a) {
int n=a.size();
int i,j,ans=1;
int dp[n+3][n+3]={{0}};

for(i=1;i<=n;i++)
{
    for(j=i;j>=1;j--)
    {
        if(a[i-1]==a[j-1])
        {
            if(i==j+1)
            dp[j][i]=2;
            else if(i==j)
            dp[j][i]=1;
            else
            dp[j][i]=2+dp[j+1][i-1];
        }
        else
        {
            dp[j][i]=max(dp[j][i-1],dp[j+1][i]);
        }
        
        ans=max(ans,dp[j][i]);
    }
    
}
return dp[1][n];

}