LeetCode 1143 Longest Common Subsequence
概述
https://leetcode.com/problems/longest-common-subsequence/
动态规划法
极值问题，无脑动态规划。
class Solution {
public:
vector<vector<int>> dp;
string text1;
string text2;
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.size(), vector<int>(text2.size(), -1));
this->dp = dp;
this->text1 = text1;
this->text2 = text2;
return helper(0, 0);
}
int helper(int i, int j) {
if (i >= text1.size() || j >= text2.size()) return 0;
if (dp[i][j] != -1) return dp[i][j];
if (text1[i] == text2[j]) {
dp[i][j] = 1 + helper(i+1, j+1);
} else {
dp[i][j] = max(helper(i+1, j), helper(i, j+1));
}
return dp[i][j];
}
};