1143 最长公共子序列
动态规划
与上一题一样:
text1[i - 1] == text2[j - 1]仍然是dp[i][j] = dp[i - 1][j - 1] + 1;
和上一题不同之处在于:
由于上一题是公共子数组,子数组特性在于连续,因此text1[i - 1] != text2[j - 1]说明dp[i][j] == 0
而本题是公共子序列,可以不连续,text1[i - 1] != text2[j - 1]时dp[i][j] != 0,需要我们额外计算
dp[i][j]的长度是dp[i - 1][j]和dp[i][j - 1]中的最大值
二维做法
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size();
int m = text2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0))
; for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(text1[i - 1] == text2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[n][m];
}
};
一维优化
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size();
int m = text2.size();
vector<int> dp(m + 1, 0)
; for(int i = 1; i <= n; i++){
int pre = dp[0];
for(int j = 1; j <= m; j++){
// 这里的dp[j]为dp[i - 1][j]
int cur = dp[j];
if(text1[i - 1] == text2[j - 1])
dp[j] = pre + 1;
else
// dp[j]为dp[i - 1][j]
// dp[j - 1]为dp[i][j - 1]
dp[j] = max(dp[j], dp[j - 1]);
// 这里的pre为dp[i - 1][j]
// j++后,pre为dp[i - 1][j - 1]
pre = cur;
}
}
return dp[m];
}
};
- 时间复杂度:\(O(n × m)\),n 为A长度,m为B长度
- 空间复杂度:\(O(m)\)