數(shù)據(jù)結(jié)構(gòu)與算法實踐指導 課件 11-動態(tài)規(guī)劃

第11章

動態(tài)規(guī)劃11.1知識簡介

動態(tài)規(guī)劃方法通常用來求解最優(yōu)化問題，這類問題可以有很多可行解，每個解都有一個值，需要找到具有最優(yōu)值（最小值或者最大值）的解。11.1.1動態(tài)規(guī)劃

適合應用動態(tài)規(guī)劃方法求解的最優(yōu)化問題應該具備的兩個要素：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊。1）最優(yōu)子結(jié)構(gòu)性質(zhì)

如果一個問題的最優(yōu)解包含其子問題的最優(yōu)解，則稱這個問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。因此，判斷某個問題是否適合用動態(tài)規(guī)劃算法，需要判斷該問題是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)。11.1知識簡介2）子問題的重疊性11.1.1動態(tài)規(guī)劃

適合用動態(tài)規(guī)劃方法求解的問題應該具備的第二個基本要素是子問題的重疊性。在用遞歸算法自頂向下求解問題時，某些子問題被反復計算，則稱該問題具有子問題重疊的性質(zhì)。為了避免子問題重復計算，動態(tài)規(guī)劃方法求解問題時對每個子問題求解一次，將解存入一個表格中，當再次需要這個子問題時直接查表。11.1知識簡介11.1.2求解問題的步驟

用動態(tài)規(guī)劃求解問題的一般步驟：1）找出最優(yōu)解的性質(zhì)，刻畫其結(jié)構(gòu)特征；2）遞歸定義最優(yōu)解的值；3）采用自底向上的方法計算最優(yōu)解的值；4）通過最優(yōu)值求解過程構(gòu)造一個最優(yōu)解。11.2實驗目的

通過對0-1背包問題、最大子數(shù)組問題和最長公共子序列問題的設計與實現(xiàn)，讓學生學會分析問題從而確定問題是否可以適用動態(tài)規(guī)劃，并能將復雜問題分解為一系列相互關(guān)聯(lián)且具有最優(yōu)子結(jié)構(gòu)的子問題。通過問題實例的編程實現(xiàn)，加深對理論知識的理解，提升自身的算法設計與分析水平，同時鍛煉編碼實現(xiàn)和調(diào)試技能。11.3實驗范例

給定n種物品和一個背包，第i種物品重量為wi，其價值為vi，其中i=1、2、3、…、n，背包的容量為c，問如何選擇放入背包的物品，使得放入背包的物品的總價值最大，重量w、背包容量c均為正整數(shù)。11.3.10-1背包問題1、問題描述

11.3實驗范例0-1背包問題是一個特殊的整數(shù)規(guī)劃問題：11.3.10-1背包問題1、問題描述

11.3實驗范例11.3.10-1背包問題1、問題描述i12345wi103454vi2429109

如有5個物品，每個物品的重量和價格如下表所示，背包容量為13。該問題的最優(yōu)值為28，分別放入物品3、物品4和物品5。11.3實驗范例11.3.10-1背包問題2、問題分析

先分析問題是否具備利用動態(tài)規(guī)劃求解的兩個基本要素：最優(yōu)子結(jié)構(gòu)和子問題重疊。1）最優(yōu)子結(jié)構(gòu)性質(zhì)

11.3實驗范例11.3.10-1背包問題2、問題分析

11.3實驗范例11.3.10-1背包問題2、問題分析

由此可見，該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。即大問題的最優(yōu)解包含子問題的最優(yōu)解。

基于這個性質(zhì)可以得到一個遞歸關(guān)系，由這個遞歸關(guān)系，我們能想到的最簡單的方法就是遞歸方法。11.3實驗范例11.3.10-1背包問題2、問題分析

其遞歸定義如下。

11.3實驗范例11.3.10-1背包問題2、問題分析

用遞歸函數(shù)KnapsackRA(w[],v[],i,j)求將i個物品放入容量為j的背包中的物品的最大價值，其中數(shù)組w存放每個物品的重量，數(shù)組v存放每個物品的價值，偽代碼描述如下：intKnapsackRA(intw[],intv[],inti,intj){if(i<=0||j<=0)return0;//只有一個物品

else{if(w[i]>j)//第i個物品裝不下returnKnapsackRA(w,v,i-1,j);elsereturnmax(KnapsackRA(w,v,i-1,j),KnapsackRA(w,v,i-1,j-w[i])+v[i]);}}11.3實驗范例11.3.10-1背包問題2、問題分析

假設每個物品的重量都為w，求解過程的遞歸樹如下圖所示。

其中：1表示選擇第i個物品，0表示不選擇第i個物品。11.3實驗范例11.3.10-1背包問題2、問題分析

用遞歸方法求0-1背包問題的時間復雜度是O(2n)。從遞歸樹可以看出，用遞歸求解過程中有很多子問題重復求解，從而導致算法的時間復雜度高。11.3實驗范例11.3.10-1背包問題2、問題分析2）子問題重疊

在用遞歸方法求解問題時有很多子問題重復求解，這就是子問題重疊性質(zhì)。為了避免相同子問題重復求解，采用空間換時間策略，記錄每個子問題首次計算結(jié)果，后面再用時就直接取值，這樣每個子問題只計算一次。在遞歸方法基礎上用表格存儲子問題解的方法稱為帶備忘錄的遞歸方法。遞歸方法的計算順序是先自頂向下遞歸直到遞歸出口（最原始的子問題），然后通過自底向上的遞推過程計算每步的解，最后得到原問題的解。11.3實驗范例11.3.10-1背包問題2、問題分析2）子問題重疊

遞歸過程如下圖所示：

為了進一步優(yōu)化求解過程，可以不用遞歸，即去掉自頂向下的遞歸過程，直接自底向上計算問題的解，這個就是動態(tài)規(guī)劃的方法。11.3實驗范例11.3.10-1背包問題2、問題分析3）采用動態(tài)規(guī)劃解題步驟

（1）問題結(jié)構(gòu)分析

用一個二維數(shù)組存儲每個子問題的最優(yōu)解，用P[i,j]表示前i個物品可選，背包容量為j時的最優(yōu)解。原問題的最優(yōu)解則為P[n,c],表示有n個物品，背包容量為c時的最優(yōu)解。

11.3實驗范例11.3.10-1背包問題2、問題分析3）采用動態(tài)規(guī)劃解題步驟

（3）采用自底向上的方法計算最優(yōu)解的值

根據(jù)遞推關(guān)系，確定子問題的計算順序。遞推關(guān)系的初始化條件為：

①當背包容量j為0時，P[i,0]=0；

②當沒有物品，即i為0時，P[0,j]=0。

即二維數(shù)組中的第一行和第一列都為0。11.3實驗范例11.3.10-1背包問題2、問題分析

通過遞推關(guān)系可知，P[i,j]的值依賴于子問題P[i-1,j-wi]的值和子問題P[i-1,j]的值，在計算過程中需把P[i-1,j-wi]和P[i-1,j]計算出來，才能計算P[i,j]的值。3）采用動態(tài)規(guī)劃解題步驟11.3實驗范例11.3.10-1背包問題2、問題分析

P[i-1,j-wi]和P[i-1,j]都在P[i,j]的上一行，所以需從第一行開始從上往下順序計算。同時這兩個值一個在左側(cè)一個在上面，所以每行需從第一列開始從左往右順序計算。如有n個物品，背包容量為c的問題，P的計算順序如下表所示。3）采用動態(tài)規(guī)劃解題步驟11.3實驗范例11.3.10-1背包問題2、問題分析

如有5個物品，每個物品的重量w={10，3，4，5，4}，每個物品的價格v={24，2，9，10，9}，背包容量c為13。

當i=0或者j=0時，P[i,j]值為0。3）采用動態(tài)規(guī)劃解題步驟11.3實驗范例11.3.10-1背包問題2、問題分析

當i=1時，放第一個物品，第一個物品重量為10，價格為24。當j<10時，該物品不能裝入背包，所以P[1,j]的值都為0。當j≥10時，該物品可以放入背包，則背包中物品價值為第一個物品的價值24，則P[1,10]到P[1,13]的值為24。P中第1行的各個元素值如下表所示。3）采用動態(tài)規(guī)劃解題步驟11.3實驗范例11.3.10-1背包問題2、問題分析

當i=2時放第二個物品，第二個物品重量為3，價值為2。

當j<3時，該物品都不能放入背包，P[2,j]等于P[1,j]，都為0。

當j=3時，該物品可以放入背包，此時放入該物品的價值為P[1,3-3]+2=0+2=2，不放入該物品的價值為P[1,3]=0，選大者，所以P[2,3]=2。直到P[2,9]，值都為2。

當j≥10且j≤12時，該物品也可以放背包。將該物品放入背包后，背包中物品的價值為P[1,10-3]+2=0+2=2。如果不放入背包，背包中物品的最大價值為P[1,10]=24。選兩者中的大者，所以P[2,10]=max{2，24}=24。同理P[2,11]和P[2,12]也等于24。3）采用動態(tài)規(guī)劃解題步驟11.3實驗范例11.3.10-1背包問題2、問題分析

當j=13時，該物品也可以放入背包，如果將該物品放入背包，則背包中物品的最大值為P[1,13-3]+2=24+2=26。如果不放入背包，背包中物品的最大價值為P[1,10]=24。選兩者中的大者，所以P[2,13]=max{26，24}=26。P中第2行的各個元素值如下表所示。3）采用動態(tài)規(guī)劃解題步驟11.3實驗范例11.3.10-1背包問題2、問題分析

后面3行同樣的方法計算，最后計算的結(jié)果如下表。

該問題的最優(yōu)值P[5,13]=28。3）采用動態(tài)規(guī)劃解題步驟11.3實驗范例11.3.10-1背包問題2、問題分析

（4）通過最優(yōu)值求解過程構(gòu)造一個最優(yōu)解。3）采用動態(tài)規(guī)劃解題步驟

11.3實驗范例11.3.10-1背包問題2、問題分析

（4）通過最優(yōu)值求解過程構(gòu)造一個最優(yōu)解。3）采用動態(tài)規(guī)劃解題步驟

再根據(jù)Rec數(shù)組的值，從Rec[n,C]開始，倒序判斷是否選擇了某個物品，從而確定選擇了哪些物品裝入背包。

如上述案例，有5個物品，每個物品的重量w={10，3，4，5，4}，每個物品的價格v={24，2，9，10，9}，背包容量為13。在計算P數(shù)組的同時對Rec數(shù)組賦值。11.3實驗范例11.3.10-1背包問題2、問題分析

（4）通過最優(yōu)值求解過程構(gòu)造一個最優(yōu)解。2）采用動態(tài)規(guī)劃解題步驟

當i=1時，判斷是否裝入物品1，當背包容量小于10時，物品1不能裝入背包，所以Rec數(shù)組中第1行，0到9列的值為0。當背包容量大于等于10，可以裝入物品1，所以此行后面的值為1。

當i=2時，判斷物品2是否裝入背包，當j=3時，P[2,3]=max{P[1,3-3]+2=0+2=2，P[1,3]=0}=2，是選擇裝入物品2，所以Rec[2,3]賦值1。當j=10時，P[2,10]=max{P[1,10-3]+2=0+2=2，P[1,10]=24}=24，不裝入物品2，所以Rec[2,3]賦值0。11.3實驗范例11.3.10-1背包問題2、問題分析

（4）通過最優(yōu)值求解過程構(gòu)造一個最優(yōu)解。2）采用動態(tài)規(guī)劃解題步驟

最后Rec數(shù)組的值如下表所示。11.3實驗范例11.3.10-1背包問題2、問題分析

（4）通過最優(yōu)值求解過程構(gòu)造一個最優(yōu)解。2）采用動態(tài)規(guī)劃解題步驟

從Rec[5,13]開始，倒序判斷選擇了哪些物品裝入背包。Rec[5,13]值為1，說明選擇物品5。背包容量13減去物品5的重量4，等于9，接著找Rec[4,9]。Rec[4,9]的值為1，說明選擇物品4。背包容量9減去物品4的重量5，等于4，接著找Rec[3,4]。Rec[3,4]等于1，說明選擇物品3。背包容量4減去物品3的重量4，等于0。此時背包容量為0，說明前面的物品都不選擇裝入背包，即物品2和物品1都不選。因此，該問題的解用向量表示為（0,0,1,1,1）。11.3實驗范例11.3.10-1背包問題2、問題分析

（4）通過最優(yōu)值求解過程構(gòu)造一個最優(yōu)解。2）采用動態(tài)規(guī)劃解題步驟

根據(jù)Rec數(shù)組值推出最優(yōu)解的過程如下表所示。11.3實驗范例3、算法描述11.3.10-1背包問題n個商品，各商品的價值v[],各商品的重量w[]，背包容量c，返回最大價值，算法的偽代碼描述如下：intKnapsack(intv[],intw[],intn,intc,int**P,int**Rec){//將二維數(shù)組P[0..n,0..c]和Rec[0..n,0..c]賦值為0//P[i][j]表示放i個物品放入容量為j背包的中時物品的最大價值;//Rec[i][j]取值0或者1,表示將i個物品到容量為j的背包中時，第i個物品選還是不選，1表示選，0表示不選for(i=0;i<=c;i++){P[0][i]=0;Rec[0][i]=0;

}11.3實驗范例3、算法描述11.3.10-1背包問題n個商品，各商品的價值v[],各商品的重量w[]，背包容量c，返回最大價值，算法的偽代碼描述如下：for(i=0;i<=n;i++){P[i][0]=0;

Rec[i][0]=0;}//計算P數(shù)組中的值for(i=1;i<=n;i++){for(j=1;j<=c;j++){//第i個物品能放入背包，且放入之后的價格更大if((w[i]<=j)&&v[i]+P[i-1][j-w[i]]>P[i-1][j]){

P[i][j]=v[i]+P[i-1][j-w[i]];//將p數(shù)組中的值替換成更優(yōu)的值Rec[i][j]=1;//并將記錄第i個物品被選定

}11.3實驗范例3、算法描述11.3.10-1背包問題n個商品，各商品的價值v[],各商品的重量w[]，背包容量c，返回最大價值，算法的偽代碼描述如下：else{//第i個物品不能裝入背包P[i][j]=P[i-1][j];Rec[i][j]=0;}}}returnP[n][c];}11.3實驗范例3、算法描述11.3.10-1背包問題

接著定義函數(shù)traceBack，根據(jù)Rec數(shù)組的值得出哪些物品裝入背包，用selected數(shù)組存儲各物品是否被選定。voidtraceBack(int**Rec,int*w,intn,intc,int*selected){t=c;//從Rec[n][c]開始判斷for(i=n;i>0;i--){if(Rec[i][t]==1){selected[i]=1;

t=t-w[i];}

else{selected[i]=0;}}}11.3實驗范例3、算法描述11.3.10-1背包問題

接著定義主函數(shù)。intmain(){inti;intgNum,capacity;//物品個數(shù)和背包容量int*w;//存放各物品的重量int*v;//存放各物品的價格//輸入物品個數(shù)printf("輸入物品個數(shù)和背包容量：");scanf("%d%d",&gNum,&capacity);w=(int*)malloc((gNum+1)*sizeof(int));v=(int*)malloc((gNum+1)*sizeof(int));printf("輸入各物品的重量和價格：");11.3實驗范例3、算法描述11.3.10-1背包問題

接著定義主函數(shù)。for(i=1;i<=gNum;i++){scanf("%d%d",&w[i],&v[i]);}int**P,**Rec;//定義二維數(shù)組P和Rec//數(shù)組P[gNum+1][capacity+1],P[i][j]表示放i個物品放入容量為j背包的中時物品的最大價值;//Rec[gNum+1][capacity+1],Rec[i][j]取值0或者1,表示將i個物品到容量為j的背包中時，第i個物品選還是不選，選用1表示，不選用0表示;P=(int**)malloc(sizeof(int*)*(gNum+1));for(i=0;i<gNum+1;i++)P[i]=(int*)malloc(sizeof(int)*(capacity+1));Rec=(int**)malloc(sizeof(int*)*(gNum+1));11.3實驗范例3、算法描述11.3.10-1背包問題

接著定義主函數(shù)。for(i=0;i<gNum+1;i++)

Rec[i]=(int*)malloc(sizeof(int)*(capacity+1));int*selected;//selected數(shù)組用來存儲哪些物品被選定，選定為1，未選定為0selected=(int*)malloc(sizeof(int)*(gNum+1));intmaxV=Knapsack(v,w,gNum,capacity,P,Rec);printf("MaxV=%d\n",maxV);traceBack(Rec,w,gNum,capacity,selected);11.3實驗范例3、算法描述11.3.10-1背包問題

接著定義主函數(shù)。//輸出數(shù)組selected中的值printf("所選物品：(");for(i=1;i<gNum;i++)printf("%2d,",selected[i]);printf("%2d)\n",selected[i]);return0;}11.3實驗范例4、算法分析11.3.10-1背包問題

算法的時間復雜度為O(nc)，空間復雜度為O(nc)。采用此方法求0-1背包問題要求物品重量和背包容量必須是整數(shù)。11.4實驗任務完成下列任務，并分析各算法的時間復雜度。任務1：最大子數(shù)組問題（MaxContinuousSubarray）。

求S(l,r)的最大值，記為Smax。

11.4實驗任務完成下列任務，并分析各算法的時間復雜度。任務1：最大子數(shù)組問題（MaxContinuousSubarray）。

如有數(shù)組X如下：

子數(shù)組X[3..7]，其和為：3+5-4+3+2=9。

子數(shù)組X[1..10]，其和為：-1-3+3+5-4+3+2-2+3+6=12。

子數(shù)組X[3..10]，其和為：3+5-4+3+2-2+3+6=16。

此數(shù)組中，最大子數(shù)組值為X[3..10]=16。11.4實驗任務完成下列任務，并分析各算法的時間復雜度。任務2：最長公共子序列。

給定一個序列X=<x1,x2,x3,x4,…,xn>，另一個序列Z=<z1,z2,z3,z4,…,zk>，若存在一個嚴格遞增的x的下標序列<i1,i2,i3,…,ik>對所有的1,2,3,4,…,k都滿足x(ik)=zk，則稱Z是X的子序列。也就是將序列X中零個或多個元素去掉后所得的序列。例如序列X=<A,B,C,B,D,A,B>，則序列<A,B,C,B,D,A,B>、<A,B,C,B>、<A,C,B,B>都是序列X的子序列。如果一個序列Z既是X的子序列又是Y的子序列時，則稱Z是序列X和序列Y的公共子序列。如給定序列Y=<B,D,C,A,B,A>，則序列<C,A>、<A,B,A>、<B,D,B>、<B,C,A,B>都是X和Y的公共子序列。給定序列X和序列Y，求X和Y的最長公共子序列。11.4實驗任務完成下列任務，并分析各算法的時間復雜度。任務2：最長公共子序列。

該問題的形式化描述為：給定序列X=<x1,x2,x3,…,xn>和序列Y=<y1,y2,y3,…,ym>，求解一個公共子序列Z=<z1,z2,z3,…,zt>，令max|Z|，滿足：

11.5任務提示1、問題分析任務1提示

計算每個子數(shù)組和需要O(n)，所以該方法的時間復雜度為O(n3)。

由于在計算過程中，很多計算是重復的，例如在計算X[2..8]和計算X[2..9]時重復計算了X[2..8]?？梢詫⑿U力枚舉進行優(yōu)化，在計算X[2..9]時，用X[2..8]+X[9]。優(yōu)化之后的時間復雜度為O(n2)。

11.5任務提示1、問題分析任務1提示

該問題能否用動態(tài)規(guī)劃策略來解決呢？如果能時間復雜度是多少？

從蠻力枚舉法分析可知，該問題具有子問題重疊性質(zhì)，同時該問題也具有最優(yōu)子結(jié)構(gòu)性質(zhì)。11.5任務提示1、問題分析任務1提示

用D[j]表示子數(shù)組X[1..j]中最大值子段和，即：

某個數(shù)加上一個正數(shù)，其結(jié)果肯定大于該數(shù)，而加上一個負數(shù)肯定小于該數(shù)。11.5任務提示1、問題分析任務1提示

例如數(shù)組X有6個元素，各元素值分布如下：D[1]=1：只有一個數(shù)，就是最大值；D[2]=4：D[1]>0，所以D[2]=D[1]+X[2]；D[3]=-1：D[2]>0，所以D[3]=D[2]+X[3]；D[4]=3：D[3]<0，所以D[4]=X[4]；D[5]=5：D[4]>0，所以D[5]=D[4]+X[5]；D[6]=9：D[5]>0，所以D[6]=D[5]+X[6]。11.5任務提示1、問題分析任務1提示

最后計算出D值分布如下：D[1]到D[6]中最大值為9，所以該問題的最大值為9。11.5任務提示1、問題分析任務1提示

當D[j-1]>0，D[j]=D[j-1]+X[j]，當D[j-1]<0時，D[j]=X[j]。即：

由此看出該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。11.5任務提示1、問題分析任務1提示

如何得到最優(yōu)解，也就是子數(shù)組的起始位置呢？

由遞推公式可知，D[j]表示X數(shù)組中前j個元素的最大的子數(shù)組的值，最后一個元素就是X[j]。當D[j-1]>0時，D[j]的值為D[j-1]+X[j]，則計算D[j]的起始元素和計算D[j-1]的起始元素相同。當D[j-1]≤0時，D[j]的值為X[j]，則計算D[j]的起始元素為j。假設用數(shù)組Rec[1..n]記錄計算D[1..n]時元素的起始位置，則有：

11.5任務提示1、問題分析任務1提示

如上例中的Rec[1...6]值的計算過程如下。

D數(shù)組中D[6]的值最大，對應位置Rec[6]的值為4，即數(shù)組X中X[4]到X[6]的和最大。11.5任務提示2、算法描述任務1提示求最大子數(shù)組和的偽代碼描述如下：intMaxSubArray_DynamicProgramming(int*X,intn,int&besti,int&bestj){//數(shù)組D和數(shù)組Rec，D[i]表示X[1..i]的最大子數(shù)組和，Rec[i]表示取到D[i]時子數(shù)組的起始位置D[1]=X[1];

Rec[1]=1;//給D[1]和Rec[1]賦初值for(i=2;i<=n;i++){

if(D[i-1]>0){D[i]=D[i-1]+X[i];Rec[i]=Rec[i-1];

}

else{D[i]=X[i];Rec[i]=i;

}

}11.5任務提示2、算法描述任務1提示求最大子數(shù)組和的偽代碼描述如下：//找到D數(shù)組中的最大值，以及求得該值的子數(shù)組起止位置maxSub=D[1];besti=1;bestj=1;for(i=2;i<=n;i++){

if(D[i]>maxSub){maxSub=D[i];besti=Rec[i];bestj=i;

}}returnmaxSub;//返回最大和}11.5任務提示任務1提示3、算法分析

此問題可以用蠻力枚舉法來解決，蠻力枚舉法的時間復雜度O(n3)。對蠻力枚舉進行優(yōu)化，減少重復計算，優(yōu)化后的時間復雜度為O(n2)。用動態(tài)規(guī)劃策略的時間復雜度為O(n)。只要對數(shù)組掃描一遍。11.5任務提示1、問題分析任務2提示

設序列Xn=<x1,x2,x3,…,xn>和序列Ym=<y1,y2,y3,…,ym>的最長公共子序列Zk=<z1,z2,z3,…,zk>，則：

①如果xn=ym，則zk=xn=ym，則Zk-1就是Xn-1和Ym-1的最長公共子序列。

②如果xn≠ym，且zk≠xn，則Z就是Xn-1和Ym的最長公共子序列。

③如果xn≠ym，則zk≠ym，則Z就是Xn和Ym-1的最長公共子序列。

其中，Xn-1=<x1,x2,x3,…,xn-1>和序列Ym-1=<y1,y2,y3,…,ym-1>的最長公共子序列Zk-1=<z1,z2,z3,…,zk-1>。

由此可見，兩個序列的最長公共子序列包含了這兩個序列的前綴的最長公共子序列，此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。11.5任務提示1、問題分析任務2提示

當要找出Xn=<x1,x2,x3,…,xn>和序列Ym=<y1,y2,y3,…,ym>的最長公共子序列，可以按照以下方式遞歸求解：

①當xn≠ym時，找出Xn和Ym-1的最長公共子序列以及Xn-1和Ym的最長公共子序列，這兩個公共子序列中較長的即為Xn和Ym的最長公共子序列。

②當xn=ym時，找出Xn-1和Ym-1的最長公共子序列Zk-1，在Zk-1的后面加上xn即可得到Xn和Ym的最長公共子序列。11.5任務提示1、問題分析任務2提示

下面舉例來分析這兩種情況。

情況1：給定序列X7=<A,B,C,B,D,A,B>和序列Y6=<B,D,C,A,B,A>，求兩者的公共子序列。

此時x7≠y6，則x7和y6不可能同時出現(xiàn)在最長公共子序列中，則有兩種可能：第一種可能，x7在最長公共子序列中，y6不在最長公共子序列中；第二種可能，x7不在最長公共子序列中，y6在最長公共子序列中。11.5任務提示1、問題分析任務2提示

第一種可能就變成在序列X7=<A,B,C,B,D,A,B>和序列Y5

=<B,D,C,A,B>找最長公共子序列。

第二種可能就變成在序列X6=<A,B,C,B,D,A,B>和序列Y6

=<B,D,C,A,B,A>找最長公共子序列。

而序列X7=<A,B,C,B,D,A,B>和序列Y6=<B,D,C,A,B,A>的最長公共子序列應該是這兩者中長的那一個。11.5任務提示1、問題分析任務2提示

情況2：給定序列X7=<A,B,C,B,D,A,B>和序列Y6=<B,D,C,A,B,B>，求兩者的公共子序列。

此時x7=y6，則x7和y6可能同時出現(xiàn)在最長公共子序列中，序列X和序列Y的最長公共子序列應該是X去掉x7的子序列和Y去掉y6的子序列的最長公共子序列再加上B這個元素。11.5任務提示1、問題分析任務2提示

根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)，建立子問題最優(yōu)值的遞歸關(guān)系。假設用c[i][j]表示序列Xi=<x1,x2,x3,…,xi>和序列Yj=<y1,y2,y3,…,yj>的最長公共子序列的長度。則有如下遞歸關(guān)系：

在計算Xn和Ym的最長公共子序列時，可能需要計算Xn和Ym-1的最長公共子序列以及Xn-1和Ym的最長公共子序列，而這兩個公共子序列都包含一個公共子問題，即計算Xn-1和Ym-1的最長公共子序列。由此可見，該問題具有子問題重疊的性質(zhì)。11.5任務提示1、問題分析任務2提示

由遞歸關(guān)系可以看出，要計算c[i][j]的值，先要計算c[i-1][j-1]、c[i][j-1]和c[i-1][j]的值，所以數(shù)組c的計算順序是自底向上的過程。如下表所示，從第1行開始往后計算，每行從左往右計算。最后計算的c[n][m]即為問題所需求得最長公共子序列的長度。11.5任務提示1、問題分析任務2提示

例：給定序列X7=<A,B,C,B,D,A,B>和序列Y6=<B,D,C,A,B,A>，求兩者的公共子序列長度的過程如下。

當i=0或者j=0時，c[i][j]的值為0。11.5任務提示1、問題分析任務2提示

例：給定序列X7=<A,B,C,B,D,A,B>和序列Y6=<B,D,C,A,B,A>，求兩者的公共子序列長度的過程如下。先計算第1行，即c[1][j]，j從1到6：c[1][1]：x1≠y1，c[1][1]=max{c[0][1],c[1][0]}=0；c[1][2]：x1≠y2，c[1][2]=max{c[0][2],c[1][1]}=0；c[1][3]：x1≠y3，c[1][3]=max{c[0][3],c[1][2]}=0；c[1][4]：x1=y4，c[1][4]=c[0][3]+1=1；c[1][5]：x1≠y5，c[1][5]=max{c[0][5],c[1][4]}=1；c[1][6]：x1=y6，c[1][6]=c[0][5]+1=1。11.5任務提示1、問題分析任務2提示

例：給定序列X7=<A,B,C,B,D,A,B>和序列Y6=<B,D,C,A,B,A>，求兩者的公共子序列長度的過程如下。計算第1行的結(jié)果如下：11.5任務提示1、問題分析任務2提示

例：給定序列X7=<A,B,C,B,D,A,B>和序列Y6=<B,D,C,A,B,A>，求兩者的公共子序列長度的過程如下。接著計算第2行：c[2][1]：x2=y1，c[2][1]=c[1][0]+1=1；c[2][2]：x2≠y2，c[2][2]=max{c[1][2],c[2][1]}=1；c[2][3]：x2≠y3，c[2][3]=max{c[1][3],c[2][2]}=1；c[2][4]：x2≠y4，c[2][4]=max{c[1][4],c[2][3]}=1；c[2][5]：x2=y5，c[2][5]=c[1][4]+1=2；c[2][6]：x2≠y6，c[2][6]=max{c[1][6],c[2][5]}=2。11.5任務提示1、問題分析任務2提示

例：給定序列X7=<A,B,C,B,D,A,B>和序列Y6=<B,D,C,A,B,A>，求兩者的公共子序列長度的過程如下。計算第2行的結(jié)果如下：11.5任務提示1、問題分析任務2提示

例：給定序列X7=<A,B,C,B,D,A,B>和序列Y6=<B,D,C,A,B,A>，求兩者的公共子序列長度的過程如下。后面5行用同樣的方法求出，最后c數(shù)組中的元素如下所示：因此該問題的最長公共子序列的長度為4。11.5任務提示1、問題分析任務2提示

如何求出最長公共子序列呢？

由遞推公式可知：

當xi=yj時，c[i][j]等于c[i-1][j-1]加1，則序列Xi和Yj的最長公共子序列就是序列Xi-1和Yj-1的最長公共子序列加上xi或者yj；

當xi≠yj

時，c[i][j]等于c[i][j-1]和c[i-1][j]大者，當c[i][j]等于c[i][j-1]時，則序列Xi和Yj的最長公共子序列就是序列Xi和Yj-1的最長公共子序列；當c[i][j]等于c[i-1][j]時，則序列Xi和Yj的最長公共子序列就是序列Xi-1和Yj的最長公共子序列。11.5任務提示1、問題分析任務2提示

用Rec數(shù)組記錄每次計算c[i][j]時是由哪個值計算而來，用O表示c[i][j]是由c[i-1][j-1]計算而來，用U表示c[i][j]是由c[i-1][j]計算而來，用L表示c[i][j]是由c[i][j-1]計算而來。則有：

11.5任務提示1、問題分析任務2提示

上例的Rec數(shù)組各元素的值如下表所示：11.5任務提示1、問題分析任務2提示

接著根據(jù)Rec數(shù)組的元素追蹤出最長公共子序列。從Rec[n][m]開始往前追蹤，當Rec[i][j]等于‘U’時，往上走找Rec[i-1][j]；當Rec[i][j]等于‘L’時，往上走找Rec[i][j-1]；當Rec[i][j]等于‘O’時，往左上走找Rec[i-1][j-1]，同時找到了最長公共子序列中的一個元素，該元素為xi或者yj（這兩個元素是相等的）。11.5任務提示1、問題分析任務2提示

如根據(jù)上例中的Rec值求解最長公共子序列的過程如下表所示。得到的元素依次為x6、x4、x3、x2，逆過來從而得到X和Y的最長公共子序列為“BCBA”。11.5任務提示2、算法描述任務2提示

求長度為n的序列X和長度為m的序列Y的最長公共子序列，返回序列的長度，用longestCS