leetcode

0 // Top-down DP

1 class Solution {

2 int search(const string &text1, const string &text2, int si, int sj, vector<vector<int>> &dp) {

3 if (si == text1.size() || sj == text2.size()) return 0;

4 if (dp[si][sj] != -1) return dp[si][sj];

5 int len = 0, i = si, j = sj;

6 while (i < text1.size() && j < text2.size() && text1[i] == text2[j])

7 i++, j++, len++;

8

9 if (i == text1.size() || j == text2.size()) return dp[si][sj] = len;

10 return dp[si][sj] = len + max(search(text1, text2, i + 1, j, dp), search(text1, text2, i, j + 1, dp));

11 }

12

13 public:

14 int longestCommonSubsequence(string text1, string text2) {

15 vector<vector<int>> dp(text1.size(), vector<int>(text2.size(), -1));

16 return search(text1, text2, 0, 0, dp);

17 }

18 };

19

20 // Bottom-up DP

21 class Solution {

22 public:

23 int longestCommonSubsequence(string text1, string text2) {

24 vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));

25 for (int i = 0; i < text1.size(); i++)

26 for (int j = 0; j < text2.size(); j++)

27 if (text1[i] == text2[j])

28 dp[i + 1][j + 1] = 1 + dp[i][j];

29 else

30 dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);

31

32 return dp.back().back();

33 }

34 };