动态规划

动态规划把一个大问题写成若干会反复出现的小问题，规定每个小问题的答案与更小问题的关系，并按依赖顺序只计算一次。它不是一条固定的“套公式”指令；状态若漏掉影响后续决策的信息，递推再快也会算错。最长公共子序列提供一个能逐格核对的例子。

从两个字符串取共同子序列

给定 $x = A B C A$ 与 $y = B A C A$ 。子序列允许跳过字符，但剩下字符的先后次序不能变；例如 ACA 是两串的共同子序列，在 x 中取第 1、3、4 个字符，在 y 中取第 2、3、4 个字符，长度为 3。BCA 也长 3，所以答案不唯一。子串要求连续，不能与子序列混称。

若只看两个字符串的前缀，许多小问题会被反复问到。记 $L (i, j)$ 为 x 的前 $i$ 个字符与 y 的前 $j$ 个字符的最长公共子序列长度。任一前缀为空时， $L (0, j) = L (i, 0) = 0$ 。

从末尾字符得到递推

看两个前缀最后的字符。若 $x_{i} = y_{j}$ ，可以把这个共同字符接在更短前缀的一条最长公共子序列后面，得到 $L (i, j) = 1 + L (i - 1, j - 1) .$ 等式不会漏掉更长答案：任意公共子序列若避开两个末尾，长度至多是 $L (i - 1, j - 1)$ ；若使用至少一个末尾，删掉它最后一个配对字符后，其余部分位于两个更短前缀中，长度至多是 $L (i - 1, j - 1) + 1$ 。所以右侧既能达到，也没有更长的可能。

若 $x_{i} \neq y_{j}$ ，一条共同子序列不可能同时把这两个不同字符当作末尾；至少要舍弃其中一个。因此 $L (i, j) = max {L (i - 1, j), L (i, j - 1)} .$ 这两个式子只依赖当前格上方、左方或左上方的格，故可从短前缀向长前缀填表。图中行对应 x 的前缀、列对应 y 的前缀；金色格子是一条回溯路线中实际配对的 A、C、A。

字符串ABCA与BACA的最长公共子序列长度表，零到四的前缀组成五乘五格，右下角数值三；配对格对应A、C、A — 右下角的 3 是最长长度；高亮格标出返回的 ACA，另有 BCA 也可达到同样长度。

例如最后两字符同为 A，故 $L (4, 4) = 1 + L (3, 3) = 1 + 2 = 3$ 。从右下角往回看，遇到相同字符就收下并向左上走；末尾不同则走向保留最大长度的相邻格。这样不仅得到长度，还能还原一条具体子序列。相等时选择哪条路，可能改变返回的是 ACA 还是 BCA，却不改变长度 3。

最长公共子序列填表

逐格利用左、上、左上方的状态，得到右下角的答案。

静态配图与完整推导见本节正文；交互演示需浏览器启用 JavaScript。

Python 实现

代码按行填表，再从右下角回溯。若两个候选格一样大，约定先向上走，以便示例稳定地返回 ACA。

Python 3

def longest_common_subsequence(x, y):
    n, m = len(x), len(y)
    length = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                length[i][j] = length[i - 1][j - 1] + 1
            else:
                length[i][j] = max(length[i - 1][j], length[i][j - 1])

    i, j = n, m
    letters = []
    while i > 0 and j > 0:
        if x[i - 1] == y[j - 1]:
            letters.append(x[i - 1])
            i -= 1
            j -= 1
        elif length[i - 1][j] >= length[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return length[n][m], "".join(reversed(letters))


if __name__ == "__main__":
    assert longest_common_subsequence("ABCA", "BACA") == (3, "ACA")
    assert longest_common_subsequence("", "BACA") == (0, "")
    assert longest_common_subsequence("A", "B") == (0, "")

状态、顺序与代价

两个前缀长度分别有 $n + 1$ 、 $m + 1$ 种取值，每格只做常数次比较，所以时间为 $O (n m)$ ，保存整张表用 $O (n m)$ 空间。若只求长度，可只保留相邻两行，把空间降到 $O (min {n, m})$ ；但要回溯一条具体答案，就不能直接丢掉所有中间决策。代码中的字符比较按常数成本计。

0-1背包问题也按“只看前几件物品”建状态，不过第二个坐标是剩余容量，而不是另一个字符串的前缀。两篇共同的做法是：明确状态代表的全部条件，列出互斥而穷尽的最后一步，再按无环依赖计算。它们的复杂度不同；背包按容量逐格填表时还要留意容量的数值和输入位数不是一回事。

参考资料

TheAlgorithms/Python：longest_common_subsequence.py：选题与实现对照，本文案例和代码独立编写。
MIT 6.006，Longest Common Subsequence：前缀状态、填表与回溯。
先修：算法与复杂度；应用：0-1背包问题。