計算理論與算法分析設(shè)計：CH3 動態(tài)規(guī)劃法

動態(tài)規(guī)劃法

2022/11/62of158方法概述:發(fā)展及研究內(nèi)容動態(tài)規(guī)劃(dynamicprogramming)是運籌學(xué)的一個分支，20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(multistepdecisionprocess)的優(yōu)化問題時，提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——動態(tài)規(guī)劃。動態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、資源分配、設(shè)備更新等問題，用動態(tài)規(guī)劃比用其它方法求解更為方便。2022/11/63of158方法概述:基本思想動態(tài)規(guī)劃的思想實質(zhì)是分治思想和解決冗余。與分治法類似的是，將原問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，經(jīng)分解的子問題往往不是互相獨立的。若用分治法來解，有些共同部分（子問題或子子問題）被重復(fù)計算了很多次。如果能夠保存已解決的子問題的答案，在需要時再查找，這樣就可以避免重復(fù)計算、節(jié)省時間。動態(tài)規(guī)劃法用一個表來記錄所有已解的子問題的答案。這就是動態(tài)規(guī)劃法的基本思路。具體的動態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表方式。2022/11/64of158方法概述:求解步驟1、找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；2、遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；3、以自底向上的方式計算出最優(yōu)值；4、根據(jù)計算最優(yōu)值時記錄的信息，構(gòu)造最優(yōu)解。注：－步驟1-3是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟4可以省略；－若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟4，步驟3中記錄的信息是構(gòu)造最優(yōu)解的基礎(chǔ)2022/11/65of158方法概述:適用條件

動態(tài)規(guī)劃法的有效性依賴于問題本身所具有的兩個重要性質(zhì)最優(yōu)子結(jié)構(gòu)：當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。2022/11/66of158方法概述:最優(yōu)性原理及舉例Bellman給出這個原理作為動態(tài)規(guī)劃的適用條件，后來Morin在1982年證明了這只是一個充分條件而非必要條件。Bellman的原定義如下：

Anoptimalpolicyhasthepropertythatwhatevertheinitialstateandinitialdecisionare,thenremainingdecisionsmustconstituteanoptimalpolicywithregardtothestateresultingfromfirstdecision.

最優(yōu)性原理又稱為最優(yōu)子結(jié)構(gòu)性質(zhì)：

如果有一決策序列包含有非最優(yōu)的決策子序列，則該決策序列一定不是最優(yōu)的。即一個最優(yōu)策略的子策略總是最優(yōu)的。2022/11/67of158例1：多段圖的最短路問題多段圖：設(shè)G=<V,E>是一個有向連通圖，

其中|V|=n,|E|=m,V有劃分{V1,V2,···,Vk}，

這里V1={s},s稱為源點，Vk={t},t稱為

終點，其中k≥2。對于每條有向邊

<u,v>∈E都存在Vi

∈V，使得u∈Vi

和v∈Vi+1,其中1≤i<k且每條邊<u,v>均

附有代價C(u,v)，則稱G是一個k段圖。2022/11/68of158123456789101112s97324212711118654356425V1V2V3V4V5t2022/11/69of158最短路：從源點s到終點t的整條路上的代價之和為最小。每個子集Vi構(gòu)成圖中的一段。由于E的約束，每條從s到t的路徑都是從第一段開始，然后順次經(jīng)過第2段，第3段，···，最后在第k段終止。對于每條從s到t的路徑，可以把它看成在k-2個階段中做出的某個決策序列的相應(yīng)結(jié)果。2022/11/610of158假設(shè)s,v2,v3,···,vk-1,t是一條從s到t的最短路徑，還假定從源點s（初始狀態(tài)）開始，已做出了到結(jié)點v2的決策（初始決策），因此v2就是初始決策所產(chǎn)生的狀態(tài)。如果把v2看成是原問題的一個子問題的初始狀態(tài)，解這個子問題就是找出一條由v2到t的最短路徑。這條路徑顯然是v2,v3,···,vk-1,t，否則設(shè)v2,q3,···,qk-1,t是一條由v2到t的更短路徑，則s,v2,q3,···,qk-1,t是一條比路徑s,v2,v3,···,vk-1,t更短的由s到t的路徑，與假設(shè)矛盾，故最優(yōu)化原理成立。2022/11/611of158cost(i,j)=min{C(j,r)+cost(i+1,r)}

r∈Vi+1<j,r>∈EjrtViVi+1最短最短向前處理法：設(shè)P(i,j)是從Vi中的點j到t的一條最短路，cost(i,j)是這條路線的耗費。由后向前推算，得到2022/11/612of158123456789101112s97324212711118654356425V1V2V3V4V5tcost(4,9)=4cost(i,j)=min{C(j,r)+cost(i+1,r)}

cost(4,10)=2cost(4,11)=5cost(3,6)=min{6+cost(4,9),5+cost(4,10)}=min{6+4,5+2}=7從第3段的頂點6到t的最短路徑是6-10-t5+22022/11/613of158123456789101112s97324212711118654356425V1V2V3V4V5tcost(3,7)=min{4+cost(4,9),3+cost(4,10)}=min{4+4,3+2}=5從第3段的頂點7到t的最短路徑是7-10-tcost(3,8)=7從第3段的頂點8到t的最短路徑是8-10-t2022/11/614of158123456789101112s97324212711118654356425V1V2V3V4V5tcost(2,2)=7從第2段頂點2到t的最短路是2-7-10-tcost(2,3)=9從第2段頂點3到t的最短路是3-6-10-tcost(2,4)=18從第2段頂點4到t的最短路是4-8-10-tcost(2,5)=15從第2段頂點5到t的最短路是5-8-10-tcost(1,1)=16從第1段頂點1到t的最短路徑由兩條：

1-2-7-10-t和1-3-6-10-t2022/11/615of158從s到t的一條最短路徑的代價為16。用D(i,j)表示使C(j,r)+cost(i+1,r)取得最小值

的r，則在上述求解過程中同時得到：D(3,6)=10,D(3,7)=10,D(3,8)=10D(2,2)=7,D(2,3)=6,D(2,4)=8D(2,5)=8,D(1,1)=2設(shè)從s到t的最短路徑為s,w2,w3,···,wk-1,t則有w2=D(1,1)=2w3=D(2,D(1,1))=D(2,2)=7w4=D(3,D(2,D(1,1)))=D(3,D(2,2))=D(3,7)=10所以這條路徑是1-2-7-10-t所以這條路徑是1-2-7-10-t2022/11/616of158為了便于描述算法，對一個k段圖的頂點，按段的順序給它的每個頂點編號。設(shè)圖中有n個頂點，則編號為1，2，···，n。首先，給s編為1號；然后給V2中的各個頂點分別編為2，3，···

，|V2|+1號；以此類推，最后t編號為n。這樣編號使Vi+1中的任何頂點的編號大于Vi中所有頂點的編號。于是，可以按n-1,n-2,···,1的順序計算出cost(i,j)和D(i,j)。算法中可以利用順序編號的特點，而不再考慮頂點所在的段。2022/11/617of158設(shè)頂點的編號已知，邊已知及邊的代價函

數(shù)C(i,j)已知。用cost[i]表示頂點i到t的最小

代價，1≤i≤n。用D[i]表示從頂點i到t的最短路徑上頂點i的后繼頂點號，用P[i]表示最短路徑經(jīng)過第i級的頂點號，1≤i≤k2022/11/618of158求兩點間最短路徑的算法：ProcedureFgraph

1.{fori←1toncost[i]←0；

2.forj=n-1step–1to1do

{

3.找頂點r,使<j,r>∈E,且C(j,r)+cost[r]最??；

4.cost[j]←C(j,r)+cost[r];

5.D[j]←r;

}

6.P[1]←1;P[k]←n;

7.forj=2tok-1doP[j]←D[P[j-1]]

}O(n+|E|)2022/11/619of158123456789101112s97324212711118654356425V1V2V3V4V5t（從前）向后：設(shè)BPij是從源點s到Vi中頂點j的最小成本路徑，bcost(i,j)是這條路徑的代價bcost(i,j)=min{bcost(i-1,r)+C(r,j)}r∈Vi-1<r,j>∈E2022/11/620of158格路問題：求從起點O(0,0)到終點E(m,n)的最短路。則分別用窮舉法和動態(tài)規(guī)劃法的加法次數(shù)和比較次數(shù)各是多少？E(m,n)O(0,0)xy2022/11/621of158E(m,n)O(0,0)xy2022/11/622of158E(m,n)O(0,0)xymn個點2022/11/623of158例2：貨郎擔(dān)問題1243105209128913156810∞1015205∞910613∞12889∞v1

v2v3v4v1v2v3v42022/11/624of158不失一般性，考慮以結(jié)點1為起點和終點的一條哈密頓回路。每一條這樣的路線都由一條邊<1,k>和一條由結(jié)點k到結(jié)點1的路徑組成，其中k∈V-{1},而這條由結(jié)點k到結(jié)點1的路徑通過V-{1，k}的每個結(jié)點各一次。如果這條周游路線是最優(yōu)的，則這條由結(jié)點k到結(jié)點1的路徑必定是通過V-{1，k}的每個結(jié)點各一次的由k到1的最短路徑。2022/11/625of158設(shè)T(i,S)是由結(jié)點i出發(fā)，經(jīng)過結(jié)點集S中每個結(jié)點各一次并回到初始結(jié)點1的一條最

短路徑長度，則T(1,V-{1})就是一條最優(yōu)的周游路線長度。動態(tài)規(guī)劃模型：T(1,V-{1})=min{d1k+T(k,V-{1,k})}2≤k≤nT(i,s)=min{dij+T(j,S-{j})}j∈S,i?S2022/11/626of158∞1015205∞910613∞12889∞v1

v2v3v4v1v2v3v4T(1,{2,3,4})=min{d12+T(2,{3,4}),

d13+T(3,{2,4}),d14+T(4,{2,3})}T(2,{3,4})=min{d23+T(3,{4}),d24+T(4,{3})}T(3,{4})=d34+T(4,Φ)T(4,Φ)=d412022/11/627of158T(1,{2,3,4})T(2,{3,4})T(3,{2,4})T(4,{2,3})T(3,{4})T(4,{3})T(2,{4})T(4,{2})T(2,{3})T(3,{2})T(4,Φ)T(3,Φ)T(4,Φ)T(2,Φ)T(3,Φ)T(4,Φ)2022/11/628of158矩陣鏈乘法問題描述加括號的方案數(shù)動態(tài)規(guī)劃法2022/11/629of158矩陣鏈乘法:問題描述給定n個矩陣A1,A2,…,An,Ai的維數(shù)為

pi-1×pi(1≤i≤n),要求計算鏈乘積A1A2…An由于矩陣乘法滿足結(jié)合率，所以可以有許多不同的計算次序，這種計算次序可以用加括號的方式來確定。比如：A1,A2,A3,A4

(A1(

A2(

A3(A4)))(A1((

A2A3)A4))(A1A2)(

A3A4)((A1(

A2A3))

A4)((A1A2)

A3)A4)2022/11/630of158不同的計算次序有不同的計算量注：1.設(shè)Ap×q,Aq×r兩矩陣相乘，普通乘法的次數(shù)為p×q×r2.加括號對乘法次數(shù)的影響如：A10×100×B100×5×C5×50((AB)C):10×100×5+10×5×50=7500次(A(BC)):100×5×50+10×100×50=75000次2022/11/631of158窮舉法：將n個矩陣從第k和第k+1處隔開，對二個子序列再分別加括號，則可以得到下面遞歸式：因此，窮舉法不是一個有效算法2022/11/632of1581.矩陣鏈乘問題滿足最優(yōu)性原理記A[i:j]為AiAi+1…Aj鏈乘的一個最優(yōu)括號方案，設(shè)A[i:j]的最優(yōu)次序中含有二個子鏈A[i:k]和A[k+1:n]，則A[i:k]和A[k+1:n]也是最優(yōu)的。（反證可得）2.矩陣鏈乘的子問題空間：A[i:j],1≤i≤j≤nA[1:1],A[1:2],A[1,:3],…,A[1:n]A[2:2],A[2:3],…,A[2:n]………A[n-1:n-1],A[n-1,n]A[n,n]2022/11/633of158遞歸求解最優(yōu)解的值記m[i][j]為計算A[i:j]的最少乘法數(shù)，則原問題的最優(yōu)值為

m[1][n](AiAi+1…Ak)pi-1×pk×(Ak+1Ak+2…Aj)pk×pj2022/11/634of158依據(jù)遞歸式自底向上計算。在計算過程中，保存已經(jīng)解決的子問題答案。A1,A2,A3,A4,A5,A62022/11/635of158A1=(aij)35Х40A2=(aij)40Х20

A3=(aij)20Х10A4=(aij)10Х15m[1][3]=min{m[1][2]=m[2][3]=40Х20Х10＝8000

m[3][4]=20Х10Х15＝300035Х40Х20＝28000m[1][1]+m[2][3]+35Х40Х10,

m[1][2]+m[3][3]+35Х20Х10}m[2][4]m[1][4]m11m12m13m14m22m23m24m33m34m44

j=1234i=1

2

3

42022/11/636of158MATRIX-CHAIN-ORDER(p)1n←

length[p]-12fori←1ton3 dom[i,i]←04forl←2ton//listhechainlength.5 dofori←1ton-l+16 doj←

i+l-17 m[i,j]←

∞8 fork←

itoj-19 doq←

m[i,k]+m[k+1,j]+pi-1pkpj10 ifq<m[i,j]11 thenm[i,j]←

q12 s[i,j]←

k13returnmands(n3)2022/11/637of158矩陣鏈乘法:s中存放m取得最優(yōu)時k的值

行x列A1 30x35A2 35x15A3 15x5A4 5x10A5 10x20A6 20x256555443333i33322333111654321sj6543i21654321mj0000001512550003500100053752500750105007125437526251187593757875157502022/11/638of158矩陣鏈乘法:s中存放m取得最優(yōu)時k的值6555443333i33322333111654321sjPRINT-OPTIMAL-PARENS(s,i,j)1ifi=j2 thenprint"A"i3 elseprint"("4 PRINT-OPTIMAL-PARENS(s,i,s[i,j])5 PRINT-OPTIMAL-PARENS(s,s[i,j]+1,j)6 print")"A1,A2,A3,A4,A5,A6

((A1(A2A3))((A4A5)A6))

2022/11/639of158課堂練習(xí)：貨物儲運問題在一個鐵路沿線順序存放著n堆裝滿貨物的集裝箱。貨物儲運公司要將集裝箱有次序地集中成一堆。規(guī)定每次只能選相鄰的2堆集裝箱合并成新的一堆，所需的運輸費用與新的一堆中集裝箱數(shù)成正比。給定各堆的集裝箱數(shù)，試制定一個運輸方案，使總運輸費用最少。5,3,4,1,3,2,3,4為了簡化，只算5,3,4,12022/11/640of158貨物儲運問題在一個鐵路沿線順序存放著n堆裝滿貨物的集裝箱。貨物儲運公司要將集裝箱有次序地集中成一堆。規(guī)定每次只能選相鄰的2堆集裝箱合并成新的一堆，所需的運輸費用與新的一堆中集裝箱數(shù)成正比。給定各堆的集裝箱數(shù)，試制定一個運輸方案，使總運輸費用最少。5,3,4,1,3,2,3,4設(shè)合并a[i:j]，1≤i≤j≤n，所需的最少費用為m[i,j]，則原問題的最優(yōu)值為m[1，n]。由最優(yōu)子結(jié)構(gòu)性質(zhì)可知，2022/11/641of158貨物儲運問題5,3,4,1m11m12m13m14m22m23m24m33m34m44

j=1234i=1

2

3

4

j=1234i=1

2

3

4反例4,2,3,42022/11/642of158最優(yōu)子結(jié)構(gòu):無后效性無權(quán)最短路徑:邊數(shù)最少.具有最優(yōu)子結(jié)構(gòu)性質(zhì).無權(quán)最長最短路徑:一定簡單.ifwedecomposealongestsimplepathintosubpaths,

thenmustn'tp1bealongestsimplepathfromutow,

andmustn'tp2bealongestsimplepathfromwtov?

Theanswerisno!

uv除接合點外,不能共享資源.2022/11/643of158最優(yōu)子結(jié)構(gòu):無后效性動態(tài)規(guī)劃要求其子問題既獨立又重疊:

如果同一問題的兩個子問題不共享資源,則它們是獨立的;

對兩個子問題來說,如果它們確實是相同的子問題,只是作為不同問題的子問題出現(xiàn)的話,是重疊的,則它們是重疊的.2022/11/644of158重疊子問題對比分治法遞歸的每一步常常產(chǎn)生全新的子問題.2022/11/645of158計算m[1][4]過程如下：自頂向下遞歸求解最優(yōu)解的值重疊子問題2022/11/646of158備忘錄MEMOIZED-MATRIX-CHAIN(p)1n←

length[p]-12fori←1ton3 doforj←

iton4 dom[i,j]←

∞5returnLOOKUP-CHAIN(p,1,n)//表示該子問題尚未解決2022/11/647of158備忘錄LOOKUP-CHAIN(p,i,j)1ifm[i,j]<∞2 thenreturnm[i,j]3ifi=j4 thenm[i,j]←05 elsefork←

itoj-16 doq←LOOKUP-CHAIN(p,i,k) +LOOKUP-CHAIN(p,k+1,j)+pi-1

pkpj7 ifq<m[i,j]8 thenm[i,j]←

q9returnm[i,j]2022/11/648of158自底向上的動規(guī)與備忘錄區(qū)別自底向上的動規(guī)每個子問題至少求解一次.備忘錄某些子問題根本沒有必要求解.2022/11/649of158Floyd算法A(k+1)(i,j)=min{A(k)(i,j)

,

A(k)(i,k+1)+A(k)(k+1,j)}A(k)(i,j)表示從i到j(luò)的最短路徑,且允許的中間結(jié)點是1…k04116023∞0v1

v2v3v1v2v3123643112v1

v2v3v1v2v30411602370A(1)

=2022/11/650of158A(k+1)(i,j)=min{A(k)(i,j)

,

A(k)(i,k+1)+A(k)(k+1,j)}A(k)(i,j)表示從i到j(luò)的最短路徑,且允許的中間結(jié)點是1…k04116023∞0v1

v2v3v1v2v3123643112v1

v2v3v1v2v30411602370A(1)

=v1

v2v3v1v2v3046

602370A(2)

=v1

v2v3v1v2v3046502370A(3)

=2022/11/651of158

Warshall算法Mk+1[i,j]=Mk[i,j]Floyd:

A(k+1)(i,j)=min{A(k)(i,j)

,

A(k)(i,k+1)+A(k)(k+1,j)}∨(Mk[i,k+1]∧

Mk[k+1,j])2022/11/652of158

Warshall算法Mk+1[i,j]=Mk[i,j]∨(Mk[i,k+1]∧

Mk[k+1,j])2022/11/653of158TRANSITIVE-CLOSURE(G)1n←|V[G]|2fori←1ton3 doforj←1ton4 doifi=jor(i,j)∈

E[G]11returnT(n)

Warshall算法2022/11/654of1580-1背包問題:問題描述及舉例問題描述舉例：w=(w1,w2,w3)=(2,3,4),v=(v1,v2,v3)=(1,2,5),n=3,c=6,求Knap(1,3,6)

取x=(1,0,1)時，2022/11/655of1580-1背包問題滿足最優(yōu)性原理證明：設(shè)(y1,y2,…,yn)是Knap(1,n,c)的一個最優(yōu)解，則(y2,…,yn)是Knap(2,n,c-w1y1)子問題的一個最優(yōu)解。若不然，設(shè)(z2,…,zn)是Knap(2,n,c-w1y1)的最優(yōu)解，因此有說明(y1,z2,…,zn)是Knap(1,n,c)的一個更優(yōu)解，矛盾。2022/11/656of1580-1背包問題:遞歸關(guān)系考慮子問題：

Knap(i,n,j)j≤c(假設(shè)c,wi取整數(shù))

設(shè)其最優(yōu)值為m(i,j),即m(i,j)是背包容量為j,可選物品為i,i+1,…,n的0-1背包問題的最優(yōu)值。子問題的背包容量在變化2022/11/657of1580-1背包問題:遞歸關(guān)系遞歸式如下：不取物品i取物品i2022/11/658of1580-1背包問題:算法voidKnapsack(intv[],intw[],intc,intn,intm[][]){//輸出m[1][c]intjMax=min(w[n]-1,c);//因為j≤c,只要計算到m[1][c]即可

for(intj=0;j<=jMax;j++)m[n][j]=0;//0≤j<wn,(4)式

for(intj=w[n];j<=c;j++)m[n][j]=v[n];//j≥wn,(3)式

for(inti=n-1;i>1;i--){//i>1表示對i=1不處理，因為i=1時只需求m[1][c]jMax=min(w[i]-1,c);for(intj=0;j<=jMax;j++)//0≤j<wi,(2)式

m[i][j]=m[i+1][j];for(intj=w[i];j<=c;j++)//j≥wi,(1)式

m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}if(c>=w[1])m[1][c]=max(m[2][c],m[2][c-w[1]]+v[1]);elsem[1][c]=m[2][c];}2022/11/659of1580-1背包問題:算法（續(xù)）voidTraceback(intw[],intc,intn,intm[][],intx[]){//輸出解x[1..n]for(inti=0;i<n;i++)if(m[i][c]=m[i+1][c])x[i]=0;else{x[i]=1;c-=w[i];}x[n]=(m[n][c])?1:0;}運行時間：T(n)=O(cn)2022/11/660of1580-1背包問題00000pi–1(j–wi)pi–1(j)0pi(j)0目標(biāo)

0i–1in0j–wi

jM2022/11/661of158例：有5個物體，其重量分別為2,2,6,5,4，價值分別為6,3,5,4,6，背包的載重量為10，求裝入背包的物體及其總價值2022/11/662of158找零錢問題:問題描述問題描述一出納員支付一定數(shù)量的現(xiàn)金。假設(shè)他手中有幾種面值的硬幣，要求他用最少的硬幣數(shù)支付規(guī)定的現(xiàn)金。

例如，現(xiàn)有3種硬幣：它們的面值分別為1元、4元和6元。要支付8元。2022/11/663of1580-1背包問題:遞歸關(guān)系不用第i種硬幣用第i種硬幣pi(j)：前i種硬幣支付金額j所需硬幣的最少個數(shù)。2022/11/664of1580∞

∞∞0pi–1(j)0pi(j–vi)pi(j)0目標(biāo)

0i–1in0j–vi

j82022/11/665of1581元、4元和6元。要支付8元。01234567800∞∞∞∞∞∞∞∞1012345678201231234230123121222022/11/666of158某公司準(zhǔn)備將新招聘的4名銷售員分配到下屬3個銷售點

甲、乙和丙。各銷售點增加若干名銷售員后可增加的

月銷售額如下表：增加銷售額（千元）增1人增2人增3人增4人甲12223038乙11202430丙13253036根據(jù)此表，只要人員分配適當(dāng)，公司每月最多

可以增加銷售額（）千元。動規(guī)練習(xí)2022/11/667of158最長公共子序列若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一個嚴(yán)格遞增下標(biāo)序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相應(yīng)的遞增下標(biāo)序列為{2，3，5，7}。給定2個序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。

2022/11/668of158最長公共子序列的結(jié)構(gòu)設(shè)序列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)若xm≠yn且zk≠xm，則Z是xm-1和Y的最長公共子序列。(3)若xm≠yn且zk≠yn，則Z是X和yn-1的最長公共子序列。證明:P57由此可見，2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2022/11/669of158子問題的遞歸結(jié)構(gòu)由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列和的最長公共子序列的長度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當(dāng)i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時C[i][j]=0。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：2022/11/670of