1143. 最长公共子序列

难度：🟡 Medium | 标签：动归 | 状态：⬜ LeetCode 链接

思路

dp[i][j] = text1[0..i) 和 text2[0..j) 的 LCS 长度。

• text1[i-1] == text2[j-1] → dp[i-1][j-1] + 1
• 否则 → max(dp[i-1][j], dp[i][j-1])

代码

class Solution {
public:
    int longestCommonSubsequence(string a, string b) {
        int m = a.size(), n = b.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j) {
                if (a[i - 1] == b[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[m][n];
    }
};

复杂度

• 时间 O(m · n)，空间 O(m · n)（可滚动到 O(n)）

易错 / 回顾

• 「子序列」≠「子串」（不连续 vs 连续）
• 索引下移 1 对齐 dp 表，base 行列全 0
• 最长公共子串：不相等时 dp 重置为 0，不取邻最大