1. class Solution {
2. public:
3.     int memo[1001][1001];
4.  
5.     // Backward recursion (m, n) -> (0, 0)
6.     int lcs1 (string s1, string s2, int m, int n) {
7.         if (m == -1 || n == -1)
8.             return 0;
9.  
10.         if (memo[m][n] != -1)
11.             return memo[m][n];
12.  
13.         int ans = 0;
14.  
15.         if (s1[m] == s2[n])
16.             ans = 1 + lcs1(s1, s2, m-1, n-1);
17.         else
18.             ans = max(lcs1(s1, s2, m-1, n), lcs1(s1, s2, m, n-1));
19.  
20.         memo[m][n] = ans;
21.         return ans;
22.     }
23.  
24.     // Forward recursion (0, 0) -> (m, n)
25.     int lcs2 (string s1, string s2, int i, int j, int m, int n) {
26.         if (i == m || j == n)
27.             return 0;
28.  
29.         if (memo[i][j] != -1)
30.             return memo[i][j];
31.  
32.         int a, b, c; a = b = c = 0;
33.  
34.         int ans = 0;
35.         if (s1[i] == s2[j]) {
36.             if (memo[i+1][j+1] != -1)
37.                 a = memo[i+1][j+1];
38.             else {
39.                 a = lcs2(s1, s2, i+1, j+1, m, n);
40.                 memo[i+1][j+1] = a;
41.             }
42.  
43.             ans = 1 + a;
44.         }
45.         else {
46.             if (memo[i][j+1] != -1)
47.                 b = memo[i][j+1];
48.             else {
49.                 b = lcs2(s1, s2, i, j+1, m, n);
50.                 memo[i][j+1] = b;
51.             }
52.  
53.             if (memo[i+1][j] != -1)
54.                 c = memo[i+1][j];
55.             else {
56.                 c = lcs2(s1, s2, i+1, j, m, n);
57.                 memo[i+1][j] = c;
58.             }
59.  
60.             ans = max(b, c);
61.         }
62.  
63.         memo[i][j] = ans;
64.         return ans;
65.  
66.     }
67.  
68.     int lcs(string s1, string s2) {
69.         int m = s1.size();
70.         int n = s2.size();
71.  
72.         int dp[m+1][n+1];
73.         for (int i = 0; i <= m; i++)
74.             for (int j = 0; j <= n; j++)
75.                 dp[i][j] = 0;
76.  
77.         for (int i = 1; i <= m; i++) {
78.             for (int j = 1; j <= n; j++) {
79.                 if (s1[i-1] == s2[j-1])
80.                     dp[i][j] = 1 + dp[i-1][j-1];
81.                 else
82.                     dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
83.             }
84.         }
85.  
86.         return dp[m][n];
87.     }
88.  
89.     int longestCommonSubsequence(string text1, string text2) {
90.  
91.         // for (int i = 0; i <= text1.size(); i++)
92.         //     for (int j = 0; j <= text2.size(); j++)
93.         //         memo[i][j] = -1;
94.  
95.         // return lcs1(text1, text2, text1.size()-1, text2.size()-1);
96.  
97.         // return lcs2(text1, text2, 0, 0, text1.size(), text2.size());
98.  
99.         return lcs(text1, text2);
100.     }
101. };