1、動態規劃解最長公共子序列 一、 問題描述與分析經常遇到一些復雜的問題，有時我們將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。由于分解到的子問題往往不是獨立的，用一個表來記錄所有已解決的子問題的答案，這樣就得到了原問題的解，這就是動態規劃法的基本思想。一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。給定兩個序列X和Y，當另一序列Z即是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。在公共子序列中長度最長的則是最長公共子序列。窮舉搜索法是最容易想到的解題算法。對X的所有子序列，檢查它是否也是Y的子序列，從而確定它是否是X和Y的公共子序列。并且

2、在檢查過程中記錄最長的公共子序列。X的所有子序列都檢查過后即可求出X和Y的最長公共子序列。事實上，最長公共子序列問題具有最優子結構的結構性質。二、 算法設計1. 最長公共子序列的結構設序列X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列為Z=z1,z2,zk，則1) 若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長公共子序列；2) 若xmyn 且zkxm，則Z是Xm-1和Y的最長公共子序列；3) 若xmyn 且zkyn，則Z是X和Yn-1的最長公共子序列。其中，Xm-1=x1,x2,xm-1; Yn-1=y1,y2,yn-1; Zk-1=z1,z2,zk-1。證

3、明： 1) 用反證法。若zkxm，則z1,z2,zk,xm是X和Y的長度為k+1的公共子序列。這與Z是X和Y的最長公共子序列矛盾。因此，必有zk=xm=yn。由此可知Zk-1是Xm-1和Yn-1的長度為k-1的公共子序列。若Xm-1和Yn-1有長度大于k-1的公共子序列W，則將xm加在其尾部產生X和Y的長度大于k的公共子序列。此為矛盾。故Zk-1是Xm-1和Yn-1的最長公共子序列。2) 由于zkxm，Z是Xm-1和Y的公共子序列。若Xm-1和Y有長度大于k的公共子序列W，則W也是X和Y的長度大于k的公共子序列。這與Z是X和Y的最長公共子序列矛盾。由此即知，Z是Xm-1和Y的公共子序列。3)

4、證明與（2）類似。2. 子問題的遞歸結構由最長公共子序列的問題的最優子結構可知，當xm=yn時，找出是Xm-1和Yn-1的最長公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的最長公共子序列。當xmyn時，必須解兩個子問題，即找出Xm-1和Y的一個最長公共子序列及X和Yn-1的一個最長公共子序列。這兩個公共子序列中較長者即為X和Y的最長公共子序列。由此遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。首先建立子問題最優值的遞歸關系。用Cij記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=x1,x2,xm；Yj=y1,y2,yn。當i=0或j=0時，空序列是Xi和Yj的最長公共子序

5、列，故此時Cij=0。在其他情況下，由最優子結構性質可建立遞歸關系如下：Cij= 0 i=0，j=0 ci-1j-1+1 i，j>0；xi =yj maxcij-1，ci-1j i，j>0；xi yj 3. 例子：求兩字符序列的最長公共字符子序列問題描述：字符序列的子序列是指從給定字符序列中隨意地（不一定連續）去掉若干個字符（可能一個也不去掉）后所形成的字符序列。令給定的字符序列X=x1,x2,xm，序列Y=y1,y2,yn是X的子序列，存在X的一個嚴格遞增下標序列i0，i1，ik-1，使得對所有的j=0，1，k-1，有xi=yj。例如，X=“BACDCA”，Y=“ABDCA”是X

6、的一個子序列。考慮最長公共子序列問題如何分解成子問題，設A=a0，a1，am-1，B=b0，b1，bm-1，并Z=z0，z1，zm-1為它們的最長公共子序列。不難證明有以下性質：1) 如果am-1=bn-1，則若zk-1=am-1=bn-1，得z0，z1，zm-1是a0，a1，am-1和b0，b1，bm-1的一個最長公共子序列；2) 如果am-1bn-1，則若zk-1am-1，得z0，z1，zm-1是a0，a1，am-2和b0，b1，bm-1的一個最長公共子序列；3) 如果am-1bn-1，則若zk-1bn-1，得z0，z1，zm-1是a0，a1，am-1和b0，b1，bm-2的一個最長公共子

7、序列。這樣，在找A和B的公共子序列時，如有am-1=bn-1，則進一步解決一個子問題，找a0，a1，am-1和b0，b1，bm-1的一個最長公共子序列；如果zk-1bn-1，則要解決兩個子問題，找出a0，a1，am-2和b0，b1，bm-1的一個最長公共子序列和找出a0，a1，am-1和b0，b1，bm-2的一個最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列。引進一個二維數組cij，用cij記錄Xi與Yj的LCS 的長度，bij記錄 cij，是通過哪一個子問題的值求得的，以決定搜索的方向。我們是自底向上進行遞推計算，那么在計算cij之前，ci-1j-1，ci-j與cij-1均已計算

8、出來。此時我們根據xi=yj還是xiyj，就可以計算出cij?；厮葺敵鲎铋L公共子序列過程：jABDCAi000000B00211131313A01112121221C01212122122D01212212222C01212223133A01112223241則輸出結果為：BDCA由于每次調用至少向上或向左（或向上向左同時）移動一步，故最多調用(m + n)次就會遇到i = 0或j = 0的情況，此時開始返回。返回時與遞歸調用時方向相反，步數相同，故算法時間復雜度為Om+n。4. 得出算法：計算最優化：cij存儲Xi與Yj的最長公共子序列的長度，bij記錄 cij的值是由那一個子問題得到的。問

9、題的最優值，即X和Y的最長公共子序列的長度記錄于cmn中。void LcsLength(char x, char y, int m, int n, int c, int b) for(int i = 0; i <= m; i+)ci0 = 0; for(int j = 1; j <= n; j+)c0j = 0;for(i = 1; i<= m; i+)for(j = 1; j <= n; j+) if(xi-1 = yj-1) cij = ci-1j-1 + 1; bij = 1; else if(ci-1j >= cij-1) cij = ci-1j; bij

10、 = 2; else cij = cij-1; bij = 3; 在算法Lcslength中，由于每個數組單元的計算耗費O1,故算法耗時Omn。構造最長公共子序列：從bmn開始，依其值在數組b中搜索。當bij=1時，表示Xi和Yj的最長公共子序列是由Xi-1和Yj-1的最長公共子序列在尾部加上xi所得到的子序列；當bij=2時，表示Xi和Yj的最長公共子序列與Xi-1和Yj的最長公共子序列相同；bij=3時，表示Xi和Yj的最長公共子序列與Xi和Yj-1的最長公共子序列相同。void LCS(int b, char x, int i, int j) if(i = 0 | j = 0) retu

11、rn; if(bij = 1) LCS(b, x, i-1, j-1); printf("%c", xi-1); else if(bij = 2) LCS(b, x, i-1, j); else LCS(b, x, i, j-1);在算法LCS中，每一次遞歸調用使i或j減1，因此算法的計算時間為Om+n。三、 算法實現#include <stdio.h>#include <string.h>void LCSLength(char x20, char y20, int m, int n, int c2020, int b2020) int i,j; f

12、or(i = 0; i <= m; i+) ci0 = 0; for(j = 1; j <= n; j+) c0j = 0; for(i = 1; i<= m; i+) for(j = 1; j <= n; j+) if(xi-1 = yj-1) cij = ci-1j-1 + 1; bij = 1; else if(ci-1j >= cij-1) cij = ci-1j; bij = 2; else cij = cij-1; bij = 3; void LCS(int b2020, char x20, int i, int j) if(i = 0 | j = 0

13、) return; if(bij = 1) LCS(b, x, i-1, j-1); printf("%c", xi-1); else if(bij = 2) LCS(b, x, i-1, j); else LCS(b, x, i, j-1);int main() char x20,y20;printf("請輸入第一組序列： "); gets(x);printf("請輸入第二組序列： ");gets(y); int b2020,c2020; int m, n; m = strlen(x); n = strlen(y); LCSLength(x, y, m, n, c, b); LCS(b, x, m, n); printf("n長度為：%dn",cmn); return 0;四、 算法分析與改進在算法Lcslength中，由于每個數組單元的計算耗費O1,故算法耗時Omn。在算法LCS中，每一次遞歸調用使i或j減1，因此算法的計算時間為Om+n。算法可以進一步改進：在算法Lcslength和Lcs中，可進一步將數組b省去。對于數組cij，可以不借助于數組b而僅借助于c本身，在O1時間內確定cij的值是由ci-1j-1，ci-1j和cij-1中哪一個值所確定的。因此，可以寫一個類