動態(tài)規(guī)劃經(jīng)典問題---數(shù)塔問題132101443220有一個由正整數(shù)組成的三角形，第一行只有一個數(shù)，除了最下行之外每個數(shù)的左下方和右下方各有一個數(shù)，如下圖所示。從第一行的數(shù)開始，每次可以往左下或右下走一格，直到走到三角形底層，把沿途經(jīng)過的數(shù)全部加起來作為得分。如何走，使得這個得分最大？經(jīng)典問題---數(shù)塔問題這是一個決策問題：每次選一個方向（左/右）行走。到底朝哪個方向走，取決于從左走能取到最大值還是從右走能取到最大值。最容易想到的是貪心算法：每次選擇數(shù)字較大的方向走。

1----3---10----3，錯誤貪心法在此問題無法保證得到最優(yōu)解。經(jīng)典問題---數(shù)塔問題暴力搜索，列舉出所有可能的路徑再比較，得出和最大的路徑。intd[100][100],n;intdfs(intx,inty)//x,y數(shù)組下標(biāo)，函數(shù)返回從d[x][y]開始走到最后一層的最大和{ if(x==n)//邊界條件 { returnd[x][y]; } else { intleft=dfs(x+1,y);//從左下方的數(shù)字開始能夠得到的最大和 intright=dfs(x+1,y+1);//右下方能得到的最大和 returnd[x][y]+max(left,right); }}//main函數(shù)內(nèi)調(diào)用dfs(1,1)經(jīng)典問題---數(shù)塔問題暴力搜索存在大量重復(fù)計算在搜索的過程中以（3,2）為起點(diǎn)的子樹搜索了兩次。132410143220經(jīng)典問題---數(shù)塔問題記憶化搜索，記憶數(shù)組f[x][y]存儲(x,y)到數(shù)塔底層最大值，默認(rèn)全為0intd[100][100],n,f[100][100];intdfs(intx,inty){ if(x==n) { returnd[x][y]; } elseif(f[x][y]!=0)returnf[x][y]; else { intleft=dfs(x+1,y); intright=dfs(x+1,y+1); f[x][y]=d[x][y]+max(left,right); returnf[x][y]; }}遞推計算f[][]假設(shè)以格子(i,j)為首的“子三角形”的最大和為f[i][j]，則原問題的解是f[1][1]。從格子(i,j)出發(fā)往左走和往右走將分別到達(dá)位置(i+1,j)和(i+1,j+1)，則：

f[i][j]=d[i][j]+max(f[i+1][j],f[i+1][j+1]);f[1][1]=1+max(f[2][1],f[2][2]);f[2][1]=3+max(f[3][1],f[3][2]);f[2][2]=2+max(f[3][2],f[3][3]);遞推計算從最底層開始，層層遞進(jìn)，最后得到最大值。時間復(fù)雜度為O(N^2)實(shí)際上d數(shù)組和f數(shù)組可以合并inti,j;for(j=1;j<=n;j++)f[n][j]=d[n][j];//最后一層for(i=n-1;i>=1;i--)//倒數(shù)第二層往上 for(j=1;j<=i;j++)

f[i][j]=d[i][j]+max(f[i+1][j],f[i+1][j+1]);另一種遞推方式：f[i][j]表示從d[1][1]到達(dá)d[i][j]能夠得到的路徑總和的最大值，從左上方(i-1,j-1)和右上方(i-1,j)到達(dá)(i,j)則：

d[i][j]+max(f[i-1][j-1],f[i-1][j]) 1<j<i

f[i][j]=d[i][j]+f[i-1][j]; j=1

d[i][j]+f[i-1][j-1]; j=i從上往下計算，取max(f[n][i]),1<=i<=n動態(tài)規(guī)劃原理在求解一個具體問題時，問題可以按時間順序分解成若干相互聯(lián)系的有順序的階段，在每一個階段都要做出決策，全部過程的決策是一個決策序列，要使整個活動的總體效果達(dá)到最優(yōu)的問題，稱為多階段決策問題。多階段決策問題現(xiàn)有一張地圖，各結(jié)點(diǎn)代表城市，兩結(jié)點(diǎn)間連線代表道路，線上數(shù)字表示城市間的距離。如圖所示，試找出從結(jié)點(diǎn)1到結(jié)點(diǎn)10的最短路徑。

多階段決策問題第一階段第二階段第三階段第四階段第五階段F[i]表示結(jié)點(diǎn)i離結(jié)點(diǎn)10的最短距離那么，有F[i]=min(map[i][j]+F[j]),i->j存在有向邊最后，求F[1]F[7]=3, F[8]=4, F[9]=6F[4]=6+F[9], F[5]=min(7+F[7],5+F[8]), F[6]=5+F[8]F[2]=min(1+F[4],5+F[5]), F[3]=min(4+F[5],3+F[6])F[1]=min(4+F[2],2+F[3])動態(tài)規(guī)劃是運(yùn)籌學(xué)的一個分支，是求解決策過程最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(multistepdecisionprocess)的優(yōu)化問題時，提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——動態(tài)規(guī)劃。1957年出版了他的名著DynamicProgramming，這是該領(lǐng)域的第一本著作。動態(tài)規(guī)劃的基本思想：和貪心類似的是，動態(tài)規(guī)劃也是用來求解優(yōu)化問題的。其基本思想也是將待求解問題分解成若干個子問題，但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的（即有重疊子問題）。不同子問題的數(shù)目常常只有多項(xiàng)式量級。如果能夠保存已經(jīng)解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計算。動態(tài)規(guī)劃的實(shí)現(xiàn)思路：建立子問題的描述，建立狀態(tài)間的轉(zhuǎn)移關(guān)系，使用遞推或記憶化搜索法來實(shí)現(xiàn)。狀態(tài)定義：用問題的某些特征參數(shù)描述一個子問題。在“數(shù)塔問題”中用f[i][j]表示以格子(i,j)為根的子三角形的最大和。每個f[i][j]稱為一個狀態(tài)狀態(tài)轉(zhuǎn)移方程：即狀態(tài)值之間的遞推關(guān)系。這個方程通常需要考慮兩個部分：一是遞推的順序，二是遞歸邊界（也是遞推起點(diǎn)）。從直接遞歸和后兩種方法的比較可以看出：重疊子問題是動態(tài)規(guī)劃展示威力的關(guān)鍵。動態(tài)規(guī)劃的適用條件

適用動態(tài)規(guī)劃的問題必須滿足：最優(yōu)化原理無后效性最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）一個問題的最優(yōu)解包含子問題的最優(yōu)解，或者說通過子問題的最優(yōu)解能夠得到原問題的最優(yōu)解，此問題具備最優(yōu)子結(jié)構(gòu)性質(zhì)。最優(yōu)化原理是動態(tài)規(guī)劃的基礎(chǔ)，任何問題，如果失去了最優(yōu)化原理的支持，就不可能用動態(tài)規(guī)劃方法計算。無后向性將各階段按照一定的次序排列好之后，對于某個給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當(dāng)前的這個狀態(tài)。換句話說，每個狀態(tài)都是過去歷史的一個完整總結(jié)。這就是無后向性，又稱為無后效性。動態(tài)規(guī)劃的適用條件

數(shù)塔II132101443220有一個由正整數(shù)組成的三角形，第一行只有一個數(shù)，除了最下行之外每個數(shù)的左下方和右下方各有一個數(shù),如下圖所示。從第一行的數(shù)開始,除了某一次可以走到下一行的任意位置外,每次都只能左下或右下走一格,直到走到最下行,把沿途經(jīng)過的數(shù)全部加起來.如何走,使得這個和盡量大?問題描述Input

輸入數(shù)據(jù)首先包括一個整數(shù)C,表示測試實(shí)例的個數(shù)，每個測試實(shí)例的第一行是一個整數(shù)N(1<=N<=500)，表示數(shù)塔的高度，接下來用N行數(shù)字表示數(shù)塔，其中第i行有個i個整數(shù)，且所有的整數(shù)均在區(qū)間[0,99]內(nèi)。Output

對于每個測試實(shí)例，輸出可能得到的最大和。SampleInput

1

4

1

32

4101

43220SampleOutput

34

hint:路徑1->3->10->20

問題分析面臨的問題：第一行是可以移動到下一行任意位置，還是只能往左下或右下走一格？這取決解決這個子問題之前做過的事情。如果在第i行到第i+1行移動，已經(jīng)任意移動過，那么就只能往左下或右下走一格了。所以這個問題，先前的決策可能會影響后續(xù)的決策，即狀態(tài)定義有后效性。解決方法：擴(kuò)展?fàn)顟B(tài)定義，把有后效性的部分包含進(jìn)來。方法一假設(shè)從第一行到位置(i,j)，每次都只能往左下或右下走一格，令F1[i][j]為從第一行開始走到(i,j)所能得到的最大和；M1[i]表示從第一行走到第i行能夠得到的最大值，M1[i]=max(F1[i][j]),1<=j<=i第i行到最后一行，又是每次都只能往左下或右下走一格，F(xiàn)2[i][j]表示從第i行第j列（即以（i,j)為根）開始走到最后一行所能得到的最大和；M2[i]表示從第i行到達(dá)最后一行能夠的到的最大值，M2[i]=max(F2[i][j]),1<=j<=i則：

原問題的解為：max(M1[i]+M2[i+1])第i行到第i+1行任意移動枚舉每一個i(i=1,2,3,...,n-1)，從而找到結(jié)果設(shè)以格子(i,j)為首的“子三角形”的最大和為f[i][j][k]

:k=1,則表示某一次可以走到下一行的任意位置k=0,則表示只能走左下或右下的一格，不可以任意移動則原問題的解是f[1][1][1]。

方法二數(shù)塔III132101443220有一個由正整數(shù)組成的三角形，第一行只有一個數(shù)，除了最下行之外每個數(shù)的左下方和右下方各有一個數(shù),如下圖所示。從第一行的數(shù)開始,每次都只能左下或右下走一格,直到走到最下行,把沿途經(jīng)過的數(shù)全部加起來.如何走,使得這個和的個位數(shù)字盡量大?問題描述Input

輸入數(shù)據(jù)首先包括一個整數(shù)C,表示測試實(shí)例的個數(shù)，每個測試實(shí)例的第一行是一個整數(shù)N(1<=N<=100)，表示數(shù)塔的高度，接下來用N行數(shù)字表示數(shù)塔，其中第i行有個i個整數(shù)，且所有的整數(shù)均在區(qū)間[0,99]內(nèi)。Output

對于每個測試實(shí)例，輸出可能得到的最大個位數(shù)。SampleInput

1

4

1

32

4101

43220SampleOutput

7

hint:路徑1->3->10->3

問題分析面臨的問題：兩個數(shù)的個位數(shù)字加起來，得到的和可能變成兩位數(shù)，因此全局最優(yōu)解可能沒有包含子問題的最優(yōu)解，如上例：全局最優(yōu)解f[1][1]為：5—0—4—0子問題f[2][1]的最優(yōu)解：0—4—2全局最優(yōu)解沒有包含子問題的最優(yōu)解

，該問題不滿足最優(yōu)子結(jié)構(gòu)5000042000假設(shè)以格子(i,j)為根的“子三角形”走過的路徑上所有數(shù)之和的個位數(shù)字最大為f[i][j]

i=2，f[2][1]=6，f[2][2]=0

i=1,

(f[2][1]+5)%10=1

(f[2][2]+5)%10=5

原問題的正確解為：f[1][1]=9

f[1][1]≠max{(f[2][1]+5)%10,(f[2][2]+5)%10}13210144322043208113237065453521746566擴(kuò)展?fàn)顟B(tài)定義，設(shè)f[i][j][k]表示以格子(i,j)為根的“子三角形”是否存在所有數(shù)之和的個位數(shù)字為k(k=0,1,2,3,...,9)的路徑：f[i][j][k]=1,則表示存在f[i][j][k]=0,則表示不存在則原問題的解是為：搜索滿足f[1][1][k]==1的最大k，即為所求解問題分析1087數(shù)塔1318數(shù)塔II1319數(shù)塔III最長上升子序列

LIS（LongestIncreasingSubsequence）

給一個序列，求它的一個遞增子序列，使它的元素個數(shù)盡量多。例如序列1,6,2,5,4,7的最長上升子序列是1,2,5,7162547DAG有向無環(huán)圖a[i]<a[j]且i<j,則從a[i]向a[j]建一條有向邊，求最長的路徑f[i]表示以a[i]為結(jié)尾的最長的子序列的長度f[i]=max{f[j]}+1,(a[j]<a[i],j<i)f[1]=1,依次求解f[2],f[3]……..通過f[1],f[2],…..,f[i-1]求得f[i]，最后在所有f[]找一個最大值f[1],f[2],….f[i-1]f[i],f[i+1],….,f[n]已知（已經(jīng)求出來）未知（還未求出來）1320攔截導(dǎo)彈1142魔族密碼1233合唱隊(duì)形1321難解的問題維護(hù)一個數(shù)組c，初始大小為1，c[i]表示最長上升子序列長度是i的所有子串中末尾最小的那個數(shù)，根據(jù)這個數(shù)字，只要當(dāng)前的數(shù)比c[i]大，那么當(dāng)前這個數(shù)一定能通過c[i]構(gòu)成一個長度為i+1的上升子序列。在C數(shù)組中找一個盡量靠后的數(shù)字，這樣我們得到的上升子串的長度最長，查找的時候使用二分搜索，這樣時間復(fù)雜度便下降了1322雷曼兔1323笨笨的導(dǎo)彈攻擊最長公共子序列問題(LCS)

問題描述一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。例如，序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列，相應(yīng)的遞增下標(biāo)序列為<2,3,5,7>。給定兩個序列X和Y，當(dāng)另一序列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的一個最長公共子序列，因?yàn)閄和Y沒有長度大于4的公共子序列。最長公共子序列(LCS)問題：給定兩個序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>，要求找出X和Y的一個最長公共子序列。動態(tài)規(guī)劃法解該問題：最長公共子序列問題有最優(yōu)子結(jié)構(gòu)性質(zhì)，定理:LCS的最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)：序列Xm=<x1,x2,…,xm>

Yn=<y1,y2,…,yn>

Xm和Yn的一個最長公共子序列Zk=<z1,z2,…,zk>，則：（1）若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長公共子序（2)若xm≠yn且zk≠xm

，則Zk是Xm-1和Yn的最長公共子序列；(3)若xm≠yn且zk≠yn

，則Zk是Xm和Yn-1的最長公共子序列。其中：Xm-1=<x1,x2,…,xm－１>，

Yn-1=<y1,y2,…,yn－１

>，

Zk-1=<z1,z2,…,zk－１>。最長公共子序列問題(LCS)

遞歸定義LCS的長度用c[i][j]記錄序列Xi和Yj的最長公共子序列的長度。其中,Xi=<x1,x2,…,xi>，Yj=<y1,y2,…,yj>。當(dāng)i=0或j=0時，空序列是Xi和Yj的最長公共子序列，故c[i][j]=0。最長公共子序列問題(LCS)

c[i][j]=0c[i-1][j-1]+1max(c[i][j-1],c[i-1][j])i=0或j=0i，j>0且Xi=Yji，j>0且Xi!=Yj計算最長公共子序列長度的動態(tài)規(guī)劃算法LCS_LENGTH(X,Y):以序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>作為輸入。輸出兩個數(shù)組c[][]和b[][]。其中c[i][j]存儲Xi與Yj的最長公共子序列的長度，b[i][j]記錄指示c[i][j]的值是由哪一個子問題的解達(dá)到的，這在構(gòu)造最長公共子序列時要用到。X和Y的最長公共子序列的長度記錄于c[m][n]中。voidLCS_LENGTH(X,Y){

for(i=1;i<=m;i++)c[i][0]=0;for(j=1;j<=n;j++)c[0][j]=0;

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

if

(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=‘↖’;}elseif(c[i-1][j]≥c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=‘↑’;}else{c[i][j]=c[i][j-1];b[i][j]=‘←’}

}由于每個數(shù)組單元的計算耗費(fèi)Ο(1)時間，算法LCS_LENGTH耗時Ο(mn)。最長公共子序列問題(LCS)

最長公共子序列問題(LCS)

構(gòu)造最長公共子序列由算法LCS_LENGTH計算得到的數(shù)組b可用于快速構(gòu)造序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的最長公共子序列。首先從b[m][n]開始，沿著其中的箭頭所指的方向在數(shù)組b中搜索。當(dāng)b[i][j]中遇到"↖"時，表示Xi與Yj的最長公共子序列是由Xi-1與Yj-1的最長公共子序列在尾部加上xi得到的子序列；當(dāng)b[i][j]中遇到"↑"時，表示Xi與Yj的最長公共子序列和Xi-1與Yj的最長公共子序列相同；當(dāng)b[i][j]中遇到"←"時，表示Xi與Yj的最長公共子序列和Xi與Yj-1的最長公共子序列相同。最長公共子序列問題(LCS)

算法LCS(b,X,i,j)實(shí)現(xiàn)根據(jù)b的內(nèi)容打印出Xi與Yj的最長公共子序列。voidLCS(b,X,i,j){

ifi==0orj==0return;

ifb[i][j]==‘↖’{LCS(b,X,i-1,j-1);print(x[i]);/*打印x[i]*/

}

elseifb[i,j]==‘↑’LCS(b,X,i-1,j)elseLCS(b,X,i,j-1);}在算法LCS中，每一次的遞歸調(diào)用使i或j減1，因此算法的計算時間為O(m+n)。最長公共子序列問題(LCS)

背包問題有N個物品和一個背包，其中:物品具有重量(w1,w2,…,wn)背包的最大重量承受限制為W

每件物品要么選要么不選，怎樣使背包盡可能裝滿，求裝入背包物品重量和的最大值?簡單方法：定義標(biāo)記數(shù)組f，初始全部為0，f[i]=1表示存在物品重量和為i的選取方案f[0]=1;//不選任何物品for(intj=1;j<=n;j++)//w1,w2,w3,……

for(inti=W-w[j];i>=0;i--)//總和不能超過背包容量

{ if(f[i])//存在重量和為i的方案

f[i+w[j]]=1;//加上第j個物品

}為了保證，每個物品最多只取一次，代碼中第二層for循環(huán)，循環(huán)變量必須是遞減的如果改成for(inti=0;i<=W-w[j];i++)，可能導(dǎo)致某件物品選了多次比如，W=10，w[1]=3，那么f[3]=1，i循環(huán)到3時，f[6]又等于1，第1件物品取了兩次背包問題有N個物品和一個背包，其中:物品具有重量(w1,w2,…,wn)和價值(p1,p2,…,pn)背包的最大重量承受限制為W

如何放置物品可得最高價值?簡單方法：數(shù)組f，初始全為0f[i]表示物品重量和為i的方案總價值的最大值f[i]=0表示不存在重量和為i的選取方案for(intj=0;j<n;j++){ for(inti=W-w[j];i>=0;i--) { if(f[i]>0||i==0) { if(f[i+w[j]]<f[i]+p[j])//存在重量和為i+w[j]，總價值更高的方案 f[i+w[j]]=f[i]+p[j]; } }}//在f數(shù)組內(nèi)選一個最大值w[]={5,3,2}P[]={9,7,8}W=53，5，0編號，剩下的重量，總價值2，5，0Depthfirstleftfirst決策樹1，5，01，2，7-，5，0-，0，92，3，81，3，81，0，15-，2，7-，3，8左邊-不選右邊-選intMaxVal(inti,intr)//返回前i個物品，剩余重量是r，能取得的價值最大值{if(i==1)//邊界條件{if(r>=w[i])returnp[i];//選第一個物品elsereturn0;}if(r<w[i])returnMaxVal(i-1,r);//只能往左returnmax(MaxVal(i-1,r),p[i]+MaxVal(i-1,r-w[i]));

//在不選第i個物品與選擇第i個物品中選一個最大值}記憶化搜索：intMaxVal(inti,intr){ if(i==1) { if(r>=w[i])returnp[i]; elsereturn0; } if(f[i][r])returnf[i][r]; if(r<w[i])f[i][r]=MaxVal