C++ dp solution for this problem


#1

int Solution::solve(string A, string B) {
int m=A.size();
int n=B.size();
vector<vector > dp(m+1, vector(n+1,0));
for(int i=1; i<=m; 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][j-1],dp[i-1][j]);
}
}
return dp[m][n];
}


#2

int lcs(string s1,string s2,int m,int n,vector<vector>&dp){
if(m==s1.length()||n==s2.length())
return 0;
if(dp[m+1][n+1]>-1)
return dp[m+1][n+1];
if(s1[m]==s2[n]){
int ans = 1+lcs(s1,s2,m+1,n+1,dp);
dp[m+1][n+1]=ans;
return ans;
}
else{
int ans=max(lcs(s1,s2,m,n+1,dp),lcs(s1,s2,m+1,n,dp));
dp[m+1][n+1]=ans;
return ans;
}
}
int Solution::solve(string A, string B) {
vector<vector>dp(A.length()+1,vector(B.length()+1));
for(int i=0;i<A.length()+1;i++){
for(int j=0;j<B.length()+1;j++)
dp[i][j]=-1;
}
return lcs(A,B,0,0,dp);
}