一、最長公共子序列問題

1、問題概念

• 一個序列的子序列是在該序列中刪去若干元素后得 到的序列。

• 例如："ABCD”和“BDF”都是“ABCDEFG”的子序列。

• 最長公共子序列(LCS) 問題: 給定兩個序列X和Y，求X和Y長度最大的公共子字列。

• 例:X="ABBCBDE”Y="DBBCDB”LCS(XY)="BBCD"

• 應用場景:字符串相似度比對

2、問題求解思路

（1）問題思考

• 思考: 暴力窮舉法的時間復雜度是多少?

序列中的每一個值都有兩種選擇，被選擇或者不被選擇，因此一個長度為n的序列，其子序列為種。求解長度為n和長度為m的序列的公共子序列，對比和個子序列之間的關系，是否相同，因此時間復雜度為O()。

• 思考: 最長公共子序列是否具有最優(yōu)子結構性質?

有，見解最優(yōu)子結構

（2）最優(yōu)子結構

（LCS的最優(yōu)子結構）：令X=(，，......，）和Y=(，，......，)為兩個序列，Z=(，，......，)為X和Y的任意 LCS。

• 如果 = ，則 = = 且是和的一個LCS。

例如：序列ABCD和ABD，其LCS為ABD，此時 = = =D，可見，AB是ABC和AB的LCS。

• 如果，且意味著Z是和Y的一個LCS。

例如：序列ABCD和ABC，其LCS為ABC，此時，即D與C不相等，則為ABC，可見，ABC是ABC和ABC的LCS。

• 如果，且意味著Z是X和的一個LCS。

例如：序列ABC和ACD，其LCS為AC，此時，即D與C不相等，則為AC，可見，AC是ABC和AC的LCS。

示例如下：

要求a="ABCBDAB"與b="BDCABA"的LCS：

• 由于最后一位"B“≠"A”：

• 因此LCS(a,b)應該來源于LCS(a[:-1],b)與LCS(a,b[:-1])中更大的那一個

（3）問題遞推式

1）遞推式推理說明

結合最優(yōu)子結構的定理，可以得到以上的圖。

舉例解析：

• x0都是空列表，y0也是空列表，因此與x0或者y0的LCS一定是0。

• 序列BDC和序列A：C != A，則LCS來源與LCS([BDC],[ ])和LCS([BD],[A])中，圖中可看出，兩者都為0，即LCS([BDC], [A])的左邊和上邊的位置。

• 序列BDCA和序列A：A = A，則A一定是兩個序列的LCS中的一個元素，且LCS([BDC], [A])加上元素A就是LCS([BDCA], [A])。查看可知，LCS([BDC], [A]) = 0，所以LCS([BDCA], [A]) = 0 + 1(元素A)。

• 剩余的同理。

2）遞推式

c[i,j]表示和的LCS長度

二、最長公共子序問題代碼實現(xiàn)

1、最長公共子序長度求解

def lcs_length(x,y): # 公共子序列長度，x，y: 字符串、列表等序列m = len(x) # x序列長度n = len(y) # y序列長度c = [[0 for i in range(n + 1)] for _ in range(m+1)] # 創(chuàng)建m行n列二維數(shù)組，初始值為0 for i in range(1, m+1):  # 按數(shù)組的行求，x0都為0不用求，所以從1開始for j in range(1, n+1): # 數(shù)組每行中的遍歷，y0都為0，不用求if x[i - 1] == y[j - 1]:  # x[i-1]其實是字符串的i，因為i=0在二維列表中都是0，不求解，但是在字符串中仍需要從索引0遍歷c[i][j] = c[i-1][j-1] + 1 # 遞推式else:  # xi！=yic[i][j] = max(c[i-1][j],c[i][j-1])  # 遞推式return c[m][n]    # x和y的最后一個元素對比完，二維數(shù)組的最后一位print(lcs_length('ABCBDAB', 'BDCABA'))

輸出結果

4

2、最長公共子序的序列求解

動態(tài)規(guī)劃+ 回溯算法搭配使用，動態(tài)規(guī)劃求解最優(yōu)值，回溯法推算出過程的解。

（1）動態(tài)規(guī)劃求解并存儲解-代碼實現(xiàn)

# 動態(tài)規(guī)劃求解，存儲解及解的計算過程
def lcs(x,y): # 求解并存儲箭頭方向，x，y為字符串、列表等序列m = len(x) # x的長度n = len(y) # y的長度c = [[0 for i in range(n+1)] for _ in range(m+1)] # 二維數(shù)組，初始值為0，用于存儲長度結果d = [[0 for i in range(n+1)] for _ in range(m+1)] # 二維數(shù)組，初始值為0，用于存儲箭頭方向,1表示左上，2表示上，3表示左for i in range(1,m+1): # 按行遍歷二維數(shù)組for j in range(1,n+1): # 每行的各數(shù)值遍歷， c0j和ci0相關的值都為0，所以均從1開始if x[i - 1] == y[j - 1]: # xi=yi的情況，二維數(shù)組中i，j=0時，都為0已經確定，但字符串x，y仍需從0開始遍歷c[i][j] = c[i - 1][j - 1] + 1 # 遞推式d[i][j] = 1 # 箭頭方向左上方elif c[i][j - 1] > c[i - 1][j]: # 遞推式，選擇更大的c[i][j] = c[i][j - 1]d[i][j] = 3 # 箭頭左邊else: # c[i-1][j] >= c[i][j-1]c[i][j] = c[i - 1][j]d[i][j] = 2 # 箭頭上方return c[m][n], dc, d = lcs("ABCBDAB", "BDCABA")
for _ in d:print(_)

輸出結果：

[0, 0, 0, 0, 0, 0, 0]
[0, 2, 2, 2, 1, 3, 1]
[0, 1, 3, 3, 2, 1, 3]
[0, 2, 2, 1, 3, 2, 2]
[0, 1, 2, 2, 2, 1, 3]
[0, 2, 1, 2, 2, 2, 2]
[0, 2, 2, 2, 1, 2, 1]
[0, 1, 2, 2, 2, 1, 2]

（2）回溯算法的應用-代碼實現(xiàn)

# 動態(tài)規(guī)劃求解，存儲解及解的計算過程
def lcs(x,y): # 求解并存儲箭頭方向，x，y為字符串、列表等序列m = len(x) # x的長度n = len(y) # y的長度c = [[0 for i in range(n+1)] for _ in range(m+1)] # 二維數(shù)組，初始值為0，用于存儲長度結果d = [[0 for i in range(n+1)] for _ in range(m+1)] # 二維數(shù)組，初始值為0，用于存儲箭頭方向,1表示左上，2表示上，3表示左for i in range(1,m+1): # 按行遍歷二維數(shù)組for j in range(1,n+1): # 每行的各數(shù)值遍歷， c0j和ci0相關的值都為0，所以均從1開始if x[i - 1] == y[j - 1]: # xi=yi的情況，二維數(shù)組中i，j=0時，都為0已經確定，但字符串x，y仍需從0開始遍歷c[i][j] = c[i - 1][j - 1] + 1 # 遞推式d[i][j] = 1 # 箭頭方向左上方elif c[i][j - 1] > c[i - 1][j]: # 遞推式，選擇更大的c[i][j] = c[i][j - 1]d[i][j] = 3 # 箭頭左邊else: # c[i-1][j] >= c[i][j-1]c[i][j] = c[i - 1][j]d[i][j] = 2 # 箭頭上方return c[m][n], d# 回溯算法
def lcs_trackback(x,y): # 最長公共子序列的序列c, d = lcs(x, y) # c長度，d箭頭方向i = len(x) # x的長度j = len(y) # y的長度res = [] # 結果列表while i > 0 and j > 0 : # 序列x和y還有值未比對，任何一個序列為0了都不再繼續(xù)if d[i][j] == 1: # 箭頭左上方 ——> 匹配res.append(x[i - 1])  # 二維列表中i=0時，值為0，但是序列x的值是從0開始遍歷的i = i - 1 # 位置移到左上位置j = j - 1elif d[i][j] == 2: # 箭頭上方->不匹配i = i - 1 # 位置往上移一格else: # dij = 3 ，箭頭左向j = j - 1 # 位置往左移一格return "".join(reversed(res))  # 列表翻轉，并將列表用''連接成字符串print(lcs_trackback("ABCBDAB", "BDCABA"))

結果輸出

BCBA