动态规划算法解最长公共子序列LCS问题
動態規劃算法解LCS問題
作者 July 二零一零年十二月三十一日
本文參考：微軟面試100題系列V0.1版第19、56題、算法導論、維基百科。
第一部分、什么是動態規劃算法
ok，咱們先來了解下什么是動態規劃算法。
動態規劃一般也只能應用于有最優子結構的問題。最優子結構的意思是局部最優解能決定全局最優解(對有些問題這個要求并不能完全滿足，故有時需要引入一定的近似)。簡單地說，問題能夠分解成子問題來解決。
動態規劃算法分以下4個步驟：
好，接下來，咱們討論適合采用動態規劃方法的最優化問題的倆個要素：最優子結構性質，和子問題重疊性質。
- 最優子結構
如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質（即滿足最優化原理）。意思就是，總問題包含很多個子問題，而這些子問題的解也是最優的。
- 重疊子問題
子問題重疊性質是指在用遞歸算法自頂向下對問題進行求解時，每次產生的子問題并不總是新問題，有些子問題會被重復計算多次。動態規劃算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然后將其計算結果保存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地查看一下結果，從而獲得較高的效率。
第二部分、動態規劃算法解LCS問題
下面，咱們運用此動態規劃算法解此LCS問題。有一點必須聲明的是，LCS問題即最長公共子序列問題，它不要求所求得的字符在所給的字符串中是連續的（例如：輸入兩個字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長公共子序列，則輸出它們的長度4，并打印任意一個子序列）。
ok，咱們馬上進入面試題第56題的求解，即運用經典的動態規劃算法：
2.0、LCS問題描述
56.最長公共子序列。
題目：如果字符串一的所有字符按其在字符串中的順序出現在另外一個字符串二中，
則字符串一稱之為字符串二的子串。
注意，并不要求子串（字符串一）的字符必須連續出現在字符串二中。
請編寫一個函數，輸入兩個字符串，求它們的最長公共子串，并打印出最長公共子串。
例如：輸入兩個字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長公共子序列，則輸出它們的長度4，并打印任意一個子序列。
分析：求最長公共子序列（Longest Common Subsequence, LCS）是一道非常經典的動態規劃題，因此一些重視算法的公司像MicroStrategy都把它當作面試題。
事實上，最長公共子序列問題也有最優子結構性質。
記:
Xi=﹤x1，?，xi﹥即X序列的前i個字符 (1≤i≤m)（前綴）
Yj=﹤y1，?，yj﹥即Y序列的前j個字符 (1≤j≤n)（前綴）
假定Z=﹤z1，?，zk﹥∈LCS(X , Y)。
-
若xm=yn（最后一個字符相同），則不難用反證法證明：該字符必是X與Y的任一最長公共子序列Z（設長度為k）的最后一個字符，即有zk = xm = yn 且顯然有Zk-1∈LCS(Xm-1 , Yn-1)即Z的前綴Zk-1是Xm-1與Yn-1的最長公共子序列。此時，問題化歸成求Xm-1與Yn-1的LCS（LCS(X , Y)的長度等于LCS(Xm-1 , Yn-1)的長度加1）。
-
若xm≠yn，則亦不難用反證法證明：要么Z∈LCS(Xm-1, Y)，要么Z∈LCS(X , Yn-1)。由于zk≠xm與zk≠yn其中至少有一個必成立，若zk≠xm則有Z∈LCS(Xm-1 , Y)，類似的，若zk≠yn 則有Z∈LCS(X , Yn-1)。此時，問題化歸成求Xm-1與Y的LCS及X與Yn-1的LCS。LCS(X , Y)的長度為：max{LCS(Xm-1 , Y)的長度, LCS(X , Yn-1)的長度}。
由于上述當xm≠yn的情況中，求LCS(Xm-1 , Y)的長度與LCS(X , Yn-1)的長度，這兩個問題不是相互獨立的：兩者都需要求LCS(Xm-1，Yn-1)的長度。另外兩個序列的LCS中包含了兩個序列的前綴的LCS，故問題具有最優子結構性質考慮用動態規劃法。
也就是說，解決這個LCS問題，你要求三個方面的東西：1、LCS（Xm-1，Yn-1）+1；2、LCS（Xm-1，Y），LCS（X，Yn-1）；3、max{LCS（Xm-1，Y），LCS（X，Yn-1）}。
2.1、最長公共子序列的結構
最長公共子序列的結構有如下表示：
設序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一個最長公共子序列Z=<z1, z2, …, zk>，則：
其中Xm-1=<x1, x2, …, xm-1>，Yn-1=<y1, y2, …, yn-1>，Zk-1=<z1, z2, …, zk-1>。
2.2、子問題的遞歸結構
由最長公共子序列問題的最優子結構性質可知，要找出X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最長公共子序列，可按以下方式遞歸地進行：當xm=yn時，找出Xm-1和Yn-1的最長公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一個最長公共子序列。當xm≠yn時，必須解兩個子問題，即找出Xm-1和Y的一個最長公共子序列及X和Yn-1的一個最長公共子序列。這兩個公共子序列中較長者即為X和Y的一個最長公共子序列。
由此遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如，在計算X和Y的最長公共子序列時，可能要計算出X和Yn-1及Xm-1和Y的最長公共子序列。而這兩個子問題都包含一個公共子問題，即計算Xm-1和Yn-1的最長公共子序列。
與矩陣連乘積最優計算次序問題類似，我們來建立子問題的最優值的遞歸關系。用c[i,j]記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=<x1, x2, …, xi>，Yj=<y1, y2, …, yj>。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列，故c[i,j]=0。其他情況下，由定理可建立遞歸關系如下：
2.3、計算最優值
直接利用上節節末的遞歸式，我們將很容易就能寫出一個計算c[i,j]的遞歸算法，但其計算時間是隨輸入長度指數增長的。由于在所考慮的子問題空間中，總共只有θ(m*n)個不同的子問題，因此，用動態規劃算法自底向上地計算最優值能提高算法的效率。
計算最長公共子序列長度的動態規劃算法LCS_LENGTH(X,Y)以序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>作為輸入。輸出兩個數組c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存儲Xi與Yj的最長公共子序列的長度，b[i,j]記錄指示c[i,j]的值是由哪一個子問題的解達到的，這在構造最長公共子序列時要用到。最后，X和Y的最長公共子序列的長度記錄于c[m,n]中。
[cpp]?view plaincopyprint?由算法LCS_LENGTH計算得到的數組b可用于快速構造序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最長公共子序列。首先從b[m,n]開始，沿著其中的箭頭所指的方向在數組b中搜索。
- 當b[i,j]中遇到"↖"時（意味著xi=yi是LCS的一個元素），表示Xi與Yj的最長公共子序列是由Xi-1與Yj-1的最長公共子序列在尾部加上xi得到的子序列；
- 當b[i,j]中遇到"↑"時，表示Xi與Yj的最長公共子序列和Xi-1與Yj的最長公共子序列相同；
- 當b[i,j]中遇到"←"時，表示Xi與Yj的最長公共子序列和Xi與Yj-1的最長公共子序列相同。
這種方法是按照反序來找LCS的每一個元素的。由于每個數組單元的計算耗費Ο(1)時間，算法LCS_LENGTH耗時Ο(mn)。
2.4、構造最長公共子序列
下面的算法LCS(b,X,i,j)實現根據b的內容打印出Xi與Yj的最長公共子序列。通過算法的調用LCS(b,X,length[X],length[Y])，便可打印出序列X和Y的最長公共子序列。
[cpp]?view plaincopyprint?在算法LCS中，每一次的遞歸調用使i或j減1，因此算法的計算時間為O(m+n)。
例如，設所給的兩個序列為X=和Y=。由算法LCS_LENGTH和LCS計算出的結果如下圖所示：
我來說明下此圖（參考算法導論）。在序列X={A，B，C，B，D，A，B}和 Y={B，D，C，A，B，A}上，由LCS_LENGTH計算出的表c和b。第i行和第j列中的方塊包含了c[i，j]的值以及指向b[i，j]的箭頭。在c[7,6]的項4，表的右下角為X和Y的一個LCS的長度。對于i，j>0，項c[i，j]僅依賴于是否有xi=yi，及項c[i-1，j]和c[i，j-1]的值，這幾個項都在c[i，j]之前計算。為了重構一個LCS的元素，從右下角開始跟蹤b[i，j]的箭頭即可，這條路徑標示為陰影，這條路徑上的每一個“↖”對應于一個使xi=yi為一個LCS的成員的項（高亮標示）。
所以根據上述圖所示的結果，程序將最終輸出：“B C B A”，或“B D A B”。
可能還是有讀者對上面的圖看的不是很清楚，下面，我再通過對最大子序列，最長公共子串與最長公共子序列的比較來闡述相關問題@Orisun：
- 最大子序列：最大子序列是要找出由數組成的一維數組中和最大的連續子序列。比如{5,-3,4,2}的最大子序列就是{5,-3,4,2}，它的和是8,達到最大；而{5,-6,4,2}的最大子序列是{4,2}，它的和是6。你已經看出來了，找最大子序列的方法很簡單，只要前i項的和還沒有小于0那么子序列就一直向后擴展，否則丟棄之前的子序列開始新的子序列，同時我們要記下各個子序列的和，最后找到和最大的子序列。更多請參看：程序員編程藝術第七章、求連續子數組的最大和。
- 最長公共子串：找兩個字符串的最長公共子串，這個子串要求在原字符串中是連續的。其實這又是一個序貫決策問題，可以用動態規劃來求解。我們采用一個二維矩陣來記錄中間的結果。這個二維矩陣怎么構造呢？直接舉個例子吧："bab"和"caba"(當然我們現在一眼就可以看出來最長公共子串是"ba"或"ab")
b a b
c 0 0 0
a 0 1 0
b 1 0 1
a 0 1 0
我們看矩陣的斜對角線最長的那個就能找出最長公共子串。
不過在二維矩陣上找最長的由1組成的斜對角線也是件麻煩費時的事，下面改進：當要在矩陣是填1時讓它等于其左上角元素加1。
b a b
c 0 0 0
a 0 1 0
b 1 0 2
a 0 2 0
這樣矩陣中的最大元素就是最長公共子串的長度。
在構造這個二維矩陣的過程中由于得出矩陣的某一行后其上一行就沒用了，所以實際上在程序中可以用一維數組來代替這個矩陣。
- 最長公共子序列LCS問題：最長公共子序列與最長公共子串的區別在于最長公共子序列不要求在原字符串中是連續的，比如ADE和ABCDE的最長公共子序列是ADE。
我們用動態規劃的方法來思考這個問題如是求解。首先要找到狀態轉移方程：
等號約定，C1是S1的最右側字符，C2是S2的最右側字符，S1‘是從S1中去除C1的部分，S2'是從S2中去除C2的部分。
LCS(S1,S2)等于：
（1）LCS（S1，S2’）
（2）LCS（S1’，S2）
（3）如果C1不等于C2：LCS（S1’，S2’）；如果C1等于C2：LCS（S1'，S2'）+C1；
邊界終止條件：如果S1和S2都是空串，則結果也是空串。
下面我們同樣要構建一個矩陣來存儲動態規劃過程中子問題的解。這個矩陣中的每個數字代表了該行和該列之前的LCS的長度。與上面剛剛分析出的狀態轉移議程相對應，矩陣中每個格子里的數字應該這么填，它等于以下3項的最大值：
（1）上面一個格子里的數字
（2）左邊一個格子里的數字
（3）左上角那個格子里的數字（如果C1不等于C2）；左上角那個格子里的數字+1（如果C1等于C2）
舉個例子：
G C T A
0 0 0 0 0
G 0 1 1 1 1
B 0 1 1 1 1
T 0 1 1 2 2
A 0 1 1 2 3
填寫最后一個數字時，它應該是下面三個的最大者：
（1）上邊的數字2
（2）左邊的數字2
（3）左上角的數字2+1=3,因為此時C1==C2
所以最終結果是3。
在填寫過程中我們還是記錄下當前單元格的數字來自于哪個單元格，以方便最后我們回溯找出最長公共子串。有時候左上、左、上三者中有多個同時達到最大，那么任取其中之一，但是在整個過程中你必須遵循固定的優先標準。在我的代碼中優先級別是左上>左>上。
下圖給出了回溯法找出LCS的過程：
2.5、算法的改進
對于一個具體問題，按照一般的算法設計策略設計出的算法，往往在算法的時間和空間需求上還可以改進。這種改進，通常是利用具體問題的一些特殊性。
例如，在算法LCS_LENGTH和LCS中，可進一步將數組b省去。事實上，數組元素c[i,j]的值僅由c[i-1,j-1]，c[i-1,j]和c[i,j-1]三個值之一確定，而數組元素b[i,j]也只是用來指示c[i,j]究竟由哪個值確定。因此，在算法LCS中，我們可以不借助于數組b而借助于數組c本身臨時判斷c[i,j]的值是由c[i-1,j-1]，c[i-1,j]和c[i,j-1]中哪一個數值元素所確定，代價是Ο(1)時間。既然b對于算法LCS不是必要的，那么算法LCS_LENGTH便不必保存它。這一來，可節省θ(mn)的空間，而LCS_LENGTH和LCS所需要的時間分別仍然是Ο(mn)和Ο(m+n)。不過，由于數組c仍需要Ο(mn)的空間，因此這里所作的改進，只是在空間復雜性的常數因子上的改進。
另外，如果只需要計算最長公共子序列的長度，則算法的空間需求還可大大減少。事實上，在計算c[i,j]時，只用到數組c的第i行和第i-1行。因此，只要用2行的數組空間就可以計算出最長公共子序列的長度。更進一步的分析還可將空間需求減至min(m, n)。
第三部分、最長公共子序列問題代碼
ok，最后給出此面試第56題的代碼，參考代碼如下，請君自看：
[cpp]?view plaincopyprint? 程序運行結果如下所示：
擴展：如果題目改成求兩個字符串的最長公共子字符串，應該怎么求？子字符串的定義和子串的定義類似，但要求是連續分布在其他字符串中。
比如輸入兩個字符串BDCABA和ABCBDAB的最長公共字符串有BD和AB，它們的長度都是2。
第四部分、LCS問題的時間復雜度
算法導論上指出，
關于此動態規劃算法更多可參考 算法導論一書第15章 動態規劃問題，至于關于此面試第56題的更多，可參考我即將整理上傳的答案V04版第41-60題的答案。
補充：一網友提供的關于此最長公共子序列問題的java算法源碼，我自行測試了下，正確：
import java.util.Random;
public class LCS{
public static void main(String[] args){
//設置字符串長度
int substringLength1 = 20;
int substringLength2 = 20; //具體大小可自行設置
// 隨機生成字符串
String x = GetRandomStrings(substringLength1);
String y = GetRandomStrings(substringLength2);
Long startTime = System.nanoTime();
// 構造二維數組記錄子問題x[i]和y[i]的LCS的長度
int[][] opt = new int[substringLength1 + 1][substringLength2 + 1];
// 動態規劃計算所有子問題
for (int i = substringLength1 - 1; i >= 0; i--){
for (int j = substringLength2 - 1; j >= 0; j--){
if (x.charAt(i) == y.charAt(j))
opt[i][j] = opt[i + 1][j + 1] + 1; //參考上文我給的公式。
else
opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]); //參考上文我給的公式。
}
}
-------------------------------------------------------------------------------------
理解上段，參考上文我給的公式：
根據上述結論，可得到以下公式，
如果我們記字符串Xi和Yj的LCS的長度為c[i,j]，我們可以遞歸地求c[i,j]：
-------------------------------------------------------------------------------------
System.out.println("substring1:"+x);
System.out.println("substring2:"+y);
System.out.print("LCS:");
int i = 0, j = 0;
while (i < substringLength1 && j < substringLength2){
if (x.charAt(i) == y.charAt(j)){
System.out.print(x.charAt(i));
i++;
j++;
} else if (opt[i + 1][j] >= opt[i][j + 1])
i++;
else
j++;
}
Long endTime = System.nanoTime();
System.out.println(" Totle time is " + (endTime - startTime) + " ns");
}
//取得定長隨機字符串
public static String GetRandomStrings(int length){
StringBuffer buffer = new StringBuffer("abcdefghijklmnopqrstuvwxyz");
StringBuffer sb = new StringBuffer();
Random r = new Random();
int range = buffer.length();
for (int i = 0; i < length; i++){
sb.append(buffer.charAt(r.nextInt(range)));
}
return sb.toString();
}
}
eclipse運行結果為：
substring1:akqrshrengxqiyxuloqk
substring2:tdzbujtlqhecaqgwfzbc
LCS:qheq Totle time is 818058 ns
OK，更多，請參考：程序員編程藝術第十一章、最長公共子序列（LCS）問題。完。
總結
以上是生活随笔為你收集整理的动态规划算法解最长公共子序列LCS问题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 求连续子数组的最大和
- 下一篇： 数值概率算法