LC1143　最长公共子序列¶

中等通过率 67.8%python3核心代码模式多维动态规划样例通过牛客 AC字符串动态规划最长公共子序列

讲解章节：线性 DP

一句话

末尾字符相同就一起吃掉并加一，不同则丢弃其中一串的末位取较优。

解题思路¶

这题考什么¶

LCS（Longest Common Subsequence，最长公共子序列）是双序列 DP 的教科书例题，见线性 DP。子序列允许跳过字符但不能重排，所以两串的比较必须从末尾同步推进，这样才有「谁被消费掉」的清晰分类。

状态定义：f[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度。边界：f[0][j] = f[i][0] = 0，任一方为空时公共子序列只能是空。转移方程，记 a = text1 的第 i 个字符、b = text2 的第 j 个字符：

a == b:  f[i][j] = f[i-1][j-1] + 1
a != b:  f[i][j] = max(f[i-1][j], f[i][j-1])

两条式子的含义：

相同时，把 a 与 b 配成一对接在「两串各去掉末位」的最优解后面。
这里**不需要**再与另外两项取最大——配上这一对永远不吃亏，
因为任何不含这一对的方案都能被改造成含它且不更短的方案。
不同时，a 与 b 至少有一个不可能出现在公共子序列的末尾，
于是分两种情况丢掉其中一个末位，取较优者。

要返回的是长度，不是子序列本身。这一点与牛客 BM65（最长公共子序列(二)）恰好相反——那题要求输出具体的子串，必须额外记录转移方向再回溯还原。只求长度时，回溯所需的信息可以整个丢掉，这正是下面能把二维表滚成一行的前提。

滚动成一行时的陷阱与 LC72 编辑距离完全相同：扫到第 j 列的瞬间， dp[j] 尚未覆盖是「上」，dp[j-1] 已覆盖是「左」，而「左上」在 dp[j-1] 被写入时就丢了，必须用临时变量 diag 在覆盖之前接住，每列算完再把本列的「上」交棒给下一列的「左上」。

数据规模与复杂度¶

1 <= text1.length, text2.length <= 1000，仅小写英文字母。时间 O(m * n) 最坏 1e6 次内层迭代，本机实测 1000 与 1000 对拼约 0.08 秒。空间 O(min(m, n))：把较短的串放到内层维度上，滚动数组最长 1001 项。暴力枚举 text1 的全部子序列再逐个检查是 2 的 1000 次方种，完全不可行。

坑在哪¶

返回长度不是子序列。看到「最长公共子序列」就去拼字符串是最常见的跑偏，本题的判题拿到字符串会直接判类型错。
diag 每行都要重置为 0。本行第一格的左上角是 f[i-1][0]，恒等于 0 （text2 取空前缀时 LCS 为 0），所以进入内层前直接置 0 即可，不必像 LC72 那样先接住 dp[0] 再改写——这里 dp[0] 全程不变。忘记重置会把上一行末尾的值当成本行的左上角，答案偏大。
up 必须在 dp[j] 被覆盖之前取出，否则读到的是刚写进去的新值。
每列结束时 diag = up。漏掉这一步，diag 会一直停在 0，所有匹配都只会算出长度 1。
不匹配时只在「左比上大」的情况下才赋值，else 分支可以省略—— 此时 dp[j] 原样保留着 up，正是「丢掉 text1 的这一位」那个候选。这不是偷懒，而是滚动数组的自然结果：不写就等于取了 up。
相同时是 diag + 1，不能写成 max(dp[j-1], dp[j]) + 1。后者可能把同一个字符重复计入，例如 text1 = "aa"、text2 = "a" 会算出 2，而正确答案是 1。
交换两串是安全的：LCS 对称，交换只为把滚动数组压到 min(m, n)。

样例复核¶

text1 = "abcde"、text2 = "ace"。text1 本就更长，不触发交换，内层维度是长度 3 的 "ace"。

dp 初值 [0, 0, 0, 0]
a='a'：'a'=='a' -> dp[1] = 0 + 1 = 1        -> dp = [0, 1, 1, 1]
a='b'：无匹配，全靠左右传递                 -> dp = [0, 1, 1, 1]
a='c'：'c'=='c' 在第 2 列 -> dp[2] = diag + 1 = 1 + 1 = 2  -> dp = [0, 1, 2, 2]
a='d'：无匹配                               -> dp = [0, 1, 2, 2]
a='e'：'e'=='e' 在第 3 列 -> dp[3] = 2 + 1 = 3             -> dp = [0, 1, 2, 3]

返回 dp[3] = 3，对应公共子序列 "ace"，与期望输出一致。

参考实现¶

solutions/leetcode/LC1143/sol.py
from typing import List, Optional


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # LCS 是对称的，交换不改变答案；只为让内层维度取到较短的一方，
        # 把滚动数组压到 min(m, n)
        if len(text2) > len(text1):
            text1, text2 = text2, text1
        n = len(text2)
        # 滚动数组省掉的是**行**这一维；此刻 dp[j] 存的是上一行的 f[i-1][j]。
        # 初值全 0 就是边界 f[0][j] = 0：text1 取空前缀时没有任何公共子序列
        dp = [0] * (n + 1)
        for a in text1:
            # 本行第一格的左上角是 f[i-1][0]，恒为 0（text2 取空前缀），所以每行重置为 0。
            # dp[0] 全程不变，不必像编辑距离那样先接住再改写；忘记重置会把上一行末尾的值
            # 当成本行的左上角，答案偏大
            diag = 0
            for j in range(1, n + 1):
                # 必须在覆盖 dp[j] 之前取出：此刻它仍是上一行的 f[i-1][j]，即「上」
                up = dp[j]
                if a == text2[j - 1]:
                    # 末尾字符配成一对，接在「两串各去掉末位」的最优解后面。
                    # 必须用 diag 而不是 max(左, 上)：后者会把同一个字符重复计入，
                    # text1 = "aa"、text2 = "a" 会算出 2 而正确答案是 1
                    dp[j] = diag + 1
                elif dp[j - 1] > up:
                    # 「左」更优：丢掉 text2 的这一位。
                    # 不写 else 分支是有意为之——那种情况下 dp[j] 原样保留着 up，
                    # 正是「丢掉 text1 的这一位」那个候选，滚动数组天然完成了赋值
                    dp[j] = dp[j - 1]
                # 下一列的「左上」正是本列的「上」；漏掉这一步 diag 会一直停在 0，
                # 所有匹配都只能算出长度 1
                diag = up
        return dp[n]

LC1143 最长公共子序列¶