1143.cpp (1310B)
1 // Top-down DP 2 class Solution { 3 int search(const string &text1, const string &text2, int si, int sj, vector<vector<int>> &dp) { 4 if (si == text1.size() || sj == text2.size()) return 0; 5 if (dp[si][sj] != -1) return dp[si][sj]; 6 int len = 0, i = si, j = sj; 7 while (i < text1.size() && j < text2.size() && text1[i] == text2[j]) 8 i++, j++, len++; 9 10 if (i == text1.size() || j == text2.size()) return dp[si][sj] = len; 11 return dp[si][sj] = len + max(search(text1, text2, i + 1, j, dp), search(text1, text2, i, j + 1, dp)); 12 } 13 14 public: 15 int longestCommonSubsequence(string text1, string text2) { 16 vector<vector<int>> dp(text1.size(), vector<int>(text2.size(), -1)); 17 return search(text1, text2, 0, 0, dp); 18 } 19 }; 20 21 // Bottom-up DP 22 class Solution { 23 public: 24 int longestCommonSubsequence(string text1, string text2) { 25 vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0)); 26 for (int i = 0; i < text1.size(); i++) 27 for (int j = 0; j < text2.size(); j++) 28 if (text1[i] == text2[j]) 29 dp[i + 1][j + 1] = 1 + dp[i][j]; 30 else 31 dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]); 32 33 return dp.back().back(); 34 } 35 };