假設(shè)有兩個(gè)序列S1[1...m]和S2[1...n]丹允，需要尋找它們之間的一個(gè)最長(zhǎng)公共子序列。
例如铲球，假定我們有如下兩個(gè)序列：
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的一個(gè)最長(zhǎng)公共子序列為THING。又如：
S1：A B C B D A B
S2：B D C A B A
則S1和S2的一個(gè)最長(zhǎng)公共子序列為BCBA。
這里需要注音的是箱沦，一個(gè)子序列不一定必須是連續(xù)的，中間可以被其他字符分開雇庙。最長(zhǎng)公共子序列不一定只有一個(gè)谓形，而我們要尋找的是其中一個(gè)。
設(shè)c[i, j] = LCS(S1[1...i], S2[1...j]) 状共，表示S1[1...i]和S2[1...j]的最長(zhǎng)子序列套耕。那么問(wèn)題的解為c[m, n]。
仔細(xì)觀察我們可以知道：
如果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}（證明略）碾牌。那么我們就將原問(wèn)題分解為相似的子問(wèn)題康愤。而子問(wèn)題很多是重復(fù)的，所以我們將子問(wèn)題的結(jié)果存放到表中舶吗，防止重復(fù)計(jì)算征冷。
最長(zhǎng)公共子序列的Python代碼如下：
#!/usr/bin/python
# -*- coding: utf8 -*-
S1 = ['I', 'T', 'E', 'I', 'N', 'G']
S2 = ['T', 'I', 'N', 'G', 'E']
#后面幾組供測(cè)試使用
#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']
#存儲(chǔ)結(jié)果的數(shù)組，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)]
#用于構(gòu)造最優(yōu)解肴捉，b[i][j]指向一個(gè)表項(xiàng)，這個(gè)表項(xiàng)對(duì)應(yīng)于在計(jì)算c[i][j]時(shí)所選擇的最優(yōu)子問(wèn)題的解
b = [[0 for col in range(len(S2))] for row in range(len(S1))]
#初始化c數(shù)組
for i in range(len(c)):
c[i][0] = 0
for j in range(len(c[0])):
c[0][j] = 0
##初始化b數(shù)組
#for i in range(len(S1)):
# b1 = []
# for j in range(len(S2)):
# b1.append(0)
# b.append(b1)
#使用動(dòng)態(tài)規(guī)則計(jì)算S1和S2的最長(zhǎng)子序列
#返回最長(zhǎng)子序列的長(zhǎng)度
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)]
#根據(jù)表b構(gòu)造出一個(gè)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)
