信息學(xué)奧賽NOIP動(dòng)態(tài)規(guī)劃入門課件

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

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

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

我們把F(x)

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

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

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

{

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

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

}時(shí)間復(fù)雜度？能優(yōu)化嗎？例1:斐波那契（Fibonacci）數(shù)列IntF(intn)時(shí)間復(fù)雜度？能優(yōu)化嗎？例1:斐波那例1:斐波那契（Fibonacci）數(shù)列//dp數(shù)組，用以保存已經(jīng)計(jì)算過(guò)的結(jié)果//dp[n]記錄F(n)的結(jié)果，dp[n]=-1表示沒(méi)有計(jì)算過(guò)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];

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

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

一個(gè)由非負(fù)數(shù)組成的三角形，第一行只有一個(gè)數(shù)，除了最下行之外每個(gè)數(shù)的左下方和右下方各有個(gè)數(shù)，從第一行的數(shù)開(kāi)始，每次可以選擇向左下或是向右下走一格，一直走到最下行，把沿途經(jīng)過(guò)的數(shù)全部加起來(lái)。如何走才能使得這個(gè)和盡量大？。數(shù)字三角形格子編號(hào)窮舉？貪心？搜索？數(shù)組存儲(chǔ)例2:數(shù)字三角形數(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];}}格子編號(hào)深搜（遞歸實(shí)現(xiàn)）格子編號(hào)分析：考察設(shè)以格子(i,j)為首的“子三角形”的最大和為d[i,j]（我們將不加區(qū)別的把這個(gè)子問(wèn)題(subproblem)本身也稱為d[i,j]），則原問(wèn)題的解是d[1,1]我們關(guān)心的是從某處出發(fā)到底部的最大和：從(2,1)點(diǎn)出發(fā)的最大和記做d[2,1];從(2,2)點(diǎn)出發(fā)的最大和記做d[2,2];從（1，1）出發(fā)有兩種選擇（2，1）或（2，2）在已知d[2,1]和d[2,2]的情況下，應(yīng)選擇較大的一個(gè)。分析：考察設(shè)以格子(i,j)為首的“子三角形”的最大和為d[思考：考慮更一般的情況，當(dāng)前位置（i，j）看成一個(gè)狀態(tài)，

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

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

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

從格子（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]。

如何選呢？

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

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

方法1：遞推計(jì)算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]);}時(shí)間復(fù)雜度O（n2）方法1：遞推計(jì)算voidsolve(

dt(1,1)的調(diào)用關(guān)系樹重復(fù)計(jì)算intsolve(inti,intj){if(i==n)returna[i][j];elsereturna[i][j]+max(solve(i+1,j),solve(i+1,j+1));}方法2：遞歸計(jì)算這樣做是正確的，可惜時(shí)間效率太低。低效的原因在于重復(fù)計(jì)算。dt(1,1)的調(diào)用關(guān)系樹重復(fù)計(jì)算intsolve(這個(gè)方法和直接遞歸非常類似，但加入了記憶化(memoization)，保證每個(gè)結(jié)點(diǎn)只訪問(wèn)一次。//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];}

時(shí)間復(fù)雜度O（n2）

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

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

子問(wèn)題重疊性質(zhì)：在用遞歸算法自頂向下對(duì)問(wèn)題進(jìn)行求解是，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題可能被重復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法利用此性質(zhì)，對(duì)每個(gè)子問(wèn)題只計(jì)算一次，然后將其結(jié)果保存起來(lái)以便高效重用。

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

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

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

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

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

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

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

種決策。

思考：邊界情況：？？思考：最后的結(jié)果：？？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]{對(duì)角線}max{d[n][1],d[n][2]……d[n][n]}d(i,j)為：取d(i-1,j)

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

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

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

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]轉(zhuǎn)移方程：

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])}

結(jié)果？轉(zhuǎn)移方程：最大連續(xù)子序列和（MaximumContinuo動(dòng)態(tài)規(guī)劃的核心設(shè)計(jì)狀態(tài)

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

838920715530029917015865樣例輸出：

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

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

設(shè)d(i)表示從結(jié)點(diǎn)i出發(fā)的最長(zhǎng)下降序列

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

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

d(i)=

Max{d(j)}+1并且a[i]>=a[j]同時(shí)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;記錄前驅(qū)}從n-1開(kāi)始遞推考慮更一般的情況：d(i)=Max{d(j)}+1并且a[考慮更一般的情況：

d(i)=