本题是一类经典的二维动态规划问题。设 dp[i][j] 为 text1[0…i] 与 text2[0…j] 的最长公共子序列，那么本问题的状态转移方程为：
if(text1[i] == text2[j]) {
dp[i][j] = 1 + dp[i-1][j-1]; //末尾字符相等时
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]); //末尾字符不相等时
}
推算出状态转移方程后，写出代码求解就十分容易了。
方法一：递归（超时）
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
return ans(text1, text2, text1.length() - 1, text2.length() - 1);
}
int ans(string &text1, string &text2, int i, int j) { //i、j分别表示对text1、text2从下标0到i、j闭区间范围的字串进行求解
if(i < 0 || j < 0)
return 0;
else {
if(text1[i] == text2[j])
return ans(text1, text2, i - 1, j - 1) + 1;
else
return max(ans(text1, text2, i - 1, j), ans(text1, text2, i, j - 1));
}
}
};
方法二：记忆化搜索
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector< vector<int> > flag(text1.length(), vector<int>(text2.length(), -1)); //将递归的结果储存到该数组中
return ans(text1, text2, text1.length() - 1, text2.length() - 1, flag);
}
int ans(string &text1, string &text2, int i, int j, vector< vector<int> > &flag) {
if(i < 0 || j < 0)
return 0;
else {
if(flag[i][j] != -1) //若该结果已经先前被计算过，直接返回flag数组中对应索引的内容
return flag[i][j];
if(text1[i] == text2[j])
flag[i][j] = ans(text1, text2, i - 1, j - 1, flag) + 1;
else
flag[i][j] = max(ans(text1, text2, i - 1, j, flag), ans(text1, text2, i, j - 1, flag));
return flag[i][j];
}
}
};
方法三：动态规划
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
if(text1.length() == 0 || text2.length() == 0)
return 0;
int n = text1.length();
int m = text2.length();
vector< vector<int> > dp(n, vector<int>(m, -1));
dp[0][0] = (text1[0] == text2[0] ? 1 : 0); //初始化dp[0][0]
for(int i = 1; i < n; i ++) { //初始化dp[1...n-1][0]
dp[i][0] = (text1[i] == text2[0] ? 1 : dp[i - 1][0]);
}
for(int j = 1; j < m; j ++) { //初始化dp[0][1...m-1]
dp[0][j] = (text1[0] == text2[j] ? 1 : dp[0][j - 1]);
}
for(int i = 1; i < n; i ++) {
for(int j = 1; j < m; j ++) {
if(text1[i] == text2[j])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[n - 1][m - 1];
}
};