南開大學(xué)ACM暑期集訓(xùn)之動態(tài)規(guī)劃ppt課件

1、南開大學(xué)ACM暑期集訓(xùn)之動態(tài)規(guī)劃朱毅2006年8月本講稿主要來源福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院第一節(jié)動態(tài)規(guī)劃的根本要素 動態(tài)規(guī)劃主要用于組合優(yōu)化問題，即求一個(gè)離散問題在某種意義下的最優(yōu)解，有時(shí)也用于組合計(jì)數(shù)問題。 那么，什么樣的問題適宜用動態(tài)規(guī)劃求解呢? 適宜用動態(tài)規(guī)劃求解的問題的兩個(gè)根本要素: (1)最優(yōu)子構(gòu)造性質(zhì) 一個(gè)問題可用動態(tài)規(guī)劃有效求解的根本要求是該問題具有最優(yōu)子構(gòu)造性質(zhì)，通俗地講即問題的最優(yōu)解包含其子問題的最優(yōu)解。 (2)子問題重疊性質(zhì) 動態(tài)規(guī)劃所針對的問題還有另外一個(gè)顯著的特征，即它所對應(yīng)的子問題樹中的子問題呈現(xiàn)大量的反復(fù)，稱為子問題重疊性質(zhì)。 在運(yùn)用動態(tài)規(guī)劃時(shí)，對于反復(fù)出現(xiàn)的子問

2、題，只需在第一次遇到時(shí)加以求解，并把答案保管起來，以便以后再遇到時(shí)直接援用，不用重新求解，從而大大地提高解題的效率。 相比之下，普通的搜索技術(shù)，對于某個(gè)子問題，不論能否曾經(jīng)求解過，只需遇上，就會再次對它求解，因此影響了解題的效率。實(shí)例一、數(shù)字三角形問題 1問題描畫 給定一個(gè)具有N層的數(shù)字三角形，從頂至底有多條途徑，每一步可沿左斜線向下或沿右斜線向下，途徑所經(jīng)過的數(shù)字之和為途徑得分，懇求出最小途徑得分。 2 6 2 1 8 4 1 5 6 8圖41 數(shù)字三角形 2解題思緒 這道題可以用動態(tài)規(guī)劃勝利地處理，但是，假設(shè)對問題的最優(yōu)構(gòu)造描寫得不恰當(dāng)(即形狀表示不適宜)，那么無法運(yùn)用動態(tài)規(guī)劃。 形狀表示

3、法一： 用一元組D(X)描畫問題，D(X)表示從頂層到達(dá)第X層的最小途徑得分。因此，此問題就是求出D(N)(假設(shè)需求，還應(yīng)求出最優(yōu)途徑)。這是一種很自然的想法和表示方法。遺憾的是，這種描畫方式并不能滿足最優(yōu)子構(gòu)造性質(zhì)。由于D(X)的最優(yōu)解(即最優(yōu)途徑)能夠不包含子問題例如D(X-1)的最優(yōu)解。如圖41所示： 顯然，D(4)2+6+1+110，其最優(yōu)解(途徑)為2-6-1-1。而D(3)2+2+48，最優(yōu)解(途徑)為2-2-4。故D(4)的最優(yōu)解不包含子問題D(3)的最優(yōu)解。由于不滿足最優(yōu)子構(gòu)造性質(zhì)，因此無法建立子問題最優(yōu)值之間的遞歸關(guān)系，也即無法運(yùn)用動態(tài)規(guī)劃。 2 6 2 1 8 4 1 5

4、6 8圖41 數(shù)字三角形 形狀表示法二： 用二元組D(X,y)描畫問題，D(X,y)表示從頂層到達(dá)第X層第y個(gè)位置的最小途徑得分。 最優(yōu)子構(gòu)造性質(zhì)：容易看出，D(X,y)的最優(yōu)途徑Path(X,y)一定包含子問題D(X-1,y)或D(X-1,y-1)的最優(yōu)途徑。 否那么，取D(X-1,y)和D(X-l,y-1)的最優(yōu)途徑中得分小的那條途徑加上第X層第y個(gè)位置構(gòu)成的途徑得分必然小于Path(X,y)的得分，這與Path(X,y)的最優(yōu)性是矛盾的。 2 6 2 1 8 4 1 5 6 8圖41 數(shù)字三角形 n 如圖41所示，D(4,2)的最優(yōu)途徑為2-6-1-5，它包含D(3,1)最優(yōu)途徑2-6-

5、1。因此，用二元組D(X,y)描畫的計(jì)算D(X,y)的問題具有最優(yōu)子構(gòu)造性質(zhì)。 遞歸關(guān)系： D(X,y)minD(X-1,y)，D(X-1,y-1+a(X,y) D(1,1)a(1,1) n其中，a(X,y)為第X層第y個(gè)位置的數(shù)值。n 原問題的最小途徑得分可以經(jīng)過比較D(N,i)獲得，其中i1，2，N。n 在上述遞歸關(guān)系中，求D(X,y)的時(shí)候，先計(jì)算D(X-1,y)和D(X-1,y-1)，下一步求D(X，y+1)時(shí)需求D(X-1，y+1)和D(X-1，y)，但其中D(X-1，y)在前面曾經(jīng)計(jì)算過了。于是，子問題重疊性質(zhì)成立。n 因此，采用形狀表示法二描畫的問題具備了用動態(tài)規(guī)劃求解的根本要素

6、，可以用動態(tài)規(guī)劃進(jìn)展求解。 形狀表示法三： 采用形狀表示法二的方法是從頂層開場，逐漸向下至底層來求出原問題的解?，F(xiàn)實(shí)上，還可以從相反的方向思索。仍用二元組D(X,y)描畫問題，D(X,y)表示從第X層第y個(gè)位置到達(dá)底層的最小途徑得分。原問題的最小途徑得分即為D(1,1)。 最優(yōu)子構(gòu)造性質(zhì)：顯然，D(X,y)的最優(yōu)途徑Path(X,y)一定包含子問題D(X+1,y)或D(X+1,y+1)的最優(yōu)途徑，否那么，取D(X+1,y)和D(X+1,y+1)的最優(yōu)途徑中得分小的那條途徑加上第X層第y個(gè)位置構(gòu)成的途徑得分必然小于Path(X,y)的得分，這與Path(X,y)的最優(yōu)性矛盾。 2 6 2 1 8

7、 4 1 5 6 8圖41 數(shù)字三角形 n 如下圖，D(1，1)的最優(yōu)途徑為2-6-1-1，它包含D(2,1)的最優(yōu)途徑6-1-1。因此，這種形狀表示描畫的計(jì)算D(X，y)的問題同樣具有最優(yōu)子構(gòu)造性質(zhì)。n遞歸關(guān)系：n D(X,y)minD(X+1,y),D(X+1,y+1)+a(X,y)n D(N,k)a(N,k)，k1，Nn其中，a(X，y)為第X層第y個(gè)位置的數(shù)值。n D(X,y)表示從第X層第y個(gè)位置到達(dá)底層的最小途徑得分。原問題的最小途徑得分即為D(1,1)。 算法設(shè)計(jì) 采用形狀表示法三的算法的主要過程如下： for ( i = n - 2; i = 0; -i ) for ( j =

8、 0; j = i; +j )tmp = soui + 1j;if ( soui + 1j + 1 tmp )tmp = soui + 1j + 1;souij += tmp; printf( %dn, sou00 );第二節(jié)動態(tài)規(guī)劃算法步驟 (1)選擇適當(dāng)?shù)膯栴}形狀表示，并分析最優(yōu)解的性質(zhì)； (2)遞歸地定義最優(yōu)值(即建立遞歸關(guān)系)； (3)以自底向上的方式計(jì)算出最優(yōu)值； (4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。 步驟(1)(3)是動態(tài)規(guī)劃的根本步驟。在只需求求出最優(yōu)值的情形，步驟(4)可以省略。 假設(shè)需求求出問題的一個(gè)最優(yōu)解，那么必需執(zhí)行步驟(4)。此時(shí)，在步驟(3)中計(jì)算最優(yōu)值

9、時(shí)，通常需記錄更多的信息，以便在步驟(4)中，根據(jù)所記錄的信息，快速地構(gòu)造出一個(gè)最優(yōu)解。 本卷須知: 在進(jìn)一步討論動態(tài)規(guī)劃設(shè)計(jì)方法及運(yùn)用之前，有兩點(diǎn)需求留意： (1)問題的形狀表示對能否用動態(tài)規(guī)劃進(jìn)展求解是至關(guān)重要的，不恰當(dāng)?shù)男螤畋硎緦⑹箚栴}的描畫不具有最優(yōu)子構(gòu)造性質(zhì)，從而無法建立最優(yōu)值的遞歸關(guān)系，動態(tài)規(guī)劃的運(yùn)用也就無從談起。因此，上面步驟(1)，即形狀表示和最優(yōu)子構(gòu)造性質(zhì)的分析，是最關(guān)鍵的一步。 (2)在算法的程序設(shè)計(jì)中，應(yīng)充分利用子問題重疊性質(zhì)來提高解題效率。更詳細(xì)地說，應(yīng)采用遞推(迭代)的方法來編程計(jì)算由遞歸式定義的最優(yōu)值，而不采用直接遞歸的方法。實(shí)例二、花束擺放問題 1問題描畫 如今有

10、F束不同種類的花束，同時(shí)有至少同樣數(shù)量的花瓶被按順序擺成一行，其位置固定于架子上，并從1至V按從左到右順序編號，V是花瓶的數(shù)目(FV)?；ㄊ梢耘矂?，并且每束花用1至F的整數(shù)獨(dú)一標(biāo)識。標(biāo)識花束的整數(shù)決議了花束在花瓶中陳列的順序，假設(shè)ij，花束i必需放在花束j左邊的花瓶中。每個(gè)花瓶只能放一束花。假設(shè)花瓶的數(shù)目大于花束的數(shù)目，那么多余的花瓶空置。 每一個(gè)花瓶都具有各自的特點(diǎn)。因此，當(dāng)各個(gè)花瓶中放入不同的花束時(shí)，會產(chǎn)生不同的美學(xué)效果，并以一美學(xué)值(一個(gè)整數(shù))來表示，空置花瓶的美學(xué)值為零。為獲得最正確美學(xué)效果，必需在堅(jiān)持花束順序的前提下，使花束的擺放獲得最大的美學(xué)值。懇求出具有最大美學(xué)值的一種擺放方式

11、。 2解題思緒 形狀表示法一： 設(shè)A(i,j)表示第i種花束擺在第j個(gè)花瓶中獲得的美學(xué)值。S(i,k)表示第i種花束擺在第k個(gè)花瓶中時(shí)(這里ki)，前i種花束可以獲得的最大美學(xué)值(之和)。這樣，原問題的最優(yōu)值可以經(jīng)過計(jì)算maxS(F,k)FkV獲得。 下面要分析一下這種形狀表示法描畫問題的方式能否具備了用動態(tài)規(guī)劃求解的根本要素。 最優(yōu)子構(gòu)造性質(zhì)：對滿足FkV的k，設(shè)T(F,k)是到達(dá)最優(yōu)值S(F,k)的一種最正確擺放方式，其中，第F-1種花束擺在第j個(gè)花瓶中(j1 S(1,k)=A(1,k) 在計(jì)算S(i,k-1)時(shí)，曾經(jīng)計(jì)算出了S(i-1,j)，i-1jk-2及其 maxS(i-1,j)i-

12、1jk-2 。因此，計(jì)算S(i,k)時(shí)，只需將S(i-1,k-1)與max S(i-1,j)i-1jk-2 進(jìn)展比較即可求得,即子問題重疊性質(zhì)。這樣做可以大大減少計(jì)算量。 現(xiàn)實(shí)上，還可以有更直接的方法。 形狀表示法二： 設(shè)Si,k表示第i種花束擺在第k個(gè)之前(包括第k個(gè))的恣意某個(gè)花瓶中，前i種花束可以獲得的最大美學(xué)值(之和)。這樣，原問題的最優(yōu)值即為SF,V。這比前一個(gè)表示法更直接。 容易驗(yàn)證，計(jì)算SF,V的問題具有最優(yōu)子構(gòu)造性質(zhì)。 其遞歸方程為： Si,k=maxSi-1,k-1+A(i,k)，Si,k-1，(i1，ki); 初始條件為： S1,1=A1,1; S1,k=maxA(1,k)

13、,S1,k-1，(k1); Si,i=Si-1,i-1+A(i,i)， (i1) 算法設(shè)計(jì)(形狀表示法二) 算法的過程如下： s00 = a00; out00 = true; for ( j = 1; j a0j ? s0j - 1 :a0j;out0j = ( s0j != s0j - 1 );for ( i = 1; i f & i ?= si - 1j - 1 + aij;outij = ( sij != sij - 1 );sij = si - 1j - 1 + aij; outij = true;if ( i ?= sij - 1; outij = ( sij != sij

14、- 1 ); 實(shí)例三、美觀輸出問題 1問題描畫 給定N個(gè)英文單詞組成的一段文章，每個(gè)單詞的長度(字符個(gè)數(shù))依序?yàn)閘1, l2,ln ，要在一臺每行最多能打印M( li M，i1,2,n )個(gè)字符的打印機(jī)上將這段文章“美觀地輸出來。這里的“美觀指的是：在打印機(jī)輸出的每一行中，行首和行尾可以不留空格，行中每兩個(gè)單詞之間留一個(gè)空格。且不允許將單詞拆開。除文章的最后一行外，希望每行多余的空格數(shù)的總和盡能夠少，同時(shí)多余的空格數(shù)在每行的分布盡能夠均勻，為此，把每行的多余空格數(shù)(除最后一行外)的平方和到達(dá)最小作為“美觀的規(guī)范。懇求出個(gè)“美觀的輸出方案。 2解題思緒 由上面的分析很自然想到采用這樣一種戰(zhàn)略(稱

15、為貪婪戰(zhàn)略)：每一行在不突破單詞的前提下按順序盡能夠多地輸出單詞。 但是，這樣做法有時(shí)無法求得最優(yōu)解。 例如，對n5, l142, l25, l320, l420, l540, M50，根據(jù)該戰(zhàn)略得到的輸出方案是1,2,3,4,5，但這不是最優(yōu)輸出方案，其多余空格數(shù)(除最后一行外)的平方和為22 + 92 85?，F(xiàn)實(shí)上，輸出方案1,2,3,4,5為最優(yōu)輸出方案，其多余空格數(shù)(除最后一行外)的平方和為82 + 32 73。 為此，思索用動態(tài)規(guī)劃求解。設(shè)C1,k是安排單詞1k時(shí)的最小費(fèi)用 ， 那 么 所 要 求 的 最 小 費(fèi) 用 為C1,n。 討論： C1,k具有最優(yōu)子構(gòu)造性質(zhì)？ 答案能否認(rèn)的。

16、n為此我們思索 Ck,n。n設(shè)Ck,n,(k1)是從一行開場安排單詞kn時(shí)的最小費(fèi)用，那么所要求的最小費(fèi)用為C1,n。n (1)問題具有最優(yōu)子構(gòu)造性質(zhì)：在一個(gè)最優(yōu)輸出方案中，從行頭開場的子輸出方案是子問題的最優(yōu)輸出方案。 (2)建立遞歸關(guān)系 設(shè) Si,j= M-(j-i)-n Si,j0nfeei,j= 0 Si,j0,j=nn (Si,j)2,其它情況n為將單詞ij安排在一行輸出時(shí)行尾的空格數(shù)。需求留意的是， Si,j能夠?yàn)樨?fù)。n feei,j表示將單詞ij打印在一行上的費(fèi)用，那么 jikkl遞歸關(guān)系：Ck,n,(1kn)是從一行開場安排單詞kn時(shí)的最小費(fèi)用，所要求的最小費(fèi)用為C1,n。 C

17、 k, n = (k=1,2,n)C n+1, n = 0 (n 1) , 1,minnjCjkfeenjk實(shí)例四、排隊(duì)買票問題 1問題描畫 一場演唱會即將舉行?，F(xiàn)有n個(gè)歌迷排隊(duì)買演唱會的票。一個(gè)人1張票。第i位歌迷買l張票需求時(shí)間t(i),為加快售票過程，售票處規(guī)定，隊(duì)伍中相鄰的2位歌迷(第j人和第j+1人)也可以由其中一人(例如第j位)買2張票(一個(gè)人每次最多也只能買2張票)，而另外一位就不用排隊(duì)了(也不再替他人買票)，按這種方式買票，這2位歌迷買2張票的時(shí)間變?yōu)閞(j) 。給出n，t(i)和r(j)的值，編程求出使每個(gè)人都買到一張票的最短時(shí)間和方法。 2解題思緒 此題可以用深度優(yōu)先搜索來

18、求解，但其時(shí)間復(fù)雜度為指數(shù)增長，因此思索能否用動態(tài)規(guī)劃的方法。 形狀表示：以f(i)表示第i位和其后的歌迷總的買票時(shí)間的最小值，但不委托第i-1位歌迷買票?？偟馁I票時(shí)間的最小值為f(1)。 最優(yōu)子構(gòu)造性質(zhì)：假設(shè)i1i2ik，kn是l，n的一個(gè)最正確買票方法，其中ip，lp k 表示第p個(gè)買票的是隊(duì)伍中排在第ip個(gè)的歌迷。 如今，無非有3種情況： (1)第1位歌迷只為本人買票，即i1=1。顯然， i2ik，kn是2，n的一個(gè)最正確買票方法。 (2)第1位歌迷委托第2位歌迷買票，即i1=2。此時(shí)，i2ik，kn是3，n的一個(gè)最正確買票方法。 (3)第1位歌迷替第2位歌迷買票，即i1=1。此時(shí)，i2

19、ik，kn仍是3，n的一個(gè)最正確買票方法。 因此，問題具有最優(yōu)子構(gòu)造性質(zhì)。根據(jù)該性質(zhì)，容易得到形狀轉(zhuǎn)移方程： 遞歸關(guān)系： f(i)= mint(i)+f(i+1),minr(i),r(i+1)+f(i+2) (i=1,2,n-1)f(n)=t(n),f(n+1)=0 形狀表示：以f(i)表示第i位和其后的歌迷總的買票時(shí)間的最小值，但不委托第i-1位歌迷票。 總的買票時(shí)間的最小值為f(1)。實(shí)例五、最少硬幣找錢問題 1問題描畫 設(shè)有n種不同面值的硬幣，各硬幣的面值存于數(shù)組T1.n中。現(xiàn)要用這些面值的硬幣來找錢。可以運(yùn)用的各種面值的硬幣個(gè)數(shù)不限。請計(jì)算找出錢數(shù) L 的最少硬幣個(gè)數(shù)。 2解題思緒 (

20、1)形狀表示；無妨設(shè)0T1T2Tn。當(dāng)只用面值為T1，T2，Ti的硬幣時(shí)，可找出錢數(shù)j的最少硬幣個(gè)數(shù)記為Ci,j；當(dāng)只用這些面值的硬幣找不出錢數(shù)j時(shí)，記Ci,j=。問題的解即為Cn,L。 (2)最優(yōu)子構(gòu)造性質(zhì) 設(shè)Sk，k=1,2,i 是只用面值為T1，T2，Ti的硬幣找錢j的一個(gè)最優(yōu)找錢序列,即 j = ,而且 ikkTkS1ikjiCkS1,n 那么容易看出：Sk，k=1,2,i-1是只用面值為T1,T2,Ti-1的硬幣找錢j-SiTi的一個(gè)最優(yōu)找錢序列。 (2)根據(jù)最優(yōu)子構(gòu)造性質(zhì),可以建立遞歸關(guān)系： Ci,j=, 1min/0kiTkjiCiTjkn初始條件為：Ci,00，il，n;n ,

21、 j mod T10n C1,j= n j div T1, j mod T1=0 n問題的解:找出錢數(shù) L 的最少硬幣個(gè)數(shù)為Cn,L。 需求闡明的是，還可以對Ci,j遞歸式作進(jìn)一步的簡化： 方法二: Ci-1,j；假設(shè)j0，即最優(yōu)找錢序列至少有一個(gè)Ti，那么在該最優(yōu)找錢序列中去掉一個(gè)Ti后的找錢序列應(yīng)是用用T1.n的硬幣可找出錢數(shù)j-Ti的最優(yōu)找錢序列，其個(gè)數(shù)為Cj-Ti。故計(jì)算Cj的問題具有最優(yōu)子構(gòu)造性質(zhì)。 根據(jù)最優(yōu)子構(gòu)造性質(zhì)，對于任何1jL及1in，假設(shè)j-Ti0，那么Cj-Ti所表示的找錢j-Ti的最優(yōu)找錢序列，再加上一枚面值為Ti的硬幣是一種找錢j的方法，且所用的硬幣個(gè)數(shù)為Cj-Ti+

22、1。因此，可建立如下的遞歸關(guān)系：1min0,1iTjCiTjnin問題的解:找出錢數(shù) L 的最少硬幣個(gè)數(shù)為CL。 0, j=0 , 0jT1遞歸關(guān)系和初始條件：實(shí)例六、編輯間隔問題 1. 問題描畫 設(shè)A和B是2個(gè)字符串。要用最少的字符操作，將字符串A轉(zhuǎn)換為字符串B。這里所說的字符操作包括： (1)刪除一個(gè)字符； (2)插入一個(gè)字符； (3)將一個(gè)字符改為另一個(gè)字符。 將字符串A轉(zhuǎn)換為字符串B所用的最少字符操作 數(shù) 稱 為 字 符 串 A到 B的 編 輯 間 隔 ， 記 為(A,B)。懇求出(A,B)。 2解題思緒 設(shè)所給的2個(gè)字符串分別為AA1.m和B=B1.n。 形狀表示：思索從字符子串A1

23、.i(按序)變換到字符子串B1.j的最少字符操作問題，有d(i，j) (A1.i， B1.j)。顯然，2個(gè)單字符a，b之間的編輯間隔:當(dāng)ab時(shí)，為(a，b)1；當(dāng)a=b時(shí)，為(a，b)0 。問題的解為d(m，n)。 最優(yōu)子構(gòu)造性質(zhì)：假設(shè)Eelek-1ek，k= d(i,j)為從字符串A1.i按序變換到字符串B1.j的一個(gè)最少字符操作序列(也稱作d(i,j)的一個(gè)最優(yōu)解)，那么最后一個(gè)操作ek，屬于以下3種操作之一： (1)將字符Ai改為字符Bj(假設(shè)AiBj，那么ek為空操作,不參與計(jì)數(shù))，此時(shí)E1elek-1為d(i-1，j-1)的一個(gè)最優(yōu)解； (2)刪除字符Ai,此時(shí)E1elek-1為d(

24、i-1,j)的一個(gè)最優(yōu)解； (3)插入字符Bj,此時(shí)E1elek-1為d(i,j-1)的一個(gè)最優(yōu)解。 因此,問題具有最優(yōu)子構(gòu)造性質(zhì)。根據(jù)最優(yōu)子構(gòu)造性質(zhì),建立遞歸關(guān)系如下： d(i,j)mind(i-1,j-1)+(Ai,Bj),d(i-1,j)+1,d(i,j-1)+1 初始條件：d(i,0)i,i0m； d(O,j)j，j0n。 問題的解為d(m，n)。實(shí)例七、最長公共子序列問題 1.問題描畫 一個(gè)給定序列的子序列是在該序列中刪去假設(shè)干元素后得到的序列。給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。公共子序列中長度最長的公共子序列叫做最長公共子

25、序列。 最長公共子序列(LCS)問題可以表達(dá)為：給定2個(gè)序列X=x1，xm和Y=y1，yn，要求找出X和Y的一個(gè)最長公共子序列。 2解題思緒 解最長公共子序列問題時(shí)最容易想到的算法是窮舉搜索法，即對X的每一個(gè)子序列，檢查它能否也是Y的子序列，從而確定它能否為X和Y的公共子序列，并且在檢查過程中遴選出最長的公共子序列。X的一切子序列都檢查過后即可求出X和Y的最長公共子序列。 X的一個(gè)子序列相應(yīng)于下標(biāo)序列1，2，m的個(gè)子序列，故X共有2m個(gè)不同子序列，窮舉搜索法需求指數(shù)時(shí)間。為此，思索能否用動態(tài)規(guī)劃方法求解。 形狀表示：用Ci,j記錄序列X(i)和Y(j)的最長公共子序列的長度，其中X(i)=x1

26、，xi, Y(j)=y1，yj 。原問題最優(yōu)解的長度為Cm,n。 最優(yōu)子構(gòu)造性質(zhì)： 設(shè)序列X=x1，xm和Y=y1，yn的一個(gè)最長公共子序列為Z=z1，zk。那么下述結(jié)論成立： (1)假設(shè)xm = yn，那么zk = xm = yn 且Z(k-1) = z1，zk-1是X(m-1)和Y(n-1)的最長公共子序列。 (2)假設(shè)xm yn 且 zk xm，那么Z是X(m-1)和Y的最長公共子序列。 (3)假設(shè)xm yn 且 zk yn，那么Z是X和Y(n-1)的最長公共子序列。 證明： (1)用反證法。假設(shè)zk xm，那么z1，zk，xm是X和Y的長度為k+l的公共子序列。這與Z是X和Y的一個(gè)最長

27、公共子序列矛盾。因此，必有zk = xm = yn。由此可知Z(k-1)=z1，zk-1是X(m-1)和Y(n-1)的一個(gè)長度為k-1的公共子序列。假設(shè)X(m-1)和Y(n-1)有一個(gè)長度大于k-1的公共子序列w，那么將xm加在其尾部將產(chǎn)生X和Y的一個(gè)長度大于K的公共子序列。此為矛盾。故 Z(k-1) = z1，zk-1是X(m-1)和Y(n-1)的一個(gè)最長公共子序列。 (2)由于zk xm，Z是X(m-1)和Y的一個(gè)公共子序列。假設(shè)X(m-1)和Y有一個(gè)長度大于k的公共子序列w，那么w也是X和Y的一個(gè)長度大于k的公共子序列。這與Z是X和y的一個(gè)最長公共子序列矛盾。由此可知，Z是X(m-1)和

28、Y的最長公共子序列。 (3)與(2)類似。 上述結(jié)論：2個(gè)序列的最長公共子序列包含了這2個(gè)序列前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子構(gòu)造性質(zhì)。 由最長公共子序列問題的最優(yōu)子構(gòu)造性質(zhì)可知，要找出X=x1，xm和Y=y1，yn的一個(gè)最長公共子序列，可按以下方式遞歸地進(jìn)展： 當(dāng) xm = yn時(shí)，找出X(m-1)和Y(n-1)的最長公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一個(gè)最長公共子序列。 當(dāng)xm yn時(shí)，必需解2個(gè)子問題，即找出X(m-1)和Y的一個(gè)最長公共子序列及X和Y(n-1)的一個(gè)最長公共子序列。這2個(gè)公共子序列中較長者即為X和Y的一個(gè)最長公共子序列。 我

29、們來建立子問題的最優(yōu)值Ci,j的遞歸關(guān)系。當(dāng)i=0或j=0時(shí)，空序列是X(i)和Y(j)的最長公共子序列，故Ci,j0。其他情況下，由最優(yōu)子構(gòu)造性質(zhì)，可建立遞歸方程如下: 0 i=0 或j=0;Ci,j Ci-1,j-1+1 i,j0 且xi=yj; maxCi-1,j,Ci,j-1 i,j0 且xiyj; 由此遞歸方程容易看到最長公共子序列問題具有子問題重疊性質(zhì)。 實(shí)例八、多邊形游戲問題 1998年國際信息學(xué)奧林匹克競賽試題之一 1問題描畫 多邊形游戲是一個(gè)單人玩的游戲，開場時(shí)有一個(gè)由n個(gè)頂點(diǎn)構(gòu)成的多邊形。每個(gè)頂點(diǎn)被賦予一個(gè)整數(shù)值，每條邊被賦予個(gè)運(yùn)算符“+或“*。一切邊依次用整數(shù)1到n編號。

30、 游戲第1步，將一條邊刪除。 隨后n-1步按以下方法操作。 (1)選擇一條邊E以及由E銜接著的2個(gè)頂點(diǎn)Vl和V2； (2)用一個(gè)新的頂點(diǎn)取代邊E以及由E銜接著的2個(gè)頂點(diǎn)V1和V2。將頂點(diǎn)V1和V2的整數(shù)值經(jīng)過邊上的運(yùn)算得到的結(jié)果賦予新頂點(diǎn)。最后，一切邊都被刪除，游戲終了。游戲的得分就是所剩頂點(diǎn)上的整數(shù)值。 編程義務(wù)：對于給定的多邊形，編程計(jì)算出最高得分，而且列出一切得到這個(gè)最高得分初次被刪除的邊的編號。 數(shù)據(jù)輸入：由文件polygon.in提供輸入數(shù)據(jù)，文件的第1行是所給多邊形的頂點(diǎn)數(shù)n；第2行包含一切邊1n所對應(yīng)的運(yùn)算符，以及與順序2邊相關(guān)聯(lián)的頂點(diǎn)的數(shù)值(1號邊與2號邊之間是1號頂點(diǎn)的數(shù)值，

31、2號邊與3號邊之間是2號頂點(diǎn)的數(shù)值，依此類推。最后的一個(gè)數(shù)值對應(yīng)于與n號邊和1號邊相關(guān)聯(lián)的頂點(diǎn))。運(yùn)算符與數(shù)值之間用一個(gè)空格分隔。字母t代表運(yùn)算符“+，字母x代表運(yùn)算符“*。文件名由鍵盤輸入。 約束條件： 3多邊形的頂點(diǎn)數(shù)50 無論刪除順序如何，一切頂點(diǎn)的數(shù)值均在-32768，32767范圍內(nèi)。 結(jié)果輸出：程序運(yùn)轉(zhuǎn)終了時(shí)，將計(jì)算結(jié)果寫入文件polygon.out中。文件的第1行是計(jì)算出的最高得分。第2行是一切得到這個(gè)最高得分初次被刪除的邊按升序陳列的編號。 2解題思緒 (1)最優(yōu)子構(gòu)造性質(zhì)。 設(shè)所給的多邊形的頂點(diǎn)和邊的順時(shí)針序列為： op1，v1，op2，v2，opn，vn 其中opi表示第i

32、條邊所對應(yīng)的運(yùn)算符，vi表示第i個(gè)頂點(diǎn)上的數(shù)值，iln。 在所給的多邊形中，從頂點(diǎn)i (1in)開場，長度為j (鏈中有j個(gè)頂點(diǎn))的順時(shí)針鏈p (i, j) 可表示為： vi，opi+1，vi+j-1 假設(shè)這條鏈的最后一次合并運(yùn)算在opi+s處發(fā)生(1sj-1)，那么可在opi+s處將鏈分割為2個(gè)子鏈p(i, s)和p(i+s, j-s)。 設(shè)m1是對子鏈p(i, s)的恣意一種合并方式得到的值，而a和b分別是在一切能夠的合并中得到的最小值和最大值。m2是p(i+s, j-s)的以恣意一種合并方式得到的值，而c和d分別是在一切能夠的合并中得到的最小值和最大值。依此定義有 am1b cm2d 子

33、鏈p(i, s)和p(i+s, j-s)的合并方式取決于p(i, j)在opi+s處斷開后的合并方式，在opi+s處合并后其值為： m(m1)opi+s (m2) 當(dāng)opi+s“+時(shí)，顯然有 a+cmb+d 換句話說，由鏈p(i, j)合并的最優(yōu)性可推出子鏈p(i, s)和p(i+s, j-s)的最優(yōu)性，且最大值對應(yīng)于子鏈的最大值，最小值對應(yīng)于子鏈的最小值。 當(dāng)opi+s“*時(shí)，情況有所不同。由于vi可取負(fù)整數(shù)，子鏈的最大值相乘未必能得到主鏈的最大值。但是我們留意到最大值一定在邊境點(diǎn)到達(dá)，即 minac, ad, bc, bdmmax(ac, ad, bc, bd) 換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。例如，當(dāng)mmax=ac時(shí)， 最大主鏈由它的2條最小子鏈組成；同理當(dāng)mmax bd時(shí)，最大主鏈由它的2條最大子鏈組成。無論哪種情形發(fā)生，由主鏈的最優(yōu)性均可推出子鏈的最