最长的共同子序列
动态规划最重要的实现之一是找出最长公共子序列 。我们先来定义一些基本术语。
子序列：
子序列是可以通过删除一些元素而不改变其余元素的顺序从另一序列导出的序列。假设我们有一个字符串 ABC 。如果我们从这个字符串中删除零个或一个或多个字符，我们得到该字符串的子序列。所以字符串 ABC 的子序列将是{ A ， B ， C ， AB ， AC ， BC ， ABC ， “” }。即使我们删除所有字符，空字符串也将是一个子序列。为了找出子序列，对于字符串中的每个字符，我们有两个选项 - 要么我们接受字符，要么我们不接受。因此，如果字符串的长度为 n ，则该字符串有 2 个 n 个子序列。
最长的共同子序列：
顾名思义，在两个字符串之间的所有公共子序列中，最长的公共子序列（LCS）是具有最大长度的子序列。例如： HELLOM 和 HMLD 之间的共同子序列是 H ， HL ， HM 等。这里 HLL 是长度为 3 的最长公共子序列。
蛮力方法：
我们可以使用回溯生成两个字符串的所有子序列。然后我们可以比较它们以找出常见的子序列。在我们需要找出具有最大长度的那个之后。我们已经看到，长度为 n 的字符串有 2 个 n 个子序列。如果我们的 n 超过 **20-25，**那么解决问题需要数年时间。
动态编程方法：
让我们用一个例子来接近我们的方法。假设我们有两个字符串 abcdaf 和 acbcf 。让我们用 s1 和 s2 表示这些。因此，这两个字符串的最长公共子序列将是 abcf ，其长度为 4.再次提醒你，子序列不需要在字符串中连续。为了构建 ABCF ，我们忽略了 阿凡达 中的 S1 和 C 的 S2 。我们如何使用动态编程找到它？
我们将从一个表（一个二维数组）开始，该表包含连续 s1 的所有字符以及列中 s2 的所有字符。这里的表是 0 索引的，我们将字符从 1 开始向前。我们将每行从左到右遍历表格。我们的表格如下：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
这里每行和每列表示两个字符串之间最长公共子序列的长度，如果我们取出该行和列的字符并添加到它之前的前缀。例如： 表[2] [3] 表示 ac 和 abc 之间最长公共子序列的长度。
第 0 列表示 s1 的空子序列。类似地，第 0 行表示 s2 的空子序列。如果我们取一个字符串的空子序列并尝试将其与另一个字符串匹配，则无论第二个子字符串的长度是多长，公共子序列的长度都为 0。所以我们可以用 0 来填充第 0 行和第 0 列。我们得到：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
让我们开始。当我们填写表[1] [1]时，我们问自己，如果我们有一个字符串 a 和另一个字符串 a 而没有别的，这里最常见的子序列是什么？这里 LCS 的长度为 1.现在让我们看一下表[1] [2] 。我们有字符串 ab 和字符串 a 。LCS 的长度为 1.如你所见，其余值对于第一行也是 1，因为它只考虑字符串 a 与 abcd ， abcda ， abcdaf 。所以我们的表格看起来像：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
对于第 2 行，现在将包括 c 。对于表[2] [1]，我们在一侧有一个 ac，在另一侧有一个。所以 LCS 的长度是 1.我们从哪里得到这个 1？从顶部，其表示该 LCS 一个 2 子之间。所以我们所说的是，如果 s1 [2] 和 s2 [1] 不相同，那么 LCS 的长度将是顶部或左侧 LCS 长度的最大值。将 LCS 的长度置于顶部表示，我们不从 s2 获取当前字符。类似地，在左侧取 LCS 的长度表示，我们不从当前字符中取出 s1 创建 LCS。我们得到：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
所以我们的第一个公式是：
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
继续，对于表[2] [2]，我们有字符串 ab 和 ac 。由于 c 和 b 不相同，我们在这里放置顶部或左侧的最大值。在这种情况下，它又是 1.在那之后，对于表[2] [3]，我们有字符串 abc 和 ac 。此时行和列的当前值都相同。现在 LCS 的长度将等于 LCS 的最大长度+ 1。到目前为止，我们如何获得 LCS 的最大长度？我们检查对角线值，它代表 ab 和 a 之间的最佳匹配。从这个状态，对于当前值，我们又向 s1 和 s 添加了一个字符 s2 碰巧是一样的。所以 LCS 的长度当然会增加。我们把 1 + 1 = 2 在表[2] [3] 。我们得到了，
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
所以我们的第二个公式是：
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
我们已经定义了这两种情况。使用这两个公式，我们可以填充整个表。填满表后，它将如下所示：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+
s1 和 s2 之间的 LCS 长度将为表[5] [6] = 4 。这里，5 和 6 分别是 s2 和 s1 的长度。我们的伪代码将是：
Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
Table[0][i] = 0
endfor
for i from 1 to s2.length
Table[i][0] = 0
endfor
for i from 1 to s2.length
for j from 1 to s1.length
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[s2.length][s1.length]
该算法的时间复杂度为： O(mn) 其中 m 和 n 表示每个字符串的长度。
我们如何找出最长的共同子序列？我们将从右下角开始。我们将检查价值的来源。如果该值来自对角线，即如果 Table [i-1] [j-1] 等于 Table [i] [j] -1 ，则我们推 s2 [i] 或 s1 [j] （两者都是是相同的）并对角移动。如果该值来自 top，这意味着，如果 Table [i-1] [j] 等于 Table [i] [j] ，我们将移至顶部。如果值来自左边，那意味着，如果 Table [i] [j-1] 等于 Table [i] [j] ，我们向左移动。当我们到达最左侧或最顶部的列时，我们的搜索结束。然后我们从堆栈中弹出值并打印它们。伪代码：
Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
S.push(s1[j]) //or S.push(s2[i])
i := i - 1
j := j - 1
else if Table[i-1][j] == Table[i][j]
i := i-1
else
j := j-1
endif
endwhile
while S is not empty
print(S.pop)
endwhile
需要注意的是：如果表[i-1] [j] 和表[i] [j-1] 都等于表[i] [j] 并且表[i-1] [j-1] 不是等于表[i] [j] - 1 ，那个时刻可以有两个 LCS。这个伪代码不考虑这种情况。你必须递归地解决这个问题才能找到多个 LCS。
该算法的时间复杂度为： O（max(m, n)） 。