動態(tài)規(guī)劃初步動態(tài)規(guī)劃初步引入：走樓梯已知一個樓梯有n級，從下往上走，一步可以走一級，也可以走兩級，走到第N級樓梯有多少種走法？【輸入格式】一行一個整數(shù)n?！据敵龈袷健恳恍袃H有一整數(shù)，表示走到第n級有多少種走法?！据斎霕永俊据敵鰳永?2【數(shù)據規(guī)?！繉?00%的數(shù)據滿足：0＜n≤30。引入：走樓梯已知一個樓梯有n級，從下往上走，一步可以走一級，最短路徑問題---求A到E的最短路的長度窮舉？貪心？搜索？最短路徑問題---求A到E的最短路的長度窮舉？貪心？搜索？思考：

仔細觀察本圖路徑的特殊性，可以分成4個階段：第一階段：A經過A-B1或A-B2到B第二階段：B1有三條路通……；B2有兩條通路……階段1階段2階段3階段4思考：仔細觀察本圖路徑的特殊性，可以分成4個階段：階段1階思考：倒著推；設F(x)表示x到E的最短路徑的長度階段4：F(D1)=3;F(D2)=4;F(D3)=3階段3：F(C1)=min{F(D1)+C1到D1的路徑長度，

F(D2)+C1到D2的路徑長度}F(C2)……階段1階段2階段3階段4思考：倒著推；設F(x)表示x到E的最短路徑的長度階段4：F信息學奧賽NOIP動態(tài)規(guī)劃入門ppt課件

我們把F(x)

稱為當前x的狀態(tài)；在這個例子中每個階段的選擇依賴當前的狀態(tài)，又隨即引起狀態(tài)的轉移，一個決策序列(E–D3-C4-B2-A)就是在變化的狀態(tài)中產生的，故有“動態(tài)”的含義。階段1階段2階段3階段4我們把F(x)稱為當前x的狀態(tài)；階段1階段2階段3階段基本概念階段：問題的過程被分成若干相互聯(lián)系的部分，我們成為階段，以便按一定的次序求解。狀態(tài)：

某一階段的出發(fā)位置稱為狀態(tài)，通常一個階段包含若干狀態(tài)。決策：

對問題的處理中作出的每種選擇的行動就是決策。即從該階段的每個狀態(tài)出發(fā)，通過一次選擇性的行動移至下一個階段的相應狀態(tài)?；靖拍铍A段：IntF(intn)

{

if(n==0||n==1)return1;

elsereturnF(n-1)+F(n-2);

}時間復雜度？能優(yōu)化嗎？例1:斐波那契（Fibonacci）數(shù)列IntF(intn)時間復雜度？能優(yōu)化嗎？例1:斐波那例1:斐波那契（Fibonacci）數(shù)列//dp數(shù)組，用以保存已經計算過的結果//dp[n]記錄F(n)的結果，dp[n]=-1表示沒有計算過IntF(intn){

if(n==0||n==1)return1;

if(dp[n]!=-1)returndp[n];

else{

dp[n]=

F(n-1)+F(n-2);

returndp[n];

}}時間復雜度？例1:斐波那契（Fibonacci）數(shù)列//dp數(shù)組，用以

例2:數(shù)字三角形

一個由非負數(shù)組成的三角形，第一行只有一個數(shù)，除了最下行之外每個數(shù)的左下方和右下方各有個數(shù)，從第一行的數(shù)開始，每次可以選擇向左下或是向右下走一格，一直走到最下行，把沿途經過的數(shù)全部加起來。如何走才能使得這個和盡量大？。數(shù)字三角形格子編號窮舉？貪心？搜索？數(shù)組存儲例2:數(shù)字三角形數(shù)字三角形格深搜（遞歸實現(xiàn)）程序清單：voidf(inti,intj){s=s+a[i][j];if(i==4)if(s>max)max=s;else{

f(i+1,j);s=s-a[i+1][j];

f(i+1,j+1);s=s-a[i+1][j+1];}}格子編號深搜（遞歸實現(xiàn)）格子編號分析：考察設以格子(i,j)為首的“子三角形”的最大和為d[i,j]（我們將不加區(qū)別的把這個子問題(subproblem)本身也稱為d[i,j]），則原問題的解是d[1,1]我們關心的是從某處出發(fā)到底部的最大和：從(2,1)點出發(fā)的最大和記做d[2,1];從(2,2)點出發(fā)的最大和記做d[2,2];從（1，1）出發(fā)有兩種選擇（2，1）或（2，2）在已知d[2,1]和d[2,2]的情況下，應選擇較大的一個。分析：考察設以格子(i,j)為首的“子三角形”的最大和為d[思考：考慮更一般的情況，當前位置（i，j）看成一個狀態(tài)，

定義狀態(tài)（i，j）的指標函數(shù)d(i，j)

為從格子（i，j）出發(fā)時能得到的最大和（包含格子（i，j）本身的值）。

原題的解：？d（？，？）格子編號d[1，1]格子編號d[1，1]思考：觀察不同狀態(tài)如何轉移的。

從格子（i，j）出發(fā)有兩種決策。如果（i，j）格子里的值為a(i，j)

向左走需要求“從（i+1，j）出發(fā)的最大和”，就是d[i+1，j]。向右走需要求“從（i+1，j+1）出發(fā)的最大和”，就是d[i+1，j+1]。

如何選呢？

思考：邊界條件？其中較大的一個，再加上a(i,j)的值就是d[i,j]。d[i,j]=a[i,j]+max{d[i+1,j],d[i+1,j+1]}思考：觀察不同狀態(tài)如何轉移的。思考：邊界條件？其中較思想：從上向下思考，從底向上計算數(shù)字三角形81321162324思想：從上向下思考，從底向上計算數(shù)字三角形813211623時間復雜度O（n2）

在計算d[i][j]前，d[i+1][j],d[i+1][j+1]已計算好了！

方法1：遞推計算voidsolve(){inti,j;for(j=1;j<=n;j++)d[n][j]=a[n][j];for(i=n-1;i>=1;i--)for(j=1;j<=i;j++)d[i][j]=a[i][j]+max(d[i+1][j],d[i+1][j+1]);}時間復雜度O（n2）方法1：遞推計算voidsolve(

dt(1,1)的調用關系樹重復計算intsolve(inti,intj){if(i==n)returna[i][j];elsereturna[i][j]+max(solve(i+1,j),solve(i+1,j+1));}方法2：遞歸計算這樣做是正確的，可惜時間效率太低。低效的原因在于重復計算。dt(1,1)的調用關系樹重復計算intsolve(這個方法和直接遞歸非常類似，但加入了記憶化(memoization)，保證每個結點只訪問一次。//initially,alld[i][j]are-1intsolve(inti,intj){if(i==n)returna[i][j];if(d[i][j]>=0)returnd[i][j];d[i][j]=a[i][j]+max(solve(i+1,j),solve(i+1,j+1));returnd[i][j];}

時間復雜度O（n2）

不必事先確定各狀態(tài)的計算順序方法3：記憶化搜索這個方法和直接遞歸非常類似，但加入了記憶化(me動態(tài)規(guī)劃基本思想

建立子問題的描述，建立狀態(tài)間的轉移關系，使用遞推或記憶化搜索法來實現(xiàn)。狀態(tài)定義用問題的某些特征參數(shù)描述一個子問題。在本題中用d[i,j]表示以格子(i,j)為根的子三角形的最大和。在很多時候，狀態(tài)描述的細微差別將引起算法的不同。狀態(tài)轉移方程即狀態(tài)值之間的遞推關系。這個方程通常需要考慮兩個部分：一是遞推的順序，二是遞歸邊界（也是遞推起點）。從直接遞歸和后兩種方法的比較可以看出：重疊子問題(overlappingsubprob-lems)是動態(tài)規(guī)劃展示威力的關鍵。動態(tài)規(guī)劃基本思想建立子問題的描述，建立狀態(tài)間的轉考察：d(1,1)；d(2,1)；d(2,2)……這些問題的共性：都是求從一個位置出發(fā)到底部的最大值；是一個共同的問題。d(2,1)d(2,2)重疊子問題考察：d(1,1)；d(2,1)；d(2,2)……這些問題的考察：d(1,1)；d(2,1)；d(2,2）；可以發(fā)現(xiàn)每個子問題結果都是最優(yōu)的。d(2,1)d(2,2)最優(yōu)子結構考察：d(1,1)；d(2,1)；d(2,2）；可以發(fā)現(xiàn)每個什么是動態(tài)規(guī)劃？動態(tài)規(guī)劃是求解包含重疊子問題的最優(yōu)化方法動態(tài)規(guī)劃的性質？

子問題重疊性質：在用遞歸算法自頂向下對問題進行求解是，每次產生的子問題并不總是新問題，有些子問題可能被重復計算多次。動態(tài)規(guī)劃算法利用此性質，對每個子問題只計算一次，然后將其結果保存起來以便高效重用。

最優(yōu)化子結構性質：若問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，則稱該問題具有最優(yōu)子結構性質（即滿足最優(yōu)化原理）。能用動態(tài)規(guī)劃解決的求最優(yōu)解問題，必須滿足最優(yōu)解的每個局部也都是最優(yōu)的什么是動態(tài)規(guī)劃？動態(tài)規(guī)劃是求解包含重疊子問題的最優(yōu)化方法無后效性：即某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)及決策的影響。也就是說，“未來與過去無關”，當前的狀態(tài)是此前歷史的一個完整總結，此前的歷史只能通過當前的狀態(tài)去影響過程未來的演變。數(shù)字三角形如果數(shù)字三角形(有負數(shù))求的是從上到下的和最接近零。就不符合無后效性原則。無后效性：即某階段的狀態(tài)一旦確定，則此后過程的演變不動態(tài)規(guī)劃的優(yōu)勢1.動態(tài)規(guī)劃比窮舉具有較少的計算次數(shù)

從數(shù)塔問題可以看出，層數(shù)為k時，

窮舉算法求路徑的條數(shù)2k-1

動態(tài)規(guī)劃計算的次數(shù)為:

窮舉最多計算到n=20，動態(tài)規(guī)劃可以算到n=1002.遞歸需要很大的?？臻g，而動規(guī)的遞推法不需要棧空間；使用記憶化搜索比較容易書寫程序。動態(tài)規(guī)劃的優(yōu)勢1.動態(tài)規(guī)劃比窮舉具有較少的計算次數(shù)思考：

還有一種思考方法，從下向上考慮，觀察不同狀態(tài)如何轉

移的。從格子（i，j）出發(fā)有兩

種決策。

思考：邊界情況：？？思考：最后的結果：？？d[1][1]=a[1][1]d[i][1]=d[i-1][1]+a[i][1]{第1列}d[i][i]=d[i-1][i-1]+a[i][i]{對角線}max{d[n][1],d[n][2]……d[n][n]}d(i,j)為：取d(i-1,j)

和d(i-1,j-1)中較大的一個加上a(i,j)的和。這種方法本質就是遞推思考：還有一種思考方法，從下思考：邊界情況：？？思考：最后例3:最大連續(xù)子序列和（MaximumContinuousSubsequenceSum）給定k個整數(shù)的序列{A1,A2,...,Ak}，其任意連續(xù)子序列可表示為{Ai,Ai+1,...,Aj}，其中1<=i<=j<=k。最大連續(xù)子序列是所有連續(xù)子序中元素和最大的一個。

例如給定序列{-2,11,-4,13,-5,-2}，其最大連續(xù)子序列為{11,-4,13}，最大連續(xù)子序列和即為20。

暴力枚舉？時間復雜度為？能優(yōu)化嗎？復雜度？例3:最大連續(xù)子序列和（MaximumContinuous令狀態(tài)dp[i]表示以A[i]作為末尾的連續(xù)序列的最大和（A[i]必須作為序列的末尾）。以樣例為例，序列{-2,11,-4,13,-5,-2}，下標分別設為：0，1，2，3，4，5；dp[0]dp[1]dp[2]dp[3]dp[4]dp[5]問題轉換為dp[0],dp[1],…,dp[n-1]中的最大者。最大連續(xù)子序列和（MaximumContinuousSubsequenceSum）令狀態(tài)dp[i]表示以A[i]作為末尾的連續(xù)序列的最大和（Adp[i]表示以A[i]作為末尾的連續(xù)序列的最大和（A[i]必須作為序列的末尾）;只有兩重情況：1、這個最大和的連續(xù)序列只有一個元素，即以A[i]開始，以A[i]結尾；最大和就是A[i]本身。2、這個最大和的連續(xù)序列有多個元素，從前面某處A[p]開始（p<i)；一直到A[i]結尾。也就是

dp[i-1]+A[i];

A[p]+…+A[i-1]+A[i]=dp[i-1]+A[i];最大連續(xù)子序列和（MaximumContinuousSubsequenceSum）dp[i]表示以A[i]作為末尾的連續(xù)序列的最大和（A[i]轉移方程：

dp[i]=max{A[i],dp[i-1]+A[i]}

邊界：dp[0]=A[0]最大連續(xù)子序列和（MaximumContinuousSubsequenceSum）代碼：

dp[0]=A[0];

for(inti=1;i<n;

i++){dp[i]=max(A[i],dp[i-1]+A[i])}

結果？轉移方程：最大連續(xù)子序列和（MaximumContinuo動態(tài)規(guī)劃的核心設計狀態(tài)

和狀態(tài)轉移方程動態(tài)規(guī)劃的核心設計狀態(tài)問題描述：攔截導彈（NOIP1999）：某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。但是這種導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲，由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導彈。輸入導彈的枚數(shù)和導彈依次飛來的高度（雷達給出的高度數(shù)據是不大于30000的正整數(shù)，每個數(shù)據之間有一個空格），計算這套系統(tǒng)最多能攔截多少導彈？樣例輸入：

838920715530029917015865樣例輸出：

6（最多能攔截的導彈數(shù)）

例4：最長下降序列問題描述：攔截導彈（NOIP1999）：樣例輸入：例4：最長題目分析：給定一個正整數(shù)序列，求出其中最長下降序列：例如：3892071553002991701586538930029917015865所求的問題：從某一個位置開始的最長下降序列尋找一個狀態(tài)？

設d(i)表示從結點i出發(fā)的最長下降序列

從d(1)位置出發(fā)，考察下一步：

389207155300499170d(1)=Max｛d(2)、d(3)、d(4)、d(6)｝+1題目分析：設d(i)表示從結點i出發(fā)的最長下降序列從d(1)考慮更一般的情況：

d(i)=

Max{d(j)}+1并且a[i]>=a[j]同時j>i

初始化

d(i)=

1

for(inti=n-1;i<=1;i--)

{

max=0;k=0;for(intj=i+1;j<=n;j++)if(a[j]<=a[i])&&(d[j]>max){

max=d[j];k=j;

};

d[i]=max+1;

c[i]=k;記錄前驅}從n-1開始遞推考慮更一般的情況：d(i)=Max{d(j)}+1并且a[考慮更一般的情況：

d(i)=