動態(tài)規(guī)劃-劉宗凡

動態(tài)規(guī)劃四會中學劉宗凡多階段決策過程最優(yōu)化問題在現(xiàn)實生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。因此各個階段決策的選取不能任意確定，它依賴于當前面臨的狀態(tài)，又影響以后的發(fā)展。當各個階段決策確定以后，就組成一個決策序列，因此也就確定了整個過程的一條活動路線。這種把一個問題看做是一個前后關聯(lián)具有鏈狀結構的多階段過程就稱為多階段決策過程，這種問題稱為多階段決策最優(yōu)化問題。引子：最短路徑問題下圖給出了一個地圖，地圖中每個頂點代表一個城市，兩個城市間的連線代表道路，連線上的數(shù)值代表道路長度。現(xiàn)在，我們想從城市a到達城市E。怎樣走才能使得路徑最短，最短路徑的長度是多少？窮舉法(回溯法)3*9*6*2=342條路徑路徑增多，將呈幾何級數(shù)增長每次除了已經訪問過的城市外，其他城市都要訪問，所以時間復雜度為O（n?。?，這是一個“指數(shù)級”的算法。在求b1到E的最短路徑的時候，先求出從C2到E的最短路徑；而在求從b2剄E的最短路徑的時候，又求了一遍從C2剄E的最短路徑。也就是說，從C2到E的最短路徑求了兩遍。同樣可以發(fā)現(xiàn)，在求從Cl、C2剄E的最短路徑的過程中，從Dl到E的最短路徑也被求了兩遍。而在整個程序中，從Dl到E的最短路徑被求了四遍，這是多么大的一個浪費啊！如果在求解的過程中，同時將求得的最短路徑的距離“記錄在案”，以便將來隨時調用，則可以避免這種重復計算。

C1C3D1AB1B3B2D2EC22511214106104131112396581052求從A到E的最短路徑問題，可以轉化為三個性質完全相同，但規(guī)模較小的子問題，即分別從B1、B2、B3到E的最短路徑問題。記從Bi(i=1,2,3)到E的最短路徑為S(Bi)，則從A到E的最短距離S(A)可以表示為：

同樣，計算S(B1)又可以歸結為性質完全相同，但規(guī)模更小的問題，即分別求C1，C2，C3到E的最短路徑問題S(Ci)(i=1,2,3)，而求S(Ci)又可以歸結為求S(D1)和S(D2)這兩個子問題。從圖可以看出，在這個問題中，S(D1)和S(D2)是以知的，它們分別是：S(D1)=5，S(D2)=2因而，可以從這兩個值開始，逆向遞歸計算S(A)的值。S(C1)=8 且如果到達C1，則下一站應到達D1；S(C2)=7 且如果到達C2，則下一站應到達D2；S(C3)=12且如果到達C3，則下一站應到達D2；S(B1)=20 且如果到達B1，則下一站應到達C1；S(B2)=14 且如果到達B2，則下一站應到達C1；S(B3)=19 且如果到達B3，則下一站應到達C2；由此，可以計算S(A)：820052712141919C1C3D1AB1B3B2D2EC22511214106104131112396581052最后，可以得到：從A到E的最短路徑為AB2C1D1E?？梢钥吹剑陨戏椒ú粌H得到了從A到D的最短路徑，同時，也得到了從圖中任一點到E的最短路徑。

動態(tài)規(guī)劃的基本特征

1、問題具有多階段決策的特征。階段可以按時間劃分，也可以按空間劃分。2、每一階段都有相應的“狀態(tài)”與之對應，描述狀態(tài)的量稱為“狀態(tài)變量”。3、每一階段都面臨一個決策，選擇不同的決策將會導致下一階段不同的狀態(tài)，同時，不同的決策將會導致這一階段不同的目標函數(shù)值。4、每一階段的最優(yōu)解問題可以遞歸地歸結為下一階段各個可能狀態(tài)的最優(yōu)解問題，各子問題與原問題具有完全相同的結構。能否構造這樣的遞推歸結，是解決動態(tài)規(guī)劃問題的關鍵。這種遞推歸結的過程，稱為“不變嵌入”。

動態(tài)規(guī)劃的幾個概念:階段：據(jù)空間順序或時間順序對問題的求解劃分階段。狀態(tài)：描述事物的性質，不同事物有不同的性質，因而用不同的狀態(tài)來刻畫。對問題的求解狀態(tài)的描述是分階段的。決策：根據(jù)題意要求，對每個階段所做出的某種選擇性操作。狀態(tài)轉移方程：用數(shù)學公式描述與階段相關的狀態(tài)間的演變規(guī)律。動態(tài)規(guī)劃的指導思想是：在做每一步決策時，列出各種可能的局部解，之后依據(jù)某種判定條件，舍棄那些肯定不能得到最優(yōu)解的局部解。這樣，在每一步都經過篩選，以每一步都是最優(yōu)的來保證全局是最優(yōu)的。篩選相當于最大限度地有效剪枝（從搜索角度看），效率會十分高。但它又不同于貪心法。貪心法只能做到局部最優(yōu)，不能保證全局最優(yōu)，因為有些問題不符合最優(yōu)性原理。兩種算法的差別在于，貪心法產生一個按貪心策略形成的判定序列，該序列不保證解是全局最優(yōu)的。而動態(tài)規(guī)劃會產生許多判定序列，再按最優(yōu)性原理對這些序列加以篩選，去除那些非局部最優(yōu)的子序列。程序設計的一般格式；fork←n-1downto1do{枚舉階段}fors取遍所有狀態(tài)doforu取遍所有決策do；這里是一種從目標狀態(tài)往回推的逆序求法，適用于目標狀態(tài)確定的問題。而很多試題是確定了初始狀態(tài)的。當然，對于初始狀態(tài)確定的問題，我們也可以采用從初始狀態(tài)出發(fā)往前推的順序求法。事實上，這種方法對我們來說要更為直觀、更易設計一些，從而更多地出現(xiàn)在我們的解題過程中。由于動態(tài)程序設計方法的模式性比較強，因此應該把主要精力放在狀態(tài)定義、階段劃分和狀態(tài)轉移方程的設計上。一旦這些問題解決了，事情成功了一大半。適用DP求解問題的特征1、最優(yōu)子結構：當問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結構性質。

2、重疊子問題：在用遞歸算法自頂向下解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。使用動態(tài)規(guī)劃的原則(一)最優(yōu)化原理(最優(yōu)子結構原理):無論過去的狀態(tài)和決策如何，對前面的決策所形成的當前狀態(tài)而言，余下的諸決策必須構成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的?？梢酝ㄋ椎乩斫鉃樽訂栴}的局部最優(yōu)將導致整個問題的全局最優(yōu)。在最短路徑問題中，A到E的最優(yōu)路徑上的任一點到終點E的路徑也必然是該點到終點E的一條最優(yōu)路徑，滿足最優(yōu)化原理。也就是說一個問題的最優(yōu)解只取決于其子問題的最優(yōu)解，非最優(yōu)解對問題的求解沒有影響。如圖，若路線I和J是A到C的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線J必是從B到C的最優(yōu)路線。這可用反證法證明：假設有另一路徑J’是B到C的最優(yōu)路徑，則A到C的路線取I和J’比I和J更優(yōu)，這與原命題矛盾。從而證明J必是B到C的最優(yōu)路徑。

最優(yōu)化原理是動態(tài)規(guī)劃的基礎，任何問題，如果失去了最優(yōu)化原理的支持，就不可能用動態(tài)規(guī)劃方法計算。ABCIJJ’使用動態(tài)規(guī)劃的原則(二)無后效性原則：某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)及決策的影響。也就是說，“未來與過去無關”，當前的狀態(tài)是此前歷史的一個完整總結，此前的歷史只能通過當前的狀態(tài)去影響過程未來的演變。具體地說，如果一個問題被劃分各個階段之后，階段I中的狀態(tài)只能由階段I-1中的狀態(tài)通過狀態(tài)轉移方程得來，與其他狀態(tài)沒有關系，特別是與未發(fā)生的狀態(tài)沒有關系，這就是無后效性。

應用動態(tài)規(guī)劃要注意階段的劃分是關鍵，必須依據(jù)題意分析，尋求合理的劃分階段(子問題)方法。而每個子問題是一個比原問題簡單得多的優(yōu)化問題。而且每個子問題的求解中，均利用它的一個后部子問題的最優(yōu)化結果，直到最后一個子問題所得最優(yōu)解，它就是原問題的最優(yōu)解。例1：數(shù)字三角形問題：給定一個具有N層的數(shù)字三角形如下圖，從頂至底有多條路徑，每一步可沿左斜線向下或沿右斜線向下，路徑所經過的數(shù)字之和為路徑得分，請求出最大路徑得分。

(1)1<三角形行數(shù)<100

(2)三角形中數(shù)字為1..99

如輸入：5

7

38

810

2774

45265

輸出：30738810

277445265回溯算法programsjx;

constmaxn=10;

var

a:array[1..maxn,1..maxn]ofinteger;

max:longint;

n,i,j:integer;

fname:string;inputf:text;proceduretry(x,y,dep:integer;sum:longint);

begin

if(dep=n)then

begin

ifsum>maxthen

max:=sum;

exit

end;

try(x+1,y,dep+1,sum+a[x+1,y]);

try(x+1,y+1,dep+1,sum+a[x+1,y+1]);

end;beginreadln(fname);assign(inputf,fname);reset(inputf);readln(inputf,n);fori:=1tondoforj:=1toidoread(inputf,a[i,j]);max:=0;try(1,1,1,a[1,1]);writeln(max);end.由以上算法不難算出其時間復雜度為2^n，而本題N最大為100，顯然當N比較大時是無法在規(guī)定時間內出解的，但本題又很難找出理想的剪枝方法。問題分析：假設從頂至數(shù)字三角形的某一未知的所有路徑中，所經過的數(shù)字總和最大的那條路徑我們稱之為未知的最大路徑。由于問題規(guī)定每一步只能沿直線或右斜線向下走，若要走到某一位置，則其前一未知必為其左上方或正上方兩個位置之一。由此可知，當前未知的最優(yōu)路徑必定與其左上方或正上方兩個位置的最優(yōu)路徑有關，且來自于其中更優(yōu)的一個。我們可以用一個二維數(shù)組maxsum記錄每個位置的最優(yōu)路徑的數(shù)字總和。計算maxsum數(shù)組可以像計算楊輝三角一樣用逐行遞推的方法實現(xiàn)。動態(tài)轉移方程：f(i,j)=max{f(i-1,j),f(j-1,j-1)}+a[i,j]f[1,1]:=a[1,1];fori:=2tondobeginf[i,1]:=a[i,1]+f[i-1,1];forj:=2toidoiff[i-1,j-1]>f[i-1,j]

thenf[i,j]:=a[i,j]+f[i-1,j-1]elsef[i,j]:=a[i,j]+f[i-1,j];end;maxsum:=0;fori:=1tondoiff[n,i]>maxsumthenmaxsum:=f[n,i];writeln(maxsum);end.constmaxn=100;varfname:string;inputf:text;n,i,j:integer;a:array[1..maxn,1..maxn]ofinteger;f:array[1..maxn,1..maxn]ofinteger;maxsum:integer;beginreadln(n);fori:=1tondoforj:=1toidoread(inputf,a[i,j]);fillchar(f,sizeof(f),0);思考：方格取數(shù)如下圖，n*m的方格，每個方格存放了一個正整數(shù)，一個卒子從左上角走到右下角，走的過程中只能向下或向右，到達每個方格就取出該方格內的數(shù)，走到右下角所取得數(shù)之和稱之為效益，求效益的最大值。3898288383199809288387219123271838828263578提示：Fij=max{fi,j-1,fi-1,j}+aij,邊界條件：F1,1=a1,1answer=Fnm例2：0/1背包問題一個旅行者有一個最多能用m公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1，W2，...,Wn,它們的價值分別為C1,C2,...,Cn.若每種物品只有一件求旅行者能獲得最大總價值。輸入樣例：

11 {weight}

4 {n}

2467 {W[i]}

6101213 {P[i]}輸出樣例：

23分析最優(yōu)子結構性質分析：我們首先自問一個簡單的問題：在最優(yōu)解中，是否包括了xi(I=1..n)？只可能有兩種情況： 1.包括有。那么何妨另起爐灶，換一個更簡單的問題來思考：在背包載重為m-wi的情況下，在其它n-1件物品中挑選，使得價值和最大。等把這個子問題求出后，再加上vi的價值就是整個問題的最優(yōu)解了。 2.沒包括。那么就當xi根本不存在，直接解物品數(shù)量為n-1，背包載重為m的子問題。子問題的最優(yōu)解就是問題的最優(yōu)解。這樣，我們就看出，無論那種情況，在問題的最優(yōu)解中，都包含著子問題的最優(yōu)解。分析遞歸地定義問題的解：請思考本題各數(shù)據(jù)的存儲結構？ 價值：一維數(shù)組v[1..n] 重量：一維數(shù)組w[1..n]因為所求問題是n件物品，背包限重為m，隨著問題規(guī)模的增減，n和m都在變化，因此很自然地想到把件數(shù)和背包限重都作為自變量。定義函數(shù)f(i,j)為在1~i件物品中選若干件裝入限重為j的背包中的最大價值和。那么根據(jù)前面的討論中關于第I件物品是否裝入了背包的情況分析，我們得出關系式： 當?shù)趇件物品要裝入背包時，f(i,j):=i-1件物品，限重為j-w[I]的最優(yōu)解+v[I],即： f(i,j):=f(i-1,j-w[i])+v[i] 當然，第i件物品要裝入是有條件限制的，是什么？ 第i件物品重量小于等于背包限重，即w[i]<=j 當?shù)趇件物品不裝入背包時，f(i,j):=i-1件物品，限重為m的最優(yōu)解，即： f(i,j):=f(i-1,j)分析現(xiàn)在已經求得裝入或者不裝入第i件物品的限重為J的背包的最大價值，那么接下來應該做什么？比較這兩種情況下誰的價值更大，更大者為當前問題的最優(yōu)解。 iff(i,j)’>f(i,j)’’then f(i,j):=f(i,j)’else f(i,j):=f(i,j)’’;上述遞歸式的邊界條件是什么？我們知道f(i,j)的i和J都有一個取值范圍。1<=i<=n,0<=J<=m.邊界條件就是當問題規(guī)模縮小到自變量下界時的函數(shù)的取值情況。當背包限重為0時，無法放任何物品，此時所有的f(i,0):=0(1<=I<=n).這就是邊界條件。分析根據(jù)上述遞歸式已經可以遞歸地求出最優(yōu)解了。請自行編程練習。下面按自底向上的方式求解本題。在按自底向上的動態(tài)規(guī)劃方式求解問題時，其實主要就是做一件事： 按問題規(guī)模從小到大地求解問題，把每階段求得的問題的最優(yōu)解保存在表格（數(shù)組）中，以便在下一階段求解更大的問題時，可以直接查表引用子問題的最優(yōu)解。首先分析階段。將n件物品放入背包，故可以把階段劃分為n個。把在前I件物品中選取物品放入背包作為第I個階段。再分析狀態(tài)。第I個階段的狀態(tài)J是對前I件物品進行取舍后得到的背包的重量。顯然狀態(tài)J滿足條件0<=J<=m，即是說狀態(tài)J的取值范圍在0到背包的最大限重之間。注意，由于物品重量均為正整數(shù)，所以狀態(tài)J是0~m之間的整數(shù)，可以進行枚舉。分析這樣，在第I個階段就有m+1個問題需要求解，分別是f[I,0],f[I,1],…,f[I,m]。由于前面分析可知所有的f[I,0]均為0，因此實際需要求解的是m個問題。而這m個問題的求解基礎是第I-1個階段的m個子問題。這些子問題的最優(yōu)解已經先于此時求得，保存在f[I-1,1],f[I-1,2],…,f[I-1,m]中，現(xiàn)在只需要直接引用它們的值就可以了。這就是動態(tài)規(guī)劃自底向上的體現(xiàn)。最后分析決策。前面的分析中已經明確了決策的個數(shù)，大家說是多少個？只有兩個：在前I件物品中，限重為J的條件下，裝入第I件物品還是不裝入第I件物品。比較這兩種情況的價值和，誰大誰就是最優(yōu)解。分析總結一下：階段：1~n個初始階段：f[I,0]:=0(1<=I<=n);f[0,m]:=0狀態(tài)：1~m個決策：2個。現(xiàn)在編程沒有任何困難了吧。測試數(shù)據(jù)：

10,3

3,4

4,5

5,6這個最大價值是怎么得來的呢?從背包容量為0開始,1號物品先試,0,1,2,的容量都不能放.所以置0,背包容量為3則里面放4.這樣,這一排背包容量為4,5,6,....10的時候，最佳方案都是放4.假如1號物品放入背包.則再看2號物品.當背包容量為3的時候，最佳方案還是上一排的最價方案c為4.而背包容量為5的時候，則最佳方案為自己的重量5.背包容量為7的時候，很顯然是5加上一個值了。加誰??很顯然是7-4=3的時候.上一排c3的最佳方案是4.所以。總的最佳方案是5+4為9.這樣.一排一排推下去。最右下放的數(shù)據(jù)就是最大的價值了。(注意第3排的背包容量為7的時候,最佳方案不是本身的6.而是上一排的9.說明這時候3號物品沒有被選.選的是1,2號物品.所以得9.)０１２３４５６７８９1011０１２３４手工驗證f(I,j)公式的正確性０１２３４５６７８９1011０000000000000１006666666666２00661010161616161616３00661010121218182222４00661010121313192323手工驗證f(I,j)公式的正確性分析顯然這個題可用深度優(yōu)先方法對每件物品進行枚舉(選或不選用0,1控制).程序簡單,但是當n的值很大的時候不能滿足時間要求，時間復雜度為O（2n）。按遞歸的思想我們可以把問題分解為子問題,使用遞歸函數(shù)即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態(tài)轉移方程便是：動態(tài)轉移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}F[n][m]即為最優(yōu)解，邊界條件為f[0][j]＝0

，f[i][0]=0;

“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉化為“前i-1件物品放入容量為v的背包中”，價值為f[i-1][v]；如果放第i件物品，那么問題就轉化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。constmaxm=200;maxn=30;

typear=array[1..maxn]ofinteger;

varm,n,j,i:integer;

c,w:ar;

f:array[0..maxn,0..maxm]ofinteger;

functionmax(x,y:integer):integer;

begin

ifx>ythenmax:=xelsemax:=y;

end;

begin

readln(m,n);

fori:=1tondo

readln(w[i],c[i]);

fori:=1tomdof(0,i):=0;

fori:=1tondof(i,0):=0;

fori:=1tondo

forj:=1tomdo

begin

ifj>=w[i]

thenf[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])

elsef[i,j]:=f[i-1,j];

end;

writeln(f[n,m]);

end.思考：完全背包問題一個旅行者有一個最多能用m公斤的背包，現(xiàn)在有n種物品，每件的重量分別是W1，W2，...,Wn,每件的價值分別為C1,C2,...,Cn.若的每種物品的件數(shù)足夠多.求旅行者能獲得的最大總價值。本問題的數(shù)學模型如下：設f(x)表示重量不超過x公斤的最大價值，則f(x）=max{f(x-w[i])+c[i]}

當x>=w[i]1<=i<=n程序如下:（順推法）programknapsack04;

constmaxm=2000;maxn=30;

typear=array[0..maxn]ofinteger;

varm,n,j,i,t:integer;

c,w:ar;

f:array[0..maxm]ofinteger;

begin

readln(m,n);

fori:=1tondo

readln(w[i],c[i]);

f(0):=0;

fori:=1tomdo

forj:=1tondo

begin

ifi>=w[j]

thent:=f[i-w[j]]+c[j];

ift>f[i]thenf[i]:=t

end;

writeln(f[m]);

end.例3：(NOIP2007)3.守望者的逃離問題描述】惡魔獵手尤迫安野心勃勃.他背叛了暗夜精靈，率深藏在海底的那加企圖叛變：守望者在與尤迪安的交鋒中遭遇了圍殺.被困在一個荒蕪的大島上。為了殺死守望者，尤迪安開始對這個荒島施咒，這座島很快就會沉下去，到那時，刀上的所有人都會遇難：守望者的跑步速度，為17m/s，以這樣的速度是無法逃離荒島的。慶幸的是守望者擁有閃爍法術，可在1s內移動60m，不過每次使用閃爍法術都會消耗魔法值10點。守望者的魔法值恢復的速度為4點/s，只有處在原地休息狀態(tài)時才能恢復?，F(xiàn)在已知守望者的魔法初值M，他所在的初始位置與島的出口之間的距離S，島沉沒的時間T。你的任務是寫一個程序幫助守望者計算如何在最短的時間內逃離荒島，若不能逃出，則輸出守望者在剩下的時間內能走的最遠距離。注意:守望者跑步、閃爍或休息活動均以秒(s)為單位。且每次活動的持續(xù)時間為整數(shù)秒。距離的單位為米(m)。【輸入】輸入文件escape.in僅一行，包括空格隔開的三個非負整數(shù)M，S，T?！据敵觥枯敵鑫募scape.out包含兩行:第1行為字符串"Yes"或"No"(區(qū)分大小寫)，即守望者是否能逃離荒島。第2行包含一個整數(shù)，第一行為"Yes"(區(qū)分大小寫）時表示守望著逃離荒島的最短時間第一行為"No"(區(qū)分大小寫)時表示守望者能走的最遠距離?！据斎胼敵鰳永?】【輸入輸出樣例2】【限制】30%的數(shù)據(jù)滿足:1<=T<=10，1<=S<=10050%的數(shù)據(jù)滿足:1<=T<=1000，1<=S<=10000100%的數(shù)據(jù)滿足:1<=T<=300000，0<=M<=10001<=S<=10^8escape.in escape.out392004No197escape.in escape.out3625510 Yes6【試題分析】(方法一：貪心)分析題意歸納出每個時間單位的三種策略

A.休息（可恢復4點魔法值）

B.跑步（可移動17的距離，不恢復魔法值）

C.閃爍（可移動60的距離，并消耗10點魔法值）這樣很容易聯(lián)想到一個貪心規(guī)則：

A.當魔法值>=10肯定要用閃爍移動。（魔法儲存起來做什么？現(xiàn)在不用，以后也要用的，不用是浪費）

B.考慮魔法值<10時，是休息等待魔法恢復后使用閃爍移動還是直接跑步的效果好。

其實很簡單（假設我花5s鐘來休息，那就可以積累20點魔法值，也就可以使用2次閃爍，移動距離為60*2=120，而總的時間花的是5+2=7；但如果這7s我們全用來跑步，則移動距離為17*7=119，顯然沒有用魔法劃算。既然這樣，那就不斷用魔法吧。）

C.但其實在島快沉沒的最后階段，可能出現(xiàn)魔法恢復后的值尚不足以連續(xù)使用閃爍，而跑步實際更優(yōu)。這就是本題的一個陷阱。即便是貪心也需考慮最后的這一段，應該跑步而不是休息并閃爍。所以單獨處理即可。

（但這樣的貪心很容易忽略邊界情況，例如假設我用完初始魔法值還剩6的魔法值，則只需再休息1s就可以使用魔法了，而不一定是7s的那種情況。）【試題分析】(方法二：動態(tài)規(guī)劃)典型的動態(tài)規(guī)劃。

設f[i,j]為第i秒，魔法值為j時可行的最大距離。

f[i,j]:=max{f[i-1,j]+17,f[i-1,j-10]+60,f[i-1,j+4]}(當j≥10時);

f[i,j]:=max{f[i-1,j]+17,f[i-1,j+4]}(當j<10時)

按題目所說，最大魔法值為1000，最大時間為300000秒，那么需要1000*300000=300000000=3*10^9的數(shù)組，空間會溢出，所以使用兩個一維數(shù)組來迭代，只需2*1000的數(shù)組，但是時間復雜度為O(t*m)，有可能會超時?！驹囶}分析】(方法三：貪心+動態(tài)規(guī)劃)1.對于初始魔法，先采用貪心思想，將其全部用完直至魔法值不足以使用閃爍為止（即M<10）。這樣就可以將問題規(guī)?？s小，轉化為魔法初值為m（<10），

2.用f[i,j]來表示i時間魔法值為j可以達到的最遠距離。假設貪心后還剩余s的路程，而全程為ss,剩余魔法為m,剩余時間為t,則很容易根據(jù)題目信息列出方程：

f[0,m]=ss-s

f[i,j]=max{f[i-1,j-4],f[i-1,j]+17,f[i-1,j+10]+60}

(1<=i<=t)

例4：求最長不下降序列問題描述：設有一個正整數(shù)的序列：b1,b2,…bn,對于下標i1<i2<…ih,若有bi1<bi2<…<bih，則稱存在一個長度為h的不下降序列。例如，下列數(shù) 13791638242738444921526315對于下標i1=1,i2=4,i3=5,i4=9,i5=13,且滿足 13<16<38<44<63則存在長度為5的不下降序列。但是，我們看到還存在其它的不下降序列。如 7<9<16<18<19<21<22<63則存在長度為8的不下降序列。問題：當給定b1,b2,…bn后，求出最長的不下降序列h及這個序列中的各個數(shù)。最長不下降序列-分析動態(tài)規(guī)劃的難點之一：怎樣定義問題？你首先要能定義出問題是什么，才能進一步定義出子問題是什么，然后才能證明或者直觀地感覺問題與子問題之間是否存在最優(yōu)子結構性質。從前往后分析。從序列長度為1開始，逐步放大序列長度，2，3，4……看看要求的結果的變化規(guī)律。我們可能會很直接地想到，把問題定義成當前最長不下降序列。序列長度 序列 當前最長不下降序列長度 1 13 1 2 137 1 3 1379 2 4 137916 3 5 13791638 4 6 1379163824 4（24<38,長度不增加） 7 137916382427 ?(憑什么計算出當前值？) 由于當前記錄的最長不下降序列是791638，而實際上應該有了更長的子序列79162427。我們定義F(i)為原始序列長度為i的最長不下降序列，則F(i)只有一個子問題F(i-1)，即原始序列長度為i-1的最長不下降序列。而且我們無法得出問題與子問題之間的“最優(yōu)子結構”性質。13791638242738444921526315最長不下降序列-分析重新思考關于問題的定義。我們定義問題F(i)為以bi結束的最長不下降序列。則得到如下的分析結果：下標i 序列 F(i) 前趨結點下標13 1 1137 1 21379 2 2137916 3 313791638 4 41379163824 4 4137916382427 5 613791638242738 6 7 13791638242738444921526315最長不下降序列-分析當我們定義問題F(i)為以bi結束的最長不下降序列時，則問題F(i)有i-1個子問題：F(1),F(2),…,F(i-1)。我們要使F(i)最大，則要找到一個F(i)最大的子問題，且同時滿足Bj<=Bi(1<j<i)，這時F(i):=F(j)+1例如F(4)有3個子問題，分別是F(1),F(2),F(3),它們都滿足bj<bi的條件，而最大的F(j)=2,因此F(4):=F(3)+1=3,而它的前趨結點下標是j13791638242738444921526315下標I 序列 F(i) 前趨結點下標13 1 1137 1 21379 2 2137916 3 313791638 4 41379163824 4 4137916382427 5 613791638242738 6 7最長不下降序列-分析這樣定義問題，我們就看到了“最優(yōu)子結構”性質。因此可以應用動態(tài)規(guī)劃方法求解問題。請你分析本問題的重疊子問題性質。請你遞歸地定義問題的解。 F(i)=Max{F(j)+1|j<I且bj<=bi}本遞歸式的邊界條件是什么？ F(1)=1請你思考本題要求的結果是F(n)嗎？如果不是，那么最后要求的結果怎樣利用用動態(tài)規(guī)劃求得的問題和子問題的值得到？怎樣輸出顯示最長不下降序列的各個結點？13791638242738444921526315最長不下降序列-討論如果從后向前分析原始序列，會得到正確的結果嗎？又該怎樣定義問題？寫出從后向前求最長不下降序列的程序。13791638242738444921526315programupdown;{從前往后推}

vars,c,a:array[1..1000]ofinteger;

b:array[1..1000,1..1000]ofboolean;

t,i,j,k,n:integer;

begin

readln(n);

fillchar(a,sizeof(a),0);

fillchar(s,sizeof(s),0);

fillchar(b,sizeof(b),false);

fori:=1tondoreadln(a[i]);

s[1]:=1;

fori:=2tondo

begin

s[i]:=1;k:=i;

forj:=1toi-1do

if(a[j]<=a[i])and(s[j]+1>s[i])thenbegin

s[i]:=s[j]+1;k:=j;

end;

b[i,k]:=true;

end;

k:=0;j:=0;

fori:=ndownto1do

ifs[i]>kthenbegink:=s[i];j:=i;end;

i:=j;

writeln(k);

while(i>=1)and(s[j]>0)do

begin

c[s[j]]:=a[i];dec(s[j]);

fort:=i-1downto1do

if(b[i,t]=true)and(s[t]=s[j])thenbegini:=t;break;end;;

end;

fori:=1tokdowrite('',c[i]);

gramlongestnondecorder;{從后往前推}

type

int=longint;

var

a,b,c:array[1..50]ofint;

m,n,i,j,p,q:int;

max:int;

begin

readln(n);

fori:=1tondoread(a[i]);

b[n]:=1;c[n]:=0;

fori:=n-1downto1do

begin

max:=0;p:=0;

forj:=i+1tondo

if(a[i]<=a[j])and(b[j]>max)then

begin

p:=j;

max:=b[j];

end;

ifp<>0then

begin

b[i]:=b[p]+1;

c[i]:=p;

end

elsebeginb[i]:=1;c[i]:=0;end

end;

max:=0;p:=0;

fori:=1tondo

ifb[i]>maxthen

begin

max:=b[i];

p:=i

end;

whilep<>0dobeginwrite(a[p],'');p:=c[p];end;writeln;

writeln('max','',max);

end.思考：攔截導彈(NOIP1999提高組)某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。但是這種導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導彈。

輸入導彈依次飛來的高度（雷達給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計算這套系統(tǒng)最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統(tǒng)。

樣例：INPUT38920715530029917015865OUTPUT6（最多能攔截的導彈數(shù)）2（要攔截所有導彈最少要配備的系統(tǒng)數(shù)）[問題分析]

第一部分是要求輸入數(shù)據(jù)串中的一個最長不上升序列的長度，可使用遞推的方法，具體做法是從序列的第一個元素開始，依次求出以第i個元素為最后一個元素時的最長不上升序列的長度len(i)，遞推公式為len(1)=1，len(i)=max(len(j)+1)，其中i>1，j=1,2,…i-1，且j同時要滿足條件：序列中第j個元素大于等于第i個元素。第二部分比較有意思。由于它緊接著第一問，所以很容易受前面的影響，采取多次求最長不上升序列的辦法，然后得出總次數(shù)，其實這是不對的。要舉反例并不難，比如長為7的高度序列“7541632”，最長不上升序列為“75432”，用多次求最長不上升序列的結果為3套系統(tǒng)；但其實只要2套，分別擊落“7541”與“632”。那么，正確的做法又是什么呢？我們的目標是用最少的系統(tǒng)擊落所有導彈，至于系統(tǒng)之間怎么分配導彈數(shù)目則無關緊要；上面錯誤的想法正是承襲了“一套系統(tǒng)盡量多攔截導彈”的思維定勢，忽視了最優(yōu)解中各個系統(tǒng)攔截數(shù)較為平均的情況，本質上是一種貪心算法。如果從每套系統(tǒng)攔截的導彈方面來想行不通的話，我們就應該換一個思路，從攔截某個導彈所選的系統(tǒng)入手。題目告訴我們，已有系統(tǒng)目前的瞄準高度必須不低于來犯導彈高度，所以，當已有的系統(tǒng)均無法攔截該導彈時，就不得不啟用新系統(tǒng)。如果已有系統(tǒng)中有一個能攔截該導彈，我們是應該繼續(xù)使用它，還是另起爐灶呢？事實是：無論用哪套系統(tǒng)，只要攔截了這枚導彈，那么系統(tǒng)的瞄準高度就等于導彈高度，這一點對舊的或新的系統(tǒng)都適用。而新系統(tǒng)能攔截的導彈高度最高，即新系統(tǒng)的性能優(yōu)于任意一套已使用的系統(tǒng)。既然如此，我們當然應該選擇已有的系統(tǒng)。如果已有系統(tǒng)中有多個可以攔截該導彈，究竟選哪一個呢？當前瞄準高度較高的系統(tǒng)的“潛力”較大，而瞄準高度較低的系統(tǒng)則不同，它能打下的導彈別的系統(tǒng)也能打下，它夠不到的導彈卻未必是別的系統(tǒng)所夠不到的。所以，當有多個系統(tǒng)供選擇時，要選瞄準高度最低的使用，當然瞄準高度同時也要大于等于來犯導彈高度。解題時，用一個數(shù)組記下已有系統(tǒng)的當前瞄準高度，數(shù)據(jù)個數(shù)就是系統(tǒng)數(shù)目。constmax=1000;vari,j,current,maxlong,minheight,select,tail,total:longint;height,longest,sys:array[1..max]oflongint;line:string;beginwrite('Inputtestdata:');readln(line);i:=1;whilei<=length(line)dobeginwhile(i<=length(line))and(line[i]='')doi:=i+1;current:=0;while(i<=length(line))and(line[i]<>'')dobegincurrent:=current*10+ord(line[i])-ord('0');i:=i+1end;total:=total+1;height[total]:=currentend;longest[1]:=1;fori:=2tototaldobeginmaxlong:=1;forj:=1toi-1dobeginifheight[i]<=height[j]theniflongest[j]+1>maxlongthenmaxlong:=longest[j]+1;

longest[i]:=maxlongend;end;maxlong:=longest[1];fori:=2tototaldoiflongest[i]>maxlongthenmaxlong:=longest[i];writeln(maxlong);sys[1]:=height[1];tail:=1;fori:=2tototaldobeginminheight:=maxint;forj:=1totaildoifsys[j]>height[i]thenifsys[j]<minheightthenbeginminheight:=sys[j];select:=jend;ifminheight=maxintthenbegintail:=tail+1;sys[tail]:=height[i]endelsesys[select]:=height[i]end;writeln(tail)end.例5：過河(NOIP2005)

在河上有一座獨木橋，一只青蛙想沿著獨木橋從河的一側跳到另一側。在橋上有一些石子，青蛙很討厭踩在這些石子上。由于橋的長度和青蛙一次跳過的距離都是正整數(shù)，我們可以把獨木橋上青蛙可能到達的點看成數(shù)軸上的一串整點：0，1，……，L（其中L是橋的長度）。坐標為0的點表示橋的起點，坐標為L的點表示橋的終點。青蛙從橋的起點開始，不停的向終點方向跳躍。一次跳躍的距離是S到T之間的任意正整數(shù)（包括S,T）。當青蛙跳到或跳過坐標為L的點時，就算青蛙已經跳出了獨木橋。題目給出獨木橋的長度L，青蛙跳躍的距離范圍S,T，橋上石子的位置。你的任務是確定青蛙要想過河，最少需要踩到的石子數(shù)。【輸入文件】輸入文件river.in的第一行有一個正整數(shù)L（1<=L<=109），表示獨木橋的長度。第二行有三個正整數(shù)S，T，M，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個數(shù)，其中1<=S<=T<=10，1<=M<=100。第三行有M個不同的正整數(shù)分別表示這M個石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點和終點處沒有石子）。所有相鄰的整數(shù)之間用一個空格隔開?！据敵鑫募枯敵鑫募iver.out只包括一個整數(shù)，表示青蛙過河最少需要踩到的石子數(shù)?！緲永斎搿?023523567【樣例輸出】2【數(shù)據(jù)規(guī)模】對于30%的數(shù)據(jù)，L<=10000；對于全部的數(shù)據(jù)，L<=109。分析由于不能往回跳，很容易想到用動態(tài)規(guī)劃解決這個題目。設f(i)表示跳到第i個點需要踩到的最少石子數(shù)，則很容易寫出動態(tài)規(guī)劃的狀態(tài)轉移方程:時間復雜度是O(L*(T-S))，但本題的L高達109，根本無法承受!

進一步分析我們先來考慮這樣一個問題：長度為k的一段沒有石子的獨木橋，判斷是否存在一種跳法從一端正好跳到另一端。若S<T，事實上對于某個可跳步長區(qū)間[S,T]，必然存在一個MaxK使得任何k>=MaxK，都可以從一端正好跳到另一端。題設中1<=S<=T<=10，經過簡單推導或者程序驗證就可以發(fā)現(xiàn)，取MaxK=100就能滿足所有區(qū)間。于是我們可以分兩種情況討論：1.S=T時： 這時候由于每一步只能按固定步長跳，所以若第i個位置上有石子并且imodS=0那么這個石子就一定要被踩到。這是我們只需要統(tǒng)計石子的位置中哪些是S的倍數(shù)即可。復雜度O(M)2.S<T時： 首先我們作如下處理：若存在某兩個相鄰石子之間的空白區(qū)域長度>MaxK+2*T，我們就將這段區(qū)域縮短成長度為MaxK+2*T?？梢宰C明處理之后的最優(yōu)值和原先的最優(yōu)值相同。 ab如上圖所示，白色點表示連續(xù)的一長段長度大于MaxK+2*T的空地，黑色點表示石子。設原先的最優(yōu)解中，白色段的第一個被跳到的位置a，最后一個被跳到的位置是b，則在做壓縮處理之后，a和b的距離仍然大于MaxK，由上面的結論可知，必存在一種跳法從a正好跳到b，而且不經過任何石子。所以原來的最優(yōu)解必然在處理之后的最優(yōu)解解集中。經過這樣的壓縮處理，獨木橋的長度L’最多為(M+1)*(MaxK+2*T)+M，大約12000左右。壓縮之后再用先前的動態(tài)規(guī)劃求解，復雜度就簡化成了O(L’*(T-S))，已經可以在時限內出解了。這樣本題就得到了解決。例6：花店櫥窗布置問題(FLOWER)問題描述

假設你想以最美觀的方式布置花店的櫥窗?，F(xiàn)在你有F束不同品種的花束，同時你也有至少同樣數(shù)量的花瓶被按順序擺成一行。這些花瓶的位置固定于架子上，并從1至V順序編號，V是花瓶的數(shù)目，從左至右排列，則最左邊的是花瓶1，最右邊的是花瓶V。花束可以移動，并且每束花用1至F間的整數(shù)唯一標識。標識花束的整數(shù)決定了花束在花瓶中的順序，如果I＜J，則令花束I必須放在花束J左邊的花瓶中。

例如，假設一束杜鵑花的標識數(shù)為1，一束秋海棠的標識數(shù)為2，一束康乃馨的標識數(shù)為3，所有的花束在放入花瓶時必須保持其標識數(shù)的順序，即：杜鵑花必須放在秋海棠左邊的花瓶中，秋海棠必須放在康乃馨左邊的花瓶中。如果花瓶的數(shù)目大于花束的數(shù)目。則多余的花瓶必須空置，且每個花瓶中只能放一束花。

每一個花瓶都具有各自的特點。因此，當各個花瓶中放入不同的花束時，會產生不同的美學效果，并以美學值（一個整數(shù)）來表示，空置花瓶的美學值為零。

在上述例子中，花瓶與花束的不同搭配所具有的美學值，如下表所示。

花

瓶12345花束1(杜鵑花)

723-5-24162(秋海棠)

521-4

10233(康乃馨)-21

5-4-2020例如，根據(jù)上表，杜鵑花放在花瓶2中，會顯得非常好看；但若放在花瓶4中則顯得十分難看。

為取得最佳美學效果，你必須在保持花束順序的前提下，使花束的擺放取得最大的美學值。如果有不止一種的擺放方式具有最大的美學值，則其中任何一直擺放方式都可以接受，但你只要輸出任意一種擺放方式。（2）假設條件

1≤F≤100，其中F為花束的數(shù)量，花束編號從1至F。

F≤V≤100，其中V是花瓶的數(shù)量。

-50≤Aij≤50，其中Aij是花束i在花瓶j中的美學值。

（3）輸入

輸入文件是正文文件（textfile），文件名是flower.inp。

第一行包含兩個數(shù)：F，V。

隨后的F行中，每行包含V個整數(shù)，Aij即為輸入文件中第（i+1）行中的第j個數(shù)。

（4）輸出

輸出文件必須是名為flower.out的正文文件，文件應包含兩行：

第一行是程序所產生擺放方式的美學值。

第二行必須用F個數(shù)表示擺放方式，即該行的第K個數(shù)表示花束K所在的花瓶的編號。（5）例子

flower.in：

35

723–5–2416

521-41023

-215-4-2020

flower.out：

53

245

（6）評分

程序必須在2秒中內運行完畢。

在每個測試點中，完全正確者才能得分。

花店櫥窗布置（IOI’99）花瓶12345花束1、杜鵑花723-5-24162、秋海棠521-410233、康乃馨-215-4-2020花瓶12345花束1、杜鵑花72323-∞-∞2、秋海棠-∞282833-∞3、康乃馨-∞-∞242453F[i，j]=前i束花放入前j個花瓶內的最大美學價值（花i不一定必須插在瓶j內）。目標:f[n,m]花瓶12345花束1、杜鵑花723-5-24162、秋海棠521-410233、康乃馨-215-4-2020a[I,j]f[I,j]分析：方法一A[i,j]=花i放入j瓶的美學價值。F[i，j]=前i束花放入前j個花瓶內的最大美學價值（花i不一定必須插在瓶j內）。計算F[I,j]有兩種情況：1):花i放入第j個花瓶中：F[i，j]=f[i-1,j-1]+a[i,j]2):花i不放入第j個花瓶中,只能放在前j-1個花瓶內：F[i，j]=f[i,j-1]動態(tài)轉移方程：F[i，j]＝max｛f[i-1,j-1]+a[i,j]，f[i,j-1]｝初始化：f[i,i]=a[1,1]+a[2,2]+…+a[i,i];目標：f[n,m]容易理解的方法：fillchar(f,sizeof(f),0);f[1,1]:=a[1,1];fori:=2tondof[i,i]:=f[i-1,i-1]+a[i,i];fori:=1tondoforj:=i+1tom-(n-i)dof[i,j]:=max(f[i,j-1],f[i-1,j-1]+a[i,j]);分析：方法二：a,f:array[0..maxn,0..maxm]ofinteger;a[i,j]表示第i束花插到第j個花瓶中的價值；f[i,j]表示第i束花插到第j個花瓶后，也就是說：第i束花插在第ｊ個花瓶，前i-1束花插在前ｊ-１個花瓶內所獲得的價值和的最大值。動態(tài)轉移方程：

f[i,j]＝max{f[i-1,k]}+a[i,j](i-1<=k<=j-1)枚舉第i-1束花所在的花瓶k初始化：f[0,0]=0;f[i,0]=-∞(1<=i<=n)目標：max{f[n,i]}(1<=i<=m)算法設計flower一題是IOI99第一天第一題，該題如用組合的方法處理，將會造成超時。正確的方法是用動態(tài)規(guī)劃，考慮角度為一束一束地增加花束，假設用b(i,j)表示1～i束花放在1到j之間的花瓶中的最大美學值，其中i<=j，則b(i,j)=max(b[i-1,k-1]+A[i,k])，其中i<=k<=j，A(i,k)的含義參見題目。輸出結果時，顯然使得b[F,k]取得總的最大美觀值的第一個k值就是第F束花應該擺放的花瓶位置，將總的最大美觀值減去A[i,k]的值即得到前k-1束花放在前k-1個瓶中的最大美觀值，依次使用同樣的方法就可求出每一束花應該擺放的花瓶號。由于這一過程是倒推出來的，所以程序中用遞歸程序來實現(xiàn)。programex8_4(input,output);

constmax=100;

var

f,v,i,j,k,cmax,current,max_val:integer;

table,val:array[1..max,1..max]ofinteger;

fname:string;

fin:text;

procedureprint(current,max_val:integer);

vari:integer;

begin

ifcurrent>0then

begin

i:=current;

whileval[current,i]<>max_valdoi:=i+1;

print(current-1,max_val-table[current,i]);

write(i,'')

end

end;begin

write('Inputthefilenameoftestdata:');

readln(fname);

assign(fin,fname);

reset(fin);

readln(fin,f,v);

fori:=1tofdo

begin

forj:=1tovdoread(fin,table[i,j]);

readln(fin);

end;

close(fin);

max_val:=-maxint;

fori:=1tovdo

ifmax_val<table[1,i]

thenbeginval[1,i]:=table[1,i];max_val:=table[1,i]end

elseval[1,i]:=table[1,i];fori:=2tofdo

forj:=itov-f+ido

begin

max_val:=-maxint;

fork:=i-1toj-1do

begin

cmax:=-maxint;

forcurrent:=k+1tojdo

iftable[i,current]>cmaxthencmax:=table[i,current];

ifcmax+val[i-1,k]>max_valthenmax_val:=cmax+val[i-1,k]

end;

val[i,j]:=max_val

end;

max_val:=-maxint;

fori:=ftovdo

ifval[f,i]>max_valthenmax_val:=val[f,i];

writeln(max_val);

print(f,max_val);

writeln

end.

思考：機器分配（HNOI’95）問題描述總公司擁有高效生產設備M臺，準備分給下屬的N個公司。各分公司若獲得這些設備，可以為國家提供一定的盈利。問：如何分配這M臺設備才能使國家得到的盈利最大？求出最大盈利值。其中M《=15，N〈=10。分配原則：每個公司有權獲得任意數(shù)目的設備，但總臺數(shù)不得超過總設備數(shù)M。保存數(shù)據(jù)的文件名從鍵盤輸入。數(shù)據(jù)文件格式為：第一行保存兩個數(shù)，第一個數(shù)是設備臺數(shù)M，第二個數(shù)是分公司數(shù)N。接下來是一個M*N的矩陣，表明了第I個公司分配J臺機器的盈利。樣例輸入：34101526302032384312202735樣例輸出：54分析：F[i,j]:前i個公司分配j臺機器獲得的最大盈利。試試看：F[1,1],f[1,2]……f[1,m].F[2,1],f[2,2]……f[2,m].。。。動態(tài)轉移方程：f[i,j]=max{f[i-1,j-k]+a[i,k]}(1<=i<=n,1<=j<=m,0<=k<=j)初始：f[1,i]:=a[1,i]i:1……m目標：f[n,m]fori:=1tomdof[1,i]:=a[1,i];fori:=2tondoforj:=1tomdofork:=0tojdof[i,j]:=max(f[i,j],f[i-1,j-k]+a[i,k]);格式一：fori:=1tondoforj:=1tomdofork:=0tojdof[i,j]:=max(f[i,j],f[i-1,j-k]+a[i,k]);格式二：動態(tài)歸劃與一般遞推的異同動態(tài)規(guī)劃和一般遞推相同點在于:

1、無后效性

2、有邊界條件不同點在于:

1、一般遞推邊界條件很明顯,動態(tài)規(guī)劃邊界條件比較隱蔽,容易被忽視

2、一般遞推數(shù)學性較強,動態(tài)規(guī)劃數(shù)學性相對較弱

3、一般遞推一般不劃分階段,動態(tài)規(guī)劃一般有較為明顯的階段動態(tài)規(guī)劃一般遞推關系遞推關系在實際應用中，許多問題的階段劃分并不明顯，這時如果刻意地劃分階段法反而麻煩。一般來說，只要該問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解（即滿足最優(yōu)子化原理），則可以考慮用動態(tài)規(guī)劃解決。動態(tài)規(guī)劃將原來具有指數(shù)級復雜度的搜索算法改進成了具有多項式時間的算法。其中的關鍵在于解決冗余，這是動態(tài)規(guī)劃算法的根本目的。動態(tài)規(guī)劃實質上是一種以空間換時間的技術，它在實現(xiàn)的過程中，不得不存儲產生過程中的各種狀態(tài)，所以它的空間復雜度要大于其它的算法。DP與其它算法的同異動態(tài)規(guī)劃的實質是分治思想和解決冗余，因此，動態(tài)規(guī)劃是一種將問題實例分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復的子問題，以解決最優(yōu)化問題的算法策略。由此可知，動態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，并通過求解子問題產生一個全局最優(yōu)解。其中貪心法的當前選擇可能要依賴已經作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個子問題是獨立的(即不包含公共的子問題)，因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。但不足的是，如果當前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達到全局最優(yōu)解；如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題。動態(tài)規(guī)劃法所針對的問題有一個顯著的特征，即它所對應的子問題樹中的子問題呈現(xiàn)大量的重復。動態(tài)規(guī)劃法的關鍵就在于，對于重復出現(xiàn)的子問題，只在第一次遇到時加以求解，并把答案保存起來，讓以后再遇到時直接引用，不必重新求解。

例7：最長公共子序列LCS一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X=<x1,x2,…,xm>，則另一序列Z=<z1,z2,…,zk>是X的子序列是指存在一個嚴格遞增的下標序列<i1,i2,…,ik>，使得對于所有j=1,2,…,k有例如，序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列，相應的遞增下標序列為<2,3,5,7>。給定兩個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。例如，若X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>，則序列<B,C,A>是X和Y的一個公共子序列，序列<B,C,B,A>也是X和Y的一個公共子序列。而且，后者是X和Y的一個最長公共子序列，因為X和Y沒有長度大于4的公共子序列。給定兩個序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>，要求找出X和Y的一個最長公共子序列。輸入輸入文件共有兩行，每行為一個由大寫字母構成的長度不超過200的字符串，表示序列X和Y。輸出輸出文件第一行為一個非負整數(shù)，表示所求得的最長公共子序列的長度，若不存在公共子序列，則輸出文件僅有一行輸出一個整數(shù)0，否則在輸出文件的第二行輸出所求得的最長公共子序列(也用一個大寫字母組成的字符串表示)，若符合條件的最長公共子序列不止一個，只需輸出其中任意的一個。樣例lcs.inABCBDABBDCABAlcs.out4BCBA評分標準若輸出的最長公共子序列的長度正確，則得5分；若輸出的最長公共子序列也正確，則再得5分。窮舉解最長公共子序列問題時最容易想到的算法是窮舉搜索法，即對X的每一個子序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列，并且在檢查過程中選出最長的公共子序列。X的所有子序列都檢查過后即可求出X和Y的最長公共子序列。X的一個子序列相應于下標序列{1,2,…,m}的一個子序列，因此，X共有2m個不同子序列，從而窮舉搜索法需要指數(shù)時間。定理:LCS的最優(yōu)子結構性質設序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的一個最長公共子序列Z=<z1,z2,…,zk>，則：若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長公共子序列；若xm≠yn且zk≠xm，則Z是Xm-1和Y的最長公共子序列；若xm≠yn且zk≠yn，則Z是X和Yn-1的最長公共子序列。其中Xm-1=<x1,x2,…,xm-1>，Yn-1=<y1,y2,…,yn-1>，

Zk-1=<z1,z2,…,zk-1>。分析描述LCS問題最優(yōu)解的結構首先．我們給出一個字符串“前綴”的概念：給定一個字符串X=<X1,X2,…,Xm>，對I=0,1,…,m，定義X的第i個前綴為例如，如果X＝＜A，B，C，B，D，A，B＞，則而則為空串。兩個輸入字符串X和Y的所有前綴組成了LCS問題的子問題空間。由此我們發(fā)現(xiàn)LCS問題的最優(yōu)子結構的三個性質：設X＝<X1,X2,…,Xm>和Y＝<Y1,Y2,…,Yn>為兩個輸入字符串，并設X和Y的最長公共子串為Z=<Z1,Z2,…,Zk>性質1：如果Xm=Yn，則Zk=Xm=Yn，且也就是說，如果兩個字符串最后一位字符相等，則它們的最長公共子串的最后一位就是這個字符，并且公共子串的第k-1個前綴是兩個字符串前綴的最長公共子串分析舉例說明： X=<A,B,E,…,G,F> Y=<C,D,H,…,K,F>因X和Y的最后一位相等，則它們的最長公共子串Z的最后一位必為F，即有Z=<……,F>的樣式。并且Z’=<……>是X’=<A,B,E,…,G>和Y’=<C,D,H,…,K>的最長公共子串。性質2：也就是說，如果兩個字符串最后一位不等，則它們的最長公共子串Z的最后一位不等于X的最后一位，就意味著Z是X的前綴與Y的最長公共子串。舉例說明：X=<A,B,E,…,G,M>Y=<C,D,H,…,K,S>Z=<……,F>因X和Y最后一位不等，X和它的子串的最后一位也不等，則Z是X’=<A,B,E…,G>和Y的最長公共子串分析-最優(yōu)子結構性質3：也就是說，如果兩個字符串最后一位不等，則它們的最長公共子串Z的最后一位不等于Y的最后一位，就意味著Z是X與Y的前綴的最長公共子串。舉例說明：X=<A,B,E,…,G,W>Y=<C,D,H,…,K,I>Z=<……,F>因X和Y最后一位不等，Y和它的子串的最后一位也不等，則Z是X和Y’=<C,D,H,…K>的最長公共子串由此可見，字符串X和Y的一個最長公共子串也是包含了兩個字符串的前綴的一個最長公共子串，這就說明了LCS問題具備最優(yōu)子結構性質。證明1.用反證法。若zk≠xm，則<z1,z2,…,zk,xm>是X和Y的長度為k十1的公共子序列。這與Z是X和Y的一個最長公共子序列矛盾。因此，必有zk=xm=yn。由此可知Zk-1是Xm-1和Yn-1的一個長度為k-1的公共子序列。若Xm-1和Yn-1有一個長度大于k-1的公共子序