Easy c++ Soln using top down approach:


#1

int dp[1007][1007];

int find(string a,int i,int j){
if(i>j){
return 0;
}
if(i==j){
return 1;
}
if(dp[i][j]!=-1){
return dp[i][j];
}
if(a[i]==a[j]){
return dp[i][j] = 2+find(a,i+1,j-1);
}
else{
return dp[i][j] = max(find(a,i+1,j),find(a,i,j-1));
}
}

int Solution::solve(string A) {
memset(dp,-1,sizeof(dp));
int soln = find(A,0,A.length()-1);
return soln;
}