最长公共子序列

子序列（Subsequence）只要求元素相对顺序不变，不要求位置连续。给定序列 $X$ 和 $Y$，LCS 问题旨在找出一个最长的序列，使其同时是 $X$ 和 $Y$ 的子序列。

MIT 的 LCS 课程介绍了如何按序列状态进行动态规划。

定义 $dp[i][j]$ 为前缀 $X[:i]$ 与 $Y[:j]$ 的 LCS 长度，状态转移方程如下：

$$dp[i][j] = \begin{cases} dp[i-1][j-1]+1, & X[i-1]=Y[j-1],\\ \max(dp[i-1][j],dp[i][j-1]), & \text{否则}. \end{cases}$$

边界条件：空前缀对应的行和列初始值均为 0。

def lcs_length(left: str, right: str) -> int:
    previous = [0] * (len(right) + 1)
    for left_item in left:
        current = [0]
        for j, right_item in enumerate(right, start=1):
            if left_item == right_item:
                current.append(previous[j - 1] + 1)
            else:
                current.append(max(previous[j], current[-1]))
        previous = current
    return previous[-1]

复杂度与输出

• 完整 DP 表：时间 $O(mn)$，空间 $O(mn)$。
• 仅求长度：将较短序列作为行宽，空间可优化至 $O(\min(m,n))$，时间仍为 $O(mn)$。
• 重建具体序列：需要保留决策路径、存储完整 DP 表，或使用分治法进行专门的重建。

注意区分：最长公共子串（Substring）要求匹配字符必须连续，这与 LCS 是不同问题。

递推从何而来，表格怎样读

末尾字符不同时，公共子序列不能把二者同时作为最后一次匹配，至少要舍弃一个，因此取两个较短前缀状态的最大值。末尾字符相同时，可以让某个最优解使用这次匹配；在两个较短前缀的最优解后追加该字符，就得到对角转移。依赖项的前缀都更短，既能归纳证明，也保证终止。

left="ABC"、right="AC" 时，含空前缀的各行为 [0,0,0]、[0,1,1]、[0,1,1]、[0,1,2]，长度为 2，AC 是一个解。任意一侧为空串时长度为零。若保留完整表，可从 (m,n) 回溯：字符相同就记录字符并沿对角线移动；否则走向保持最优值的相邻格，最后反转记录结果。并列选择可能产生不同但同样长的子序列。

上述代码实际使用 O(len(right)) 空间。若 right 更长，先交换两输入，才能达到 O(min(m,n)) 空间界。

assert lcs_length("ABC", "AC") == 2
assert lcs_length("", "AC") == 0

参考

• MIT OpenCourseWare: Dynamic Programming II

我的阅读 · 打开过的笔记会记在当前浏览器里。