this method is Memoization in dp
class Solution {
public:
int dp[1001][1001];
int lcs(string &text1,string &text2,int m,int n)
{
if(dp[m][n]!=-1) return dp[m][n];
if(n == 0 || m == 0) // Base case
return 0;
if(text1[m-1]==text2[n-1])
return dp[m][n]=1+lcs(text1,text2,m-1,n-1);
else
return dp[m][n]=max(lcs(text1,text2,m-1,n),lcs(text1,text2,m,n-1));
}
int longestCommonSubsequence(string text1, string text2) {
int m=text1.size();
int n=text2.size();
int result=0;
memset(dp,-1,sizeof(dp));
result=lcs(text1,text2,m,n);
return result;
}
};
##
Top comments (0)