查看“︁动态规划”︁的源代码

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

== 从两个字符串取共同子序列 ==
给定 <math>x=\mathrm{ABCA}</math> 与 <math>y=\mathrm{BACA}</math>。'''子序列'''允许跳过字符，但剩下字符的先后次序不能变；例如 ACA 是两串的共同子序列，在 x 中取第 1、3、4 个字符，在 y 中取第 2、3、4 个字符，长度为 3。BCA 也长 3，所以答案不唯一。'''子串'''要求连续，不能与子序列混称。

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

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

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

[[File:Gezhi-dp-lcs-table.svg|frame|center|alt=字符串ABCA与BACA的最长公共子序列长度表，零到四的前缀组成五乘五格，右下角数值三；配对格对应A、C、A|右下角的 3 是最长长度；高亮格标出返回的 ACA，另有 BCA 也可达到同样长度。]]

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

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

<pre class="algorithm-code" style="white-space: pre; overflow-x: auto;">
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 &gt; 0 and j &gt; 0:
        if x[i - 1] == y[j - 1]:
            letters.append(x[i - 1])
            i -= 1
            j -= 1
        elif length[i - 1][j] &gt;= 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, "")
</pre>

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

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

== 参考资料 ==
* [https://github.com/TheAlgorithms/Python/blob/c27e95123cb7e2fef5b15e64b5e800201cc7665c/dynamic_programming/longest_common_subsequence.py TheAlgorithms/Python：longest_common_subsequence.py]：选题与实现对照，本文案例和代码独立编写。
* [https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2008/resources/lec20/ MIT 6.006，Longest Common Subsequence]：前缀状态、填表与回溯。
* 先修：[[算法与复杂度]]；应用：[[0-1背包问题]]。
[[分类:算法]]