Simple c++ dp solution . another version of longest common subsequence


#1

int Solution::solve(string A) {
string B = A;
reverse(B.begin(),B.end());
int n = A.size();
vector<vector > dp(n+1 , vector (n+1,0));
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= n ; j++)
{
if(A[i-1] == B[j-1])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
}
}
return dp[n][n];
}