class Solution {
public:
    int dp[1001][1001];

    int lcs(string s, string t, int n, int m)
    {
        if( (n==0) || (m==0) ) return 0;
        if(dp[n][m] != -1)  return dp[n][m];

        if(s[n-1] == t[m-1])
        {
            int ans = 1+lcs(s, t, n-1, m-1);
            dp[n][m] = ans;
            return dp[n][m];
        }
            
        else
        {
            int ans1 = lcs(s, t, n-1, m);
            int ans2 = lcs(s, t, n, m-1);
            dp[n][m] = max(ans1, ans2);
            return dp[n][m];
        }
    }

    
    int longestCommonSubsequence(string s, string t) {
        int n = s.size(), m = t.size();
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            dp[i][j] = -1;
        lcs(s, t, n, m);
    return dp[n][m];
    }
};