跳转至

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)\)