假设有两个序列S1[1...m]和S2[1...n]，需要寻找它们之间的一个最长公共子序列。
例如，假定我们有如下两个序列：
S1：I N T H E B E G I N N I N G
S2：A L L T H I N G S A R E L O S T
则S1和S2的一个最长公共子序列为THING。又如：
S1：A B C B D A B
S2：B D C A B A
则S1和S2的一个最长公共子序列为BCBA。
这里需要注音的是，一个子序列不一定必须是连续的，中间可以被其他字符分开。最长公共子序列不一定只有一个，而我们要寻找的是其中一个。
设c[i, j] = LCS(S1[1...i], S2[1...j]) ，表示S1[1...i]和S2[1...j]的最长子序列。那么问题的解为c[m, n]。
仔细观察我们可以知道：
如果S1[i] = S2[j]，那么c[i, j] = c[i-1, j-1] + 1，
如果S1[i] ≠ S2[j]，那么c[i, j] = max{c[i-1, j], c[i, j-1}（证明略）。那么我们就将原问题分解为相似的子问题。而子问题很多是重复的，所以我们将子问题的结果存放到表中，防止重复计算。
最长公共子序列的Python代码如下：
#!/usr/bin/python
# -*- coding: utf8 -*-
S1 = ['I', 'T', 'E', 'I', 'N', 'G']
S2 = ['T', 'I', 'N', 'G', 'E']
#后面几组供测试使用
#S1 = ['A', 'N', 'T', 'H']
#S2 = ['A', 'L', 'N', 'T']
#S1 = ['I', 'N', 'T', 'H', 'E', 'B', 'E', 'G']
#S2 = ['A', 'L', 'L', 'T', 'H', 'I', 'N', 'G']
#S1 = ['A', 'B', 'C', 'B', 'D', 'A', 'B']
#S2 = ['B', 'D', 'C', 'A', 'B', 'A']
#存储结果的数组，c[i+1, j+1] = LCS(S1[0...i], S2[0...j])，0<=i<m，0<=j<n
c = [[0 for col in range(len(S2) + 1)] for row in range(len(S1) + 1)]
#用于构造最优解，b[i][j]指向一个表项，这个表项对应于在计算c[i][j]时所选择的最优子问题的解
b = [[0 for col in range(len(S2))] for row in range(len(S1))]
#初始化c数组
for i in range(len(c)):
c[i][0] = 0
for j in range(len(c[0])):
c[0][j] = 0
##初始化b数组
#for i in range(len(S1)):
# b1 = []
# for j in range(len(S2)):
# b1.append(0)
# b.append(b1)
#使用动态规则计算S1和S2的最长子序列
#返回最长子序列的长度
def LCS(S1, S2):
for i in range(len(S1)):
for j in range(len(S2)):
if S1[i] == S2[j]:
c[i + 1][j + 1] = c[i][j] + 1
b[i][j] = "↖"
elif c[i][j + 1] >= c[i + 1][j]:
c[i + 1][j + 1] = c[i][j + 1]
b[i][j] = "↑"
else:
c[i + 1][j + 1] = c[i + 1][j]
b[i][j] = "←"
return c[len(S1)][len(S2)]
#根据表b构造出一个LCS
def print_LCS(b, X, i, j):
if i == -1 or j == -1:
return
if b[i][j] == "↖" :
print_LCS(b, X, i-1, j-1)
print X[i]
elif b[i][j] == "↑":
print_LCS(b, X, i-1, j)
else:
print_LCS(b, X, i, j-1)
print(LCS(S1, S2))
print_LCS(b, S1, len(S1) - 1, len(S2) - 1)
