第9章第1節(jié) 動態(tài)規(guī)劃基礎(chǔ)(C版)

1、第九章 動態(tài)規(guī)劃第一節(jié) 動態(tài)規(guī)劃的基本模型第二節(jié) 背包問題第三節(jié) 動態(tài)規(guī)劃經(jīng)典題 動態(tài)規(guī)劃程序設(shè)計(jì)是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不像前面所述的那些搜索或數(shù)值計(jì)算那樣，具有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解題方法。動態(tài)規(guī)劃程序設(shè)計(jì)往往是針對一種最優(yōu)化問題，由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動態(tài)規(guī)劃的設(shè)計(jì)方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此讀者在學(xué)習(xí)時，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。我們也可以通過對若干有代表

2、性的問題的動態(tài)規(guī)劃算法進(jìn)行分析、討論，逐漸學(xué)會并掌握這一設(shè)計(jì)方法。第一節(jié) 動態(tài)規(guī)劃的基本模型多階段決策過程的最優(yōu)化問題 在現(xiàn)實(shí)生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個過程達(dá)到最好的活動效果。當(dāng)然，各個階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展，當(dāng)各個階段決策確定后，就組成一個決策序列，因而也就確定了整個過程的一條活動路線，這種把一個問題看作是一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，這種問題就稱為多階段決策問題。如下圖所示： 多階段決策過程，是指這樣的一類特殊的活動過程，問題

3、可以按時間順序分解成若干相互聯(lián)系的階段，在每一個階段都要做出決策，全部過程的決策是一個決策序列?！纠?】最短路徑問題。下圖給出了一個地圖，地圖中的每個頂點(diǎn)代表一個城市，兩個城市間的一條連線代表道路，連線上的數(shù)值代表道路的長度?，F(xiàn)在想從城市A到達(dá)城市E，怎樣走路程最短？最短路程的長度是多少？【算法分析】 把A到E的全過程分成四個階段，用K表示階段變量，第1階段有一個初始狀態(tài)A，有兩條可供選擇的支路A-B1、A-B2；第2階段有兩個初始狀態(tài)B1、B2，B1有三條可供選擇的支路，B2有兩條可供選擇的支路。用DK（XI，X+1J）表示在第K階段由初始狀態(tài)XI到下階段的初始狀態(tài)X+1J的路徑距離，F(xiàn)K（

4、XI）表示從第K階段的XI到終點(diǎn)E的最短距離，利用倒推的方法，求解A到E的最短距離。 具體計(jì)算過程如下：S1： K = 4 有 F4（D1）= 3， F4（D2）= 4， F4（D3）= 3；S2： K = 3 有 F3（C1）= MIN D3（C1，D1）+ F4（D1），D3（C1，D2）+ F4（D2） = MIN 5+3，6+4 = 8 F3（C2）= D3（C2，D1）+ F4（D1）= 5+3 = 8 F3（C3）= D3（C3，D3）+ F4（D3）= 8+3 = 11 F3（C4）= D3（C4，D3）+ F4（D3）= 3+3 = 6S3： K = 2 有 F2（B1）= M

5、IN D2（B1，C1）+ F3（C1），D2（B1，C2）+ F3（C2）， D2（B1，C3）+ F3(C3) = MIN 1+8,6+8,3+11 = 9 F2（B2）= MIN D2（B2，C2）+ F3（C2），D2（B2，C4）+ F3（C4） = MIN 8+8，4+6 = 10S4： K = 1 有 F1（A）= MIN D1（A，B1）+ F2（B1），D1（A，B2）+ F2（B2） = MIN 5+9，3+10 = 13 因此由A點(diǎn)到E點(diǎn)的全過程最短路徑為AB2C4D3E；最短路程長度為13。 從以上過程可以看出，每個階段中，都求出本階段的各個初始狀態(tài)到終點(diǎn)E的最短距離，

6、當(dāng)逆序倒推到過程起點(diǎn)A時，便得到了全過程的最短路徑和最短距離。 在上例的多階段決策問題中，各個階段采取的決策，一般來說是與階段有關(guān)的，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動態(tài)”的含義，我們稱這種解決多階段決策最優(yōu)化的過程為動態(tài)規(guī)劃程序設(shè)計(jì)方法。動態(tài)規(guī)劃的基本概念和基本模型構(gòu)成 現(xiàn)在我們來介紹動態(tài)規(guī)劃的基本概念。1. 階段和階段變量： 用動態(tài)規(guī)劃求解一個問題時，需要將問題的全過程恰當(dāng)?shù)胤殖扇舾蓚€相互聯(lián)系的階段，以便按一定的次序去求解。描述階段的變量稱為階段變量，通常用K表示，階段的劃分一般是根據(jù)時間和空間的自然特征來劃分，同時階段的劃分要便于

7、把問題轉(zhuǎn)化成多階段決策過程，如例題1中，可將其劃分成4個階段，即K = 1，2，3，4。2. 狀態(tài)和狀態(tài)變量： 某一階段的出發(fā)位置稱為狀態(tài)，通常一個階段包含若干狀態(tài)。一般地，狀態(tài)可由變量來描述，用來描述狀態(tài)的變量稱為狀態(tài)變量。如例題1中，C3是一個狀態(tài)變量。3. 決策、決策變量和決策允許集合： 在對問題的處理中作出的每種選擇性的行動就是決策。即從該階段的每一個狀態(tài)出發(fā)，通過一次選擇性的行動轉(zhuǎn)移至下一階段的相應(yīng)狀態(tài)。一個實(shí)際問題可能要有多次決策和多個決策點(diǎn)，在每一個階段的每一個狀態(tài)中都需要有一次決策，決策也可以用變量來描述，稱這種變量為決策變量。在實(shí)際問題中，決策變量的取值往往限制在某一個范圍之

8、內(nèi)，此范圍稱為允許決策集合。如例題1中，F(xiàn)3（C3）就是一個決策變量。4策略和最優(yōu)策略： 所有階段依次排列構(gòu)成問題的全過程。全過程中各階段決策變量所組成的有序總體稱為策略。在實(shí)際問題中，從決策允許集合中找出最優(yōu)效果的策略成為最優(yōu)策略。5. 狀態(tài)轉(zhuǎn)移方程 前一階段的終點(diǎn)就是后一階段的起點(diǎn)，對前一階段的狀態(tài)作出某種決策，產(chǎn)生后一階段的狀態(tài)，這種關(guān)系描述了由k階段到k+1階段狀態(tài)的演變規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。最優(yōu)化原理與無后效性 上面已經(jīng)介紹了動態(tài)規(guī)劃模型的基本組成，現(xiàn)在需要解決的問題是：什么樣的“多階段決策問題”才可以采用動態(tài)規(guī)劃的方法求解。 一般來說，能夠采用動態(tài)規(guī)劃方法求解的問題，必須滿足最優(yōu)

9、化原理和無后效性原則： 1、動態(tài)規(guī)劃的最優(yōu)化原理。作為整個過程的最優(yōu)策略具有：無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略的性質(zhì)。也可以通俗地理解為子問題的局部最優(yōu)將導(dǎo)致整個問題的全局最優(yōu)，即問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，也就是說一個問題的最優(yōu)解只取決于其子問題的最優(yōu)解，而非最優(yōu)解對問題的求解沒有影響。在例題1最短路徑問題中，A到E的最優(yōu)路徑上的任一點(diǎn)到終點(diǎn)E的路徑，也必然是該點(diǎn)到終點(diǎn)E的一條最優(yōu)路徑，即整體優(yōu)化可以分解為若干個局部優(yōu)化。 2、動態(tài)規(guī)劃的無后效性原則。所謂無后效性原則，指的是這樣一種性質(zhì)：某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)

10、及決策的影響。也就是說，“未來與過去無關(guān)”，當(dāng)前的狀態(tài)是此前歷史的一個完整的總結(jié)，此前的歷史只能通過當(dāng)前的狀態(tài)去影響過程未來的演變。在例題1最短路徑問題中，問題被劃分成各個階段之后，階段K中的狀態(tài)只能由階段K+1中的狀態(tài)通過狀態(tài)轉(zhuǎn)移方程得來，與其它狀態(tài)沒有關(guān)系，特別與未發(fā)生的狀態(tài)沒有關(guān)系，例如從Ci到E的最短路徑，只與Ci的位置有關(guān)，它是由Di中的狀態(tài)通過狀態(tài)轉(zhuǎn)移方程得來，與E狀態(tài)，特別是A到Ci的路徑選擇無關(guān)，這就是無后效性。 由此可見，對于不能劃分階段的問題，不能運(yùn)用動態(tài)規(guī)劃來解；對于能劃分階段，但不符合最優(yōu)化原理的，也不能用動態(tài)規(guī)劃來解；既能劃分階段，又符合最優(yōu)化原理的，但不具備無后效性

11、原則，還是不能用動態(tài)規(guī)劃來解；誤用動態(tài)規(guī)劃程序設(shè)計(jì)方法求解會導(dǎo)致錯誤的結(jié)果。四、基本動態(tài)規(guī)劃模型的應(yīng)用【例9.2】數(shù)字金字塔 觀察下面的數(shù)字金字塔。寫一個程序查找從最高點(diǎn)到底部任意處結(jié)束的路徑，使路徑經(jīng)過數(shù)字的和最大。每一步可以從當(dāng)前點(diǎn)走到左下方的點(diǎn)也可以到達(dá)右下方的點(diǎn)。 在上面的樣例中,從13到8到26到15到24的路徑產(chǎn)生了最大的和86。輸入： 第一個行包含R(1= R=1000)，表示行的數(shù)目。 后面每行為這個數(shù)字金字塔特定行包含的整數(shù)。 所有的被供應(yīng)的整數(shù)是非負(fù)的且不大于100。輸出： 單獨(dú)的一行，包含那個可能得到的最大的和。樣例輸入：5 /數(shù)塔層數(shù)1311 812 7 266 14

12、15 812 7 13 24 11樣例輸出：86方法一：搜索 問題要求的是從最高點(diǎn)按照規(guī)則走到最低點(diǎn)的路徑的最大的權(quán)值和，路徑起點(diǎn)終點(diǎn)固定，走法規(guī)則明確，可以考慮用搜索來解決。 定義遞歸函數(shù)void Dfs(int x,int y,int Curr)，其中x,y表示當(dāng)前已從(1,1)走到(x,y)，目前已走路徑上的權(quán)值和為Curr。當(dāng)x=N時，到達(dá)遞歸出口，如果Curr比Ans大，則把Ans更新為Curr；否則向下一行兩個位置行走，即遞歸執(zhí)行Dfs(x+1,y,Curr+Ax+1y)和Dfs(x+1,y+1,Curr+Ax+1y+1)。#include using namespace std;

13、const int MAXN = 1005;int AMAXNMAXN,FMAXNMAXN,N,Ans;void Dfs(int x,int y,int Curr) if (x=N) if (CurrAns)Ans=Curr; return; Dfs(x+1,y,Curr+Ax+1y); Dfs(x+1,y+1,Curr+Ax+1y+1);int main() cin N; for(int i = 1;i = N;i +) for(int j = 1;j Aij; Ans =0; Dfs(1,1,A11); coutAnsendl; return 0; 該方法實(shí)際上是把所有路徑都走了一遍，由于

14、每一條路徑都是由N-1步組成，每一步有“左”、“右”兩種選擇，因此路徑總數(shù)為2N-1，所以該方法的時間復(fù)雜度為O(2N-1)，超時。方法二：記憶化搜索 方法一之所以會超時，是因?yàn)檫M(jìn)行了重復(fù)搜索，如樣例中從(1,1)到(3,2)有“左右”和“右左”兩種不同的路徑，也就是說搜索過程中兩次到達(dá)(3,2)這個位置，那么從(3,2)走到終點(diǎn)的每一條路徑就被搜索了兩次，我們完全可以在第一次搜索(3,2)到終點(diǎn)的路徑時就記錄下(3,2)到終點(diǎn)的最大權(quán)值和，下次再次來到(3,2)時就可以直接調(diào)用這個權(quán)值避免重復(fù)搜索。我們把這種方法稱為記憶化搜索。 記憶化搜索需要對方法一中的搜索進(jìn)行改裝。由于需要記錄從一個點(diǎn)開

15、始到終點(diǎn)的路徑的最大權(quán)值和，因此我們重新定義遞歸函數(shù)Dfs。 定義Dfs(x,y)表示從(x,y)出發(fā)到終點(diǎn)的路徑的最大權(quán)值和，答案就是Dfs(1,1)。計(jì)算Dfs(x,y)時考慮第一步是向左還是向右，我們把所有路徑分成兩大類： 第一步向左：那么從(x,y)出發(fā)到終點(diǎn)的這類路徑就被分成兩個部分，先從(x,y)到(x+1,y)再從(x+1,y)到終點(diǎn)，第一部分固定權(quán)值就是Axy，要使得這種情況的路徑權(quán)值和最大，那么第二部分從(x+1,y)到終點(diǎn)的路徑的權(quán)值和也要最大，這一部分與前面的Dfs(x,y)的定義十分相似，僅僅是參數(shù)不同，因此這一部分可以表示成Dfs(x+1,y)。綜上，第一步向左的路徑

16、最大權(quán)值和為Axy+Dfs(x+1,y)； 第一步向右：這類路徑要求先從(x,y)到(x+1,y+1)再從(x+1,y+1)到終點(diǎn)，分析方法與上面一樣，這類路徑最大權(quán)值和為Axy+Dfs(x+1,y+1)； 為了避免重復(fù)搜索，我們開設(shè)全局?jǐn)?shù)組Fxy記錄從(x,y)出發(fā)到終點(diǎn)路徑的最大權(quán)值和，一開始全部初始化為-1表示未被計(jì)算過。在計(jì)算Dfs(x,y)時，首先查詢Fxy，如果Fxy不等于-1，說明Dfs(x,y)之前已經(jīng)被計(jì)算過，直接返回 Fxy即可，否則計(jì)算出Dfs(x,y)的值并存儲在Fxy中。 #include #include using namespace std; const int

17、 MAXN = 505; int AMAXNMAXN,FMAXNMAXN,N; int Dfs(int x,int y) if (Fxy= -1) if (x=N)Fxy=Axy; else Fxy=Axy+max(Dfs(x+1,y),Dfs(x+1,y+1); return Fxy; int main() cin N; for(int i = 1;i = N;i +) for(int j = 1;j Aij; for(int i = 1;i = N;i +) for(int j = 1;j = i;j +) Fij = -1; Dfs(1,1); cout F11 endl; return

18、 0; 由于Fxy對于每個合法的(x,y)都只計(jì)算過一次，而且計(jì)算是在O(1)內(nèi)完成的，因此時間復(fù)雜度為O(N2)?？梢酝ㄟ^本題。方法三：動態(tài)規(guī)劃(順推法) 方法二通過分析搜索的狀態(tài)重復(fù)調(diào)用自然過渡到記憶化搜索，而記憶化搜索本質(zhì)上已經(jīng)是動態(tài)規(guī)劃了。下面我們完全從動態(tài)規(guī)劃的算法出發(fā)換一個角度給大家展示一下動態(tài)規(guī)劃的解題過程，并提供動態(tài)規(guī)劃的迭代實(shí)現(xiàn)法。確定狀態(tài)： 題目要求從(1,1)出發(fā)到最底層路徑最大權(quán)值和，路徑中是各個點(diǎn)串聯(lián)而成，路徑起點(diǎn)固定，終點(diǎn)和中間點(diǎn)相對不固定。因此定義Fxy表示從(1,1)出發(fā)到達(dá)(x,y)的路徑最大權(quán)值和。最終答案Ans=maxFN1,FN2,.,FNN。確定狀態(tài)轉(zhuǎn)

19、移方程和邊界條件： 不去考慮(1,1)到(x,y)的每一步是如何走的，只考慮最后一步是如何走，根據(jù)最后一步是向左還是向右分成以下兩種情況： 向左：最后一步是從(x-1,y)走到(x,y),此類路徑被分割成兩部分，第一部分是從(1,1)走到(x-1,y)，第二部分是從(x-1,y)走到(x,y)，要計(jì)算此類路徑的最大權(quán)值和，必須用到第一部分的最大權(quán)值和，此部分問題的性質(zhì)與Fxy的定義一樣，就是Fx-1,y，第二部分就是Axy，兩部分相加即得到此類路徑的最大權(quán)值和為Fx-1,y+Ax,y； 向右：最后一步是從(x-1,y-1)走到(x,y),此類路徑被分割成兩部分，第一部分是從(1,1)走到(x-

20、1,y-1)，第二部分是從(x-1,y-1)走到(x,y)，分析方法如上。此類路徑的最大權(quán)值和為Fx-1,y-1+Ax,y； Fxy的計(jì)算需要求出上面兩種情況的最大值。綜上，得到狀態(tài)轉(zhuǎn)移方程如下： Fxy=maxFx-1,y-1,Fx-1y+Ax,y 與遞歸關(guān)系式還需要遞歸終止條件一樣，這里我們需要對邊界進(jìn)行處理以防無限遞歸下去。觀察發(fā)現(xiàn)計(jì)算Fxy時需要用到Fx-1y-1和Fx-1,y，是上一行的元素，隨著遞歸的深入，最終都要用到第一行的元素F11,F11的計(jì)算不能再使用狀態(tài)轉(zhuǎn)移方程來求，而是應(yīng)該直接賦予一個特值A(chǔ)11。這就是邊界條件。綜上得： 狀態(tài)轉(zhuǎn)移方程：Fxy=maxFx-1y-1,Fx

21、-1y+Ax,y 邊界條件：F11=A11 現(xiàn)在讓我們來分析一下該動態(tài)規(guī)劃的正確性，分析該解法是否滿足使用動態(tài)規(guī)劃的兩個前提： 最優(yōu)化原理：這個在分析狀態(tài)轉(zhuǎn)移方程時已經(jīng)分析得比較透徹，明顯是符合最優(yōu)化原理的； 無后效性：狀態(tài)轉(zhuǎn)移方程中，我們只關(guān)心Fx-1y-1與Fx-1y的值，計(jì)算Fx-1y-1時可能有多種不同的決策對應(yīng)著最優(yōu)值，選哪種決策對計(jì)算Fxy的決策沒有影響，F(xiàn)x-1y也是一樣。這就是無后效性。 程序?qū)崿F(xiàn)： 由于狀態(tài)轉(zhuǎn)移方程就是遞歸關(guān)系式，邊界條件就是遞歸終止條件，所以可以用遞歸來完成，遞歸存在重復(fù)調(diào)用，利用記憶化可以解決重復(fù)調(diào)用的問題，方法二已經(jīng)講過。記憶化實(shí)現(xiàn)比較簡單，而且不會計(jì)算

22、無用狀態(tài)，但遞歸也會受到“棧的大小”和“遞推+回歸執(zhí)行方式”的約束，另外記憶化實(shí)現(xiàn)調(diào)用狀態(tài)的順序是按照實(shí)際需求而展開，沒有大局規(guī)劃，不利于進(jìn)一步優(yōu)化。 這里介紹一種迭代法。與分析邊界條件方法相似，計(jì)算Fxy用到狀態(tài)Fx-1y-1與Fx-1y，這些元素在Fxy的上一行，也就是說要計(jì)算第x行的狀態(tài)的值，必須要先把第x-1行元素的值計(jì)算出來，因此我們可以先把第一行元素F11賦為 A11，再從第二行開始按照行遞增的順序計(jì)算出每一行的有效狀態(tài)即可。時間復(fù)雜度為O(N2)。 #include #include using namespace std; const int MAXN = 1005; int

23、AMAXNMAXN,FMAXNMAXN,N; int main() cin N; for(int i = 1;i = N;i +) for(int j = 1;j Aij; F11 = A11; for(int i = 2;i = N;i +) for(int j = 1;j = i;j +) Fij=max(Fi-1j-1,Fi-1j)+Aij; int ans =0; for(int i = 1;i = N;i +) ans = max(ans,FNi); cout ans endl; return 0; 方法四：動態(tài)規(guī)劃(逆推法) 【算法分析】 貪心法往往得不到最優(yōu)解：本題若采用貪心法則

24、：13-11-12-14-13，其和為63,但存在另一條路：13-8-26-15-24，其和為86。 貪心法問題所在：眼光短淺。 動態(tài)規(guī)劃求解：動態(tài)規(guī)劃求解問題的過程歸納為：自頂向下的分析，自底向上計(jì)算。其基本方法是： 劃分階段：按三角形的行，劃分階段，若有n行，則有n-1個階段。 A從根結(jié)點(diǎn)13出發(fā)，選取它的兩個方向中的一條支路，當(dāng)?shù)降箶?shù)第二層時，每個結(jié)點(diǎn)其后繼僅有兩個結(jié)點(diǎn)，可以直接比較，選擇最大值為前進(jìn)方向，從而求得從根結(jié)點(diǎn)開始到底端的最大路徑。 B自底向上計(jì)算：（給出遞推式和終止條件） 從底層開始，本身數(shù)即為最大數(shù)； 倒數(shù)第二層的計(jì)算，取決于底層的數(shù)據(jù)：12+6=18，13+14=27，

25、24+15=39，24+8=32； 倒數(shù)第三層的計(jì)算，取決于底二層計(jì)算的數(shù)據(jù)：27+12=39，39+7=46，39+26=65 倒數(shù)第四層的計(jì)算，取決于底三層計(jì)算的數(shù)據(jù)：46+11=57，65+8=73 最后的路徑：138261524 C數(shù)據(jù)結(jié)構(gòu)及算法設(shè)計(jì) 圖形轉(zhuǎn)化：直角三角形，便于搜索：向下、向右 用三維數(shù)組表示數(shù)塔：axy1表示行、列及結(jié)點(diǎn)本身數(shù)據(jù),axy2能夠取得最大值,axy3表示前進(jìn)的方向0向下，1向右； 算法： 數(shù)組初始化，輸入每個結(jié)點(diǎn)值及初始的最大路徑、前進(jìn)方向?yàn)?； 從倒數(shù)第二層開始向上一層求最大路徑，共循環(huán)N-1次； 從頂向下，輸出路徑：究竟向下還是向右取決于列的值，若列的

26、值比原先多1則向右，否則向下。 參考程序#include#includeusing namespace std;int main()int n,x,y;int a51514;coutn;memset(a,0,sizeof(a);for (x=1;x=n;x+) /輸入數(shù)塔的初始值 for (y=1;yaxy1;axy2=axy1;axy3=0; /路徑走向，默認(rèn)向下 for (x=n-1;x=1;x-) for (y=1;yax+1y+12) /選擇路徑，保留最大路徑值 axy2=axy2+ax+1y2; axy3=0; else axy2=axy2+ax+1y+12; axy3=1; cou

27、tmax=a112endl; /輸出數(shù)塔最大值 y=1; for (x=1;x=n-1;x+) /輸出數(shù)塔最大值的路徑 coutaxy1; y=y+axy3; /下一行的列數(shù) coutany18-26-15-24【例3】求最長不下降序列問題描述： 設(shè)有由n個不相同的整數(shù)組成的數(shù)列，記為:b(1)、b(2)、b(n)且b(i)b(j) (ij)，若存在i1i2i3 ie 且有b(i1)b(i2) b(ie)則稱為長度為e的不下降序列。當(dāng)原數(shù)列出之后，求出最長的不下降序列。 例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，

28、63就是一個長度為7的不下降序列，同時也有7 ，9，16，18，19，21，22，63長度為8的不下降序列。算法分析： 根據(jù)動態(tài)規(guī)劃的原理，由后往前進(jìn)行搜索(當(dāng)然從前往后也一樣)。 1對b(n)來說，由于它是最后一個數(shù)，所以當(dāng)從b(n)開始查找時，只存在長度為1的不下降序列； 2若從b(n-1)開始查找，則存在下面的兩種可能性： 若b(n-1)b(n)則存在長度為1的不下降序列b(n-1)或b(n)。 3一般若從b(i)開始，此時最長不下降序列應(yīng)該按下列方法求出: 在b(i+1),b(i+2),b(n)中，找出一個比b(i)大的且最長的不下降序列，作為它的后繼。數(shù)據(jù)結(jié)構(gòu)： 為算法上的需要，定義

29、一個整數(shù)類型二維數(shù)組b(N,3) 1b(I,1)表示第I個數(shù)的數(shù)值本身； 2b(I,2)表示從I位置到達(dá)N的最長不下降序列長度 3b(I,3)表示從I位置開始最長不下降序列的下一個位置，若bI,3=0則表示后面沒有連接項(xiàng)。 求解過程： 從倒數(shù)第二項(xiàng)開始計(jì)算，后面僅有1項(xiàng)，比較一次，因6315，不符合要求，長度仍為1。 從倒數(shù)第三項(xiàng)開始其后有2項(xiàng)，需做兩次比較，得到目前最長的不下降序列為2，如下表：11121314111213142263152122631521132111300121300一般處理過程是： 在i+1,i+2,n項(xiàng)中，找出比bI,1大的最長長度L以及位置K; 若L0，則bI,2:

30、=L+1;bI,3:=k; 最后本題經(jīng)過計(jì)算，其數(shù)據(jù)存儲表如下：123456789101112131413791638243718441921226315787634352432114348979101311121300初始化:for (i=1;ibi1; bi2=1;bi3=0;下面給出求最長不下降序列的算法:for (i=n-1;i=1;i-) l=0;k=0; for (j=i+1;jbi1)&(bj2l) l=bj2; k=j; if (l0) bi2=l+1; bi3=k; 下面找出最長不下降序列：k=1;for (j=1;jbk2) k=j;最長不下降序列長度為bk2序列while

31、 (k!=0) coutbk1; k=bk3;#includeusing namespace std;int main() int n,i,j,l,k,b20010; coutinput n:n; for (i=1;ibi1; bi2=1;bi3=0; 程序運(yùn)行結(jié)果：輸入：1413 7 9 16 38 24 37 18 44 19 21 22 63 15輸出：max=87 9 16 18 19 21 22 63 for (i=n-1;i=1;i-) /求最長不下降序列 l=0;k=0; for (j=i+1;jbi1)&(bj2l) l=bj2; k=j; if (l0) bi2=l+1;bi

32、3=k; k=1; for (j=1;jbk2) k=j; cout“max=”bk2endl; /輸出結(jié)果 while (k!=0) /輸出最長不下降序列 cout bk1; k=bk3; 【例4】攔截導(dǎo)彈(Noip1999)某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)，導(dǎo)彈數(shù)不超過1000），計(jì)算這套系

33、統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。樣例：INPUT OUTPUT389 207 155 300 299 170 158 65 6（最多能攔截的導(dǎo)彈數(shù)） 2（攔截所有導(dǎo)彈最少要配的系統(tǒng)數(shù)）【算法分析】 第一問即經(jīng)典的最長不下降子序列問題，可以用一般的DP算法，也可以用高效算法，但這個題的數(shù)據(jù)規(guī)模不需要。用ax表示原序列中第x個元素，bx表示長度為x的不下降子序列的長度，當(dāng)處理第ax時，可查找它可以連接到長度最大為多少的不下降子序列后（即與部分bx比較）。假設(shè)可以連到長度最大為maxx的不下降子序列后，則bx:=maxx+1。b數(shù)組被賦值的最大值就是第一問的

34、答案。 第二問用貪心法即可。每顆導(dǎo)彈來襲時，使用能攔截這顆導(dǎo)彈的防御系統(tǒng)中上一次攔截導(dǎo)彈高度最低的那一套來攔截。若不存在符合這一條件的系統(tǒng)，則使用一套新系統(tǒng)?！緟⒖汲绦颉浚樛品ǎ?include#include#includeusing namespace std;int main() freopen(in.txt, r, stdin); freopen(out.txt, w, stdout); int i,j,k,x,n,maxx,m,a10000,b10000,h10000; i=1;n=0;m=0; memset(a,0,sizeof(a); memset(b,0,sizeof(b);

35、 memset(h,0,sizeof(h); while (cinai) maxx=0; for (j=1;j=ai) if (bjmaxx) maxx=bj; bi=maxx+1; if (bim) m=bi; x=0; for (k=1;k=ai) if (x=0) x=k; else if (hkhx) x=k; /若有多套系統(tǒng)可攔截，則選擇攔截高度最低的 if (x=0) n+;x=n; /新增一套導(dǎo)彈攔截系統(tǒng) hx=ai; i+; coutmendlnE。試用動態(tài)規(guī)劃的最優(yōu)化原理求出A-E的最省費(fèi)用。交通圖1 交通圖2 如圖：求v1到v10的最短路徑長度及最短路徑。【樣例輸入】sho

36、rt.in100 2 5 1 0 0 0 0 0 00 0 0 0 12 14 0 0 0 00 0 0 0 6 10 4 0 0 00 0 0 0 13 12 11 0 0 00 0 0 0 0 0 0 3 9 00 0 0 0 0 0 0 6 5 00 0 0 0 0 0 0 0 10 00 0 0 0 0 0 0 0 0 50 0 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0 0【樣例輸出】short.outminlong=191 3 5 8 10【算法分析】逆推法 設(shè)fi表示點(diǎn)i到v10的最短路徑長度，則 f10=0 fi=min aix+fx 當(dāng)aix0 ,ix=

37、n時#includeusing namespace std;#include#includeint main() long n,i,j,x,f100,c100,a100100; memset(a,0,sizeof(a); memset(c,0,sizeof(c); cinn; for (i=1;i=n;i+) /輸入各個城市之間距離 for (j=1;jaij; for (i=1;i=1;i-) /從終點(diǎn)往前逆推，計(jì)算最短路徑 for (x=i+1;x0)&(fx!=1000000)&(fiaix+fx) /aix0表示城市i和城市x通路 fi=aix+fx; /城市i到終點(diǎn)最短路徑的值 ci

38、=x; coutminlong=f1endl; /輸出最短路徑的值 x=1;while (x!=0) /輸出路過的各個城市 coutx ; x=cx; coutendl; 【例6】挖地雷【問題描述】在一個地圖上有N個地窖（N=200）,每個地窖中埋有一定數(shù)量的地雷。同時，給出地窖之間的連接路徑，并規(guī)定路徑都是單向的,也不存在可以從一個地窖出發(fā)經(jīng)過若干地窖后又回到原來地窖的路徑。某人可以從任一處開始挖地雷，然后沿著指出的連接往下挖（僅能選擇一條路徑），當(dāng)無連接時挖地雷工作結(jié)束。設(shè)計(jì)一個挖地雷的方案，使他能挖到最多的地雷。【輸入格式】 N /地窖的個數(shù) W1，W2，WN /每個地窖中的地雷數(shù) X1

39、，Y1 /表示從X1可到Y(jié)1 X2，Y2 0，0 /表示輸入結(jié)束【輸出格式】 K1-K2-Kv /挖地雷的順序 MAX /最多挖出的地雷數(shù)【輸入樣例】Mine.in 6 5 10 20 5 4 5 1 2 1 4 2 4 3 4 4 5 4 6 5 6 0 0【輸出樣例】Mine.out 3-4-5-6 34【算法分析】本題是一個經(jīng)典的動態(tài)規(guī)劃問題。很明顯，題目規(guī)定所有路徑都是單向的，所以滿足無后效性原則和最優(yōu)化原理。設(shè)Wi為第i個地窖所藏有的地雷數(shù)，Aij表示第i個地窖與第j個地窖之間是否有通路，F(xiàn)i為從第i個地窖開始最多可以挖出的地雷數(shù)，則有如下遞歸式：Fi=max Wi+ Fj (ij=

40、n , Aij=true)邊界：Fn=Wn于是就可以通過遞推的方法，從后F(n)往前逐個找出所有的Fi，再從中找一個最大的即為問題2的解。對于具體所走的路徑（問題1），可以通過一個向后的鏈接來實(shí)現(xiàn)?！緟⒖汲绦颉?include#includeusing namespace std;int main() long f201=0,w201,c201=0; bool a201201=0; long i,j,n,x,y,l,k,maxx; memset(f,0,sizeof(f); memset(c,0,sizeof(c); memset(a,false,sizeof(a); cinn; for (i

41、=1;iwi; /輸入每個地窖中的地雷數(shù) do cinxy; /表示從X可到Y(jié) if (x!=0)&(y!=0) axy=true; while (x!=0)|(y!=0); fn=wn; /從后Fn往前逐個找出所有的Fi for (i=n-1;i=1;i-) l=0;k=0; for (j=i+1;jl) l=fj; k=j; fi=l+wi; /保存從第i個地窖起能挖到最大地雷數(shù) ci=k; /k地窖是i地窖最優(yōu)路徑 k=1; for (j=2;jfk) k=j; maxx=fk; coutk; k=ck; while (k!=0) /輸出挖地雷的順序 cout-k; k=ck; cout

42、endl; coutmaxxendl; /輸出最多挖出的地雷數(shù)【例7】友好城市 【問題描述】 Palmia國有一條橫貫東西的大河，河有筆直的南北兩岸，岸上各有位置各不相同的N個城市。北岸的每個城市有且僅有一個友好城市在南岸，而且不同城市的友好城市不相同。 每對友好城市都向政府申請?jiān)诤由祥_辟一條直線航道連接兩個城市，但是由于河上霧太大，政府決定避免任意兩條航道交叉，以避免事故。編程幫助政府做出一些批準(zhǔn)和拒絕申請的決定，使得在保證任意兩條航線不相交的情況下，被批準(zhǔn)的申請盡量多?！据斎敫袷健?第1行，一個整數(shù)N(1=N=5000)，表示城市數(shù)。 第2行到第n+1行，每行兩個整數(shù)，中間用1個空格隔開，

43、分別表示南岸和北岸的一對友好城市的坐標(biāo)。(0=xi=10000)【輸出格式】 僅一行，輸出一個整數(shù)，表示政府所能批準(zhǔn)的最多申請數(shù)?！据斎霕永?7 22 4 2 6 10 3 15 12 9 8 17 17 4 2【輸出樣例】【算法分析】 我們將每對友好城市看成一條線段，則這道題的描述化為：有N條線段，問最少去掉多少條線，可以使剩下的線段互不交叉？ 第一，以北岸為線的起點(diǎn)而南岸為線的終點(diǎn)；先將所有的線按照起點(diǎn)坐標(biāo)值從小到大排序，按照每條線的終點(diǎn)坐標(biāo)計(jì)算交叉數(shù)：求線I的交叉數(shù)AI，則檢查所有1.I-1條線，若線J( 1= J I)的終點(diǎn)值大于線I的終點(diǎn)值，則線I與線J相交。AI與AJ同時加1。整

44、個搜索量最大為5000*5000。 第二，將A數(shù)組從大到小排序，每刪除一條線，則將與之相交的線的A值減1，重復(fù)這個過程，直到所有A值都為0。此時剩下的線則全不交叉。 4如上數(shù)據(jù)，則可得下面結(jié)果：編號 南岸 北岸 交叉數(shù)11322242331244515523 此時，1、2、3航線的交叉數(shù)都一樣，如果刪去的是3、5線，則剩下的1、2、4線互不相交，最多航線數(shù)為3；但如果刪去的是2、3，則還要刪去第5線才符合要求，此時的最多航線數(shù)為2，不是最優(yōu)解。 于是，我們從上面的分析中再深入，將航線按起點(diǎn)坐標(biāo)排好序后，如上所述，在本題中，只要線J的起點(diǎn)小于線I的起點(diǎn)，同時它的終點(diǎn)也小于線I的終點(diǎn)，則線J和線I

45、不相交。因此，求所有線中最多能有多少條線不相交，實(shí)際上是從終點(diǎn)坐標(biāo)值數(shù)列中求一個最長不下降序列。這就把題目轉(zhuǎn)化為一個非常典型的動態(tài)規(guī)劃題目了。 求最長不下降序列的規(guī)劃方程如下： L(Si)=maxL(Sj)+1；1 = j i且 Sj Si。Si為航線的終點(diǎn)坐標(biāo)值。從以上分析過程可以得出：當(dāng)我們拿到一道題時，不要急于求解，而應(yīng)先將題目的表面現(xiàn)象一層層象剝竹筍一樣去掉，只留下最實(shí)質(zhì)的內(nèi)容。這時再來設(shè)計(jì)算法，往往能事半功倍?！纠?】合唱隊(duì)形【問題描述】N位同學(xué)站成一排，音樂老師要請其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號為1

46、, 2, , K，他們的身高分別為T1, T2, , TK，則他們的身高滿足T1 T2 Ti+1 TK (1iK)。你的任務(wù)是，已知所有N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。【輸入文件】輸入文件chorus.in的第一行是一個整數(shù)N（2 N 100），表示同學(xué)的總數(shù)。第二行有n個整數(shù)，用空格分隔，第i個整數(shù)Ti（130 Ti 230）是第i位同學(xué)的身高（厘米）?！据敵鑫募枯敵鑫募horus.out包括一行，這一行只包含一個整數(shù)，就是最少需要幾位同學(xué)出列?！緲永斎搿?8 186 186 150 200 160 130 197 220【樣例輸出】 4【數(shù)據(jù)

47、規(guī)?！?對于50%的數(shù)據(jù)，保證有n 20；對于全部的數(shù)據(jù)，保證有n100?！舅惴ǚ治觥课覀儼凑沼勺蠖液陀捎叶蟮捻樞?，將n個同學(xué)的身高排成數(shù)列。如何分別在這兩個數(shù)列中尋求遞增的、未必連續(xù)的最長子序列，就成為問題的關(guān)鍵。設(shè)a 為身高序列，其中ai為同學(xué)i的身高；b 為由左而右身高遞增的人數(shù)序列，其中 bi為同學(xué)1同學(xué)i間（包括同學(xué)i）身高滿足遞增順序的最多人數(shù)。顯然bi=maxbj|同學(xué)j的身高同學(xué)i的身高+1；c為由右而左身高遞增的人數(shù)序列，其中ci為同學(xué)n同學(xué)i間（包括同學(xué)i）身高滿足遞增順序的最多人數(shù)。顯然ci=maxcj|同學(xué)j的身高同學(xué)i的身高+1；由上述狀態(tài)轉(zhuǎn)移方程可知，計(jì)算合唱隊(duì)

48、形的問題具備了最優(yōu)子結(jié)構(gòu)性質(zhì)(要使bi和ci最大，子問題的解bj和ck必須最大(1ji-1 ，i+1kn)和重迭子問題的性質(zhì)(為求得bi和ci，必須一一查閱子問題的解b1bi-1和ci+1cn)，因此可采用動態(tài)程序設(shè)計(jì)的方法求解。顯然，合唱隊(duì)的人數(shù)為maxbi+ci-1(公式中同學(xué)i被重復(fù)計(jì)算，因此減1)，n減去合唱隊(duì)人數(shù)即為解。具體算法如下：#include#includeusing namespace std;int a200,b200,c200;main() int n,i,j,maxx; cinn; /讀學(xué)生數(shù) memset(b,0,sizeof(b); /身高滿足遞增順序的兩個隊(duì)列初

49、始化 memset(c,0,sizeof(c); for (i=1;iai; for (i=1;i=n;i+) /按照由左而右的順序計(jì)算b序列 bi=1; for (j=1;jaj)&(bj+1bi) bi=bj+1; for (i=n;i=1;i-) /按照由右而左的順序計(jì)算c序列 ci=1; for (j=i+1;j=n;j+) if (ajci) ci=cj+1; maxx=0; /計(jì)算合唱隊(duì)的人數(shù)max(其中1人被重復(fù)計(jì)算) for (i=1;imaxx) maxx=bi+ci; coutn-maxx+1endl; /輸出出列人數(shù) 這個算法的時間復(fù)雜度為O(n2)，在1秒時限內(nèi)可解決n

50、100范圍內(nèi)的問題。例9.9 最長公共子序列【問題描述】 一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X=，則另一序列Z是X的子序列是指存在一個嚴(yán)格遞增的下標(biāo)序列,使得對于所有j=1,2,k有： Xij=Zj 例如，序列Z=是序列X=的子序列,相應(yīng)的遞增下標(biāo)序列為。給定兩個序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。例如，若X和Y，則序列是X和Y的一個公共子序列,序列 也是X和Y的一個公共子序列。而且，后者是X和Y的一個最長公共子序列因?yàn)閄和Y沒有長度大于4的公共子序列。 給定兩個序列X和Y=要求找出X和Y的一個最長公

51、共子序列。【輸入格式】 輸入共有兩行。每行為一個由大寫字母構(gòu)成的長度不超過200的字符串，表示序列X和Y?！据敵龈袷健?輸出第一行為一個非負(fù)整數(shù)。表示所求得的最長公共子序列的長度。若不存在公共子序列則輸出文件僅有一行輸出一個整數(shù)0。否則在輸出文件的第二行輸出所求得的最長公共子序列(也用一個大寫字母組成的字符串表示)。若符合條件的最長公共子序列不止一個，只需輸出其中任意一個?！緲永斎搿?ABCBDAB BDCABA【樣例輸出】 4提示: 最長公共子串（Longest Common Substring）和最長公共子序列（Longest Common Subsequence，LCS）的區(qū)別為：子串

52、是串的一個連續(xù)的部分，子序列則是從不改變序列的順序，而從序列中去掉任意的元素而獲得新的序列；也就是說，子串中字符的位置必須是連續(xù)的，子序列則可以不必連續(xù)。字符串長度小于等于1000。分析： 與最長不下降子序列(LIS)類似的，我們可以以子序列的結(jié)尾作為狀態(tài)，但現(xiàn)在有兩個子序列，那么直接以兩個子序列當(dāng)前的結(jié)尾作為狀態(tài)即可。確定狀態(tài)： 設(shè)Fxy表示S1.x與T1.y的最長公共子序列的長度。答案為F|S|T|。確定狀態(tài)轉(zhuǎn)移方程和邊界條件： 分三種情況來考慮： Sx不在公共子序列中：該情況下Fxy=Fx-1y； Ty不在公共子序列中：該情況下Fxy=Fxy-1； Sx=Ty，Sx與Ty在公共子序列中：

53、該情況下，F(xiàn)xy=Fx-1y-1+1。 Fxy取上述三種情況的最大值。綜上： 狀態(tài)轉(zhuǎn)移方程：Fxy=maxFx-1y,Fxy-1,Fx-1y-1+1,其中第三種情況要滿足Sx=Ty； 邊界條件：F0y=0,Fx0=0。程序?qū)崿F(xiàn)： 計(jì)算Fxy時用到 Fx-1y-1,Fx-1y,Fxy-1這些狀態(tài)，它們要么在Fxy的上一行，要么在Fxy的左邊。因此預(yù)處理出第0行，然后按照行從小到大、同一行按照列從小到大的順序來計(jì)算就可以用迭代法計(jì)算出來。時間復(fù)雜度為O(|S|*|T|)。【參考程序】 #include #include #include using namespace std; const int MAXN =