BM65　最长公共子序列(二)¶

中等通过率 31.88%python3核心代码模式样例通过牛客 AC动态规划

讲解章节：线性 DP

一句话

填出 LCS 表，再从右下角回溯把子序列本身拼出来。

解题思路¶

这题考什么¶

LCS（最长公共子序列，两串各自删去若干字符后能得到的最长相同序列）的标准二维 DP，外加一步方案回溯：题目要的是子序列本身，不是长度。这一点直接决定了空间不能压——滚动数组只留一行，回溯需要整张表， O(n*m) 的空间正是题面允许的上界。前置知识见线性 DP。

状态定义：dp[i][j] = s1 的前 i 个字符与 s2 的前 j 个字符的最长公共子序列长度。转移方程：

s1[i-1] == s2[j-1]:  dp[i][j] = dp[i-1][j-1] + 1
否则:                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
dp[0][*] = dp[*][0] = 0        有一方是空串时公共子序列必为空

末尾字符相同就一定可以把它配成一对：任何不用这对字符的方案，都能改造成用它的方案而长度不减，所以取 dp[i-1][j-1] + 1 不会漏掉最优解。末尾字符不同则两个末字符至少有一个用不上，扔掉其中一个再取较优的那种扔法。

回溯：从 (n, m) 出发倒着走，每一步问「这个格子的值是怎么来的」。

字符相同 -> 这一对字符必定出现在答案里，记下它并同时向左上退一格；
否则往 dp 值更大的那一侧退（相等时任选一侧，题面保证最长公共子序列唯一）。

收集顺序是从后往前，最后反转即得答案。

数据规模与复杂度¶

|str1|, |str2| <= 2000，时限 6 秒（其他语言）。表格 2001 * 2001 约 4e6 格，时间 O(nm)、空间 O(nm)，与题面要求的上界吻合。 4e6 次 Python 级内层迭代逼近 CPython 每秒千万次的量级，所以内层刻意压到最少的操作：行引用 prev / cur 提前取出、比较字符时用局部变量 c 缓存 s1[i-1]，避免每格重复做两次下标寻址。回溯至多走 n + m = 4000 步，可以忽略不计。

坑在哪¶

最长公共子序列为空时要返回字符串 "-1"，不是空串、不是 0，也不是 -1 这个整数。任一输入串为空时同样走这条出口。
不能把 dp 压成一维。滚动数组只保留相邻两行，回溯时问不出「这个值是怎么来的」，方案就还原不回来了。
回溯的分支必须与填表时的取舍一致：填表用 max(dp[i-1][j], dp[i][j-1])，回溯就往值更大的一侧退；两处判据不一致会走到值更小的格子上，拼出的串比 dp[n][m] 短。
回溯拿到的字符是倒序的，漏掉 reverse 会输出整个答案的镜像。
dp 多开一行一列当哨兵边界，于是 s1 的第 i 个字符是 s1[i-1]。这个 ±1 的偏移贯穿全表，混用下标会整体错位。

样例复核¶

s1 = "1A2C3D4B56"、s2 = "B1D23A456A"，dp[10][10] = 6，回溯依次收到 6、5、4、3、2、1，反转后是 "123456"，与期望输出一致。

参考实现¶

solutions/nowcoder/BM65/sol.py
from typing import List, Optional


class Solution:
    def LCS(self, s1: str, s2: str) -> str:
        n, m = len(s1), len(s2)
        if n == 0 or m == 0:
            return "-1"                     # 有一方为空，公共子序列必为空，按题意报 -1
        # dp[i][j]：s1[:i] 与 s2[:j] 的最长公共子序列长度。
        # 多开的第 0 行第 0 列是哨兵边界，全 0，省掉 i-1 / j-1 的越界判断
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            # 把上一行与本行、以及本轮固定的字符先绑成局部名：
            # 内层要跑 2000 次，每次省下的两次下标寻址在 4e6 格上是可观的常数
            prev, cur = dp[i - 1], dp[i]
            c = s1[i - 1]
            for j in range(1, m + 1):
                if c == s2[j - 1]:
                    cur[j] = prev[j - 1] + 1        # 末尾配成一对，接在左上角的答案后面
                else:
                    # 末尾字符对不上，两串各扔一个末字符，取较优的那种扔法
                    a, b = prev[j], cur[j - 1]
                    cur[j] = a if a >= b else b
        if dp[n][m] == 0:
            return "-1"                     # 长度为 0 表示没有公共子序列，题面指定输出 "-1"
        # 回溯：沿着「这个格子的值是怎么来的」倒推，凡是字符相同处即取用了这对字符
        out = []
        i, j = n, m
        while i > 0 and j > 0:
            if s1[i - 1] == s2[j - 1]:
                out.append(s1[i - 1])
                i -= 1
                j -= 1                      # 相同则同时左移与上移，退回左上角的子问题
            elif dp[i - 1][j] >= dp[i][j - 1]:
                i -= 1                      # 判据与填表时的 max 保持一致，才不会走丢长度
            else:
                j -= 1
        out.reverse()                       # 回溯是从后往前收集的，反转才是正序答案
        return "".join(out)

BM65 最长公共子序列(二)¶