動態(tài)規(guī)劃解最長公共子序列一、問題描述與分析經(jīng)常遇到一些復(fù)雜的問題，有時我們將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。由于分解到的子問題往往不是獨立的，用一個表來記錄所有已解決的子問題的答案，這樣就得到了原問題的解，這就是動態(tài)規(guī)劃法的基本思想。一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。給定兩個序列X和Y，當(dāng)另一序列Z即是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。在公共子序列中長度最長的則是最長公共子序列。窮舉搜索法是最容易想到的解題算法。對X的所有子序列，檢查它是否也是Y的子序列，從而確定它是否是X和Y的公共子序列。并且在檢查過程中記錄最長的公共子序列。X的所有子序列都檢查過后即可求出X和Y的最長公共子序列。事實上，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)的結(jié)構(gòu)性質(zhì)。二、算法設(shè)計最長公共子序列的結(jié)構(gòu)設(shè)序列和1）若，貝9，且2最長公共子序列的結(jié)構(gòu)設(shè)序列和1）若，貝9，且2）若且，則是3）若且，則是和其中，；證明：1）用反證法。若，則的最長公共子序列為，則是和的最長公共子序列；和的最長公共子序列；的最長公共子序列。;。是和的長度為k+1的公共子序列。這與是和的最長公共子序列矛盾。因此，必有。由此可知是和的長度為k-1的公共子序列。若和有長度大于k-1的公共子序列，，則將加在其尾部產(chǎn)生和的長度大于k的公共子序列。此為矛盾。故是和的最長公共子序列。2）由于，是和的公共子序列。若和有長度大于k的公共子序列，則也是和的長度大于k的公共子序列。這與是和的最長公共子序列矛盾。由此即知，是和的公共子序列。3）證明與（2）類似。子問題的遞歸結(jié)構(gòu)由最長公共子序列的問題的最優(yōu)子結(jié)構(gòu)可知，當(dāng)時，找出是和的最長公共子序列，然后在其尾部加上即可得和的最長公共子序列。當(dāng)時，必須解兩個子問題，即找出和的一個最長公共子序列及和的一個最長公共子序列。這兩個公共子序列中較長者即為和的最長公共子序列。由此遞歸結(jié)構(gòu)容易看到最長公共子序列問題具有子問題重疊性質(zhì)。首先建立子問題最優(yōu)值的遞歸關(guān)系。用記錄序列和的最長公共子序列的長度。其中;。當(dāng)i=0或j=0時，空序列是和的最長公共子序列，故此時系如下：。在其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)公共子序列，故此時系如下：。在其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)例子：求兩字符序列的最長公共字符子序列問題描述：字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個字符（可能一個也不去掉）后所形成的字符序列。令給定的字符序列，序列是的子序列，存在的一個嚴(yán)格遞增下標(biāo)序列，，，，使得對所有的，有。例如，BACDCA對所有的，有。例如，BACDCA”，=“ABDCA”是的一，，有以下性質(zhì):，得，，，的一個最長公共子序列；是1)，，有以下性質(zhì):，得，，，的一個最長公共子序列；是1)如果2)，如果和3)如果和,,,這樣，在找A和B的公共子序列時，，，和要解決兩個子問題，找出，，和找出，，，和如有的一個最長公共子序列；如果和則進(jìn)一步解決一個子問題，找，則的一個最長公共子序列的一個最長公共子序列，再取兩者中較長考慮最長公共子序列問題如何分解成子問題，設(shè)，，，，為它們的最長公共子序列。不難證明，則若和則若的一個最長公共子序列；則若，得，的一個最長公共子序列。者作為A和B的最長公共子序列。記錄與的LCS的長度，過哪一個子問題的值求得的，以決定搜索的方向。引進(jìn)一個二維數(shù)組記錄與的LCS的長度，過哪一個子問題的值求得的，以決定搜索的方向。引進(jìn)一個二維數(shù)組，用記錄是通之前，之前，，就可以計算出我們是自底向上進(jìn)行遞推計算，那么在計算均已計算出來。此時我們根據(jù)還是回溯輸出最長公共子序列過程jABDCAi0y0000B0、1\*<A011r、C0t4一+D0卜1TC0、1\1A01i則輸出結(jié)果為：BDCA由于每次調(diào)用至少向上或向左(或向上向左同時)移動一步，故最多調(diào)用(m+n)次就會遇到]=0或j=0的情況，此時開始返回。返回時與遞歸調(diào)用時方向相反，步數(shù)相同，故算法時間復(fù)雜度為。得出算法：計算最優(yōu)化：存儲與的最長公共子序列的長度，記錄的值是由那一個子問題得到的。問題的最優(yōu)值，即和的最長公共子序列的長度記錄于中。voidLcsLength(charx[],chary[],intm,intn,intc[][],intb[][]){for(inti=0;i<=m;i++)c[i][0]=0;for(intj=1;j<=n;j++)c[0][j]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i-1]==y[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}在算法Lcslength中，由于每個數(shù)組單元的計算耗費，故算法耗時。構(gòu)造最長公共子序列:從開始，依其值在數(shù)組b中搜索。當(dāng)=1時，表示和的最長公共子序列是由和的最長公共子序列在尾部加上所得到的子序列；當(dāng)=2時，表示和的最長公共子序列與和的最長公共子序列相同；=3時，表示和的最長公共子序列與和的最長公共子序列相同。voidLCS(intb[][],charx[],inti,intj){if(i==0||j==0)return;if(b[i][j]==1){LCS(b,x,i-1,j-1);printf("%c",x[i-1]);}elseif(b[i][j]==2)LCS(b,x,i-1,j);elseLCS(b,x,i,j-1);}在算法LCS中，每一次遞歸調(diào)用使i或j減1,因此算法的計算時間為。三、算法實現(xiàn)#include<stdio.h>#include<string.h>voidLCSLength(charx[20],chary[20],intm,intn,intc[20][20],intb[20][20])(inti,j;for(i=0;i<=m;i++)c[i][0]=0;for(j=1;j<=n;j++)c[0][j]=0;for(i=1;i<=m;i++)?[ozlEozlalozKozlqwif(A)s)a3?(":YWM..)Wu!jdf(x)s)3S?(":YWM..)Wu!jdJtOZlAlOZlxJeqo)Ouiew)ui'!'x句STIaspWT!'x句ss(Z==[n[!]qU!asp(l【B]x/1p%ll)WU!JdWT!'x句STI}(T==[f][!]qU!fujn)sj(。==1110==山！}((iui1iui*[0Z]xjeqoWIEOZlqluijsoipiOA堆=皿!】q壯?(H巾=[0[>]9}asp{那=[n[>]q傾?巾=[n[>]9)([1-(][!]3=<[[][1-!]3)1!9S|0(n=[HEilq紅+[T-n[T->]3=[0[!]9}([T-[]A==[T-!]xU!}(++[如=>"i=[)JO|intm,n;m=strlen(x);n=strlen(y);LCSLength(x,y,m,n,c,b);LCS(b,x,m,n);printf("\n長度為：％d\n",c[m][n]);return0;}四、算法分析與改進(jìn)在算法Lcslength中，由于每個數(shù)組單元的計算耗費，故算法耗時在算法LCS中，每一次遞歸調(diào)用使i或j減1，因此算法的計算時間為算法可以進(jìn)一步改進(jìn)：在算法Lcslength和Lcs中，可進(jìn)一步將數(shù)組b省去。對于數(shù)組，可以不借助于數(shù)組b而僅借助于c本身，在時間內(nèi)確定的值是由，和中哪一個值所確定的。因此，可以寫一個類似于Lcs的算法，不用數(shù)組b而在時間內(nèi)構(gòu)造最長公共子序列