信息學(xué)奧賽NOI動(dòng)態(tài)規(guī)劃入門(C++).ppt

動(dòng)態(tài)規(guī)劃入門,上課內(nèi)容,什么是動(dòng)態(tài)規(guī)劃基本概念斐波那契數(shù)列經(jīng)典的類型,最短路徑問(wèn)題-求A到E的最短路的長(zhǎng)度,窮舉？貪心？搜索？,思考：仔細(xì)觀察本圖路徑的特殊性，可以分成4個(gè)階段：第一階段：A經(jīng)過(guò)A-B1或A-B2到B第二階段：B1有三條路通；B2有兩條通路,思考：倒著推；設(shè)F(x)表示x到E的最短路徑的長(zhǎng)度,階段4：F(D1)=3;F(D2)=4;F(D3)=3階段3：F(C1)=minF(D1)+C1到D1的路徑長(zhǎng)度，F(xiàn)(D2)+C1到D2的路徑長(zhǎng)度F(C2),我們把F(x)稱為當(dāng)前x的狀態(tài)；在這個(gè)例子中每個(gè)階段的選擇依賴當(dāng)前的狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列(ED3-C4-B2-A)就是在變化的狀態(tài)中產(chǎn)生的，故有“動(dòng)態(tài)”的含義。,intfib(intn)if(n=1|n=2)return1;elsereturnfib(n-1)+fib(n-2);,時(shí)間復(fù)雜度？能優(yōu)化嗎？,例1:斐波那契（Fibonacci）數(shù)列,斐波納契數(shù)列,大量重復(fù)計(jì)算！,如何可以使計(jì)算僅需一次？,例1:斐波那契（Fibonacci）數(shù)列,/dp數(shù)組，用以保存已經(jīng)計(jì)算過(guò)的結(jié)果/dpn記錄F(n)的結(jié)果，dpn=-1表示沒(méi)有計(jì)算過(guò)intfib(intn)if(n=1|n=2)return1;if(dpn!=-1)returndpn;elsedpn=fib(n-1)+fib(n-2);returndpn;,時(shí)間復(fù)雜度？,基本概念,階段：?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)。,例2:數(shù)字三角形一個(gè)由非負(fù)數(shù)組成的三角形，第一行只有一個(gè)數(shù)，除了最下行之外每個(gè)數(shù)的左下方和右下方各有個(gè)數(shù)，從第一行的數(shù)開始，每次可以選擇向左下或是向右下走一格，一直走到最下行，把沿途經(jīng)過(guò)的數(shù)全部加起來(lái)。如何走才能使得這個(gè)和盡量大？。,數(shù)字三角形,格子編號(hào),窮舉？貪心？搜索？,數(shù)組存儲(chǔ),深搜（遞歸實(shí)現(xiàn)）程序清單：voidf(inti,intj);s=s+aij;if(i=4)if(smax)max=s;elsef(i+1,j);s=s-ai+1j;f(i+1,j+1);s=s-ai+1j+1;,格子編號(hào),分析：考察,設(shè)以格子(i,j)為首的“子三角形”的最大和為di,j（我們將不加區(qū)別的把這個(gè)子問(wèn)題(subproblem)本身也稱為di,j），則原問(wèn)題的解是d1,1我們關(guān)心的是從某處出發(fā)到底部的最大和：從(2,1)點(diǎn)出發(fā)的最大和記做d2,1;從(2,2)點(diǎn)出發(fā)的最大和記做d2,2;從（1，1）出發(fā)有兩種選擇（2，1）或（2，2）在已知d2,1和d2,2的情況下，應(yīng)選擇較大的一個(gè)。,思考：考慮更一般的情況，當(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),d1，1,思考：觀察不同狀態(tài)如何轉(zhuǎn)移的。從格子（i，j）出發(fā)有兩種決策。如果（i，j）格子里的值為a(i，j)向左走需要求“從（i+1，j）出發(fā)的最大和”，就是di+1，j。向右走需要求“從（i+1，j+1）出發(fā)的最大和”，就是di+1，j+1。如何選呢？,思考：邊界條件？,其中較大的一個(gè)，再加上a(i,j)的值就是di,j。di,j=ai,j+maxdi+1,j,di+1,j+1,思想：從上向下思考，從底向上計(jì)算,數(shù)字三角形,8,13,21,16,23,24,時(shí)間復(fù)雜度O（n2）在計(jì)算dij前，di+1j,di+1j+1已計(jì)算好了！,方法1：遞推計(jì)算,voidsolve()inti,j;for(j=1;j=1;i-)for(j=1;j=0)returndij;dij=aij+max(solve(i+1,j),solve(i+1,j+1);returndij;,時(shí)間復(fù)雜度O（n2）不必事先確定各狀態(tài)的計(jì)算順序,方法3：記憶化搜索,動(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)題。在本題中用di,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(1,1)；d(2,1)；d(2,2)這些問(wèn)題的共性：都是求從一個(gè)位置出發(fā)到底部的最大值；是一個(gè)共同的問(wèn)題。,重疊子問(wèn)題,考察：d(1,1)；d(2,1)；d(2,2）；可以發(fā)現(xiàn)每個(gè)子問(wèn)題結(jié)果都是最優(yōu)的。,最優(yōu)子結(jié)構(gòu),什么是動(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)的,無(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ú)后效性原則。,動(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.遞歸需要很大的?？臻g，而動(dòng)規(guī)的遞推法不需要?？臻g；使用記憶化搜索比較容易書寫程序。,思考：還有一種思考方法，從下向上考慮，觀察不同狀態(tài)如何轉(zhuǎn)移的。從格子（i，j）出發(fā)有兩種決策。,思考：邊界情況：？,思考：最后的結(jié)果：？,d11=a11di1=di-11+ai1第1列dii=di-1i-1+aii對(duì)角線,maxdn1,dn2dnn,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ù)雜度？,令狀態(tài)dpi表示以Ai作為末尾的連續(xù)序列的最大和（Ai必須作為序列的末尾）。以樣例為例，序列-2,11,-4,13,-5,-2，下標(biāo)分別設(shè)為：0，1，2，3，4，5；dp0dp1dp2dp3dp4dp5問(wèn)題轉(zhuǎn)換為dp0,dp1,dpn-1中的最大者。,最大連續(xù)子序列和（MaximumContinuousSubsequenceSum）,dpi表示以Ai作為末尾的連續(xù)序列的最大和（Ai必須作為序列的末尾）;只有兩種情況：1、這個(gè)最大和的連續(xù)序列只有一個(gè)元素，即以Ai開始，以Ai結(jié)尾；最大和就是Ai本身。2、這個(gè)最大和的連續(xù)序列有多個(gè)元素，從前面某處Ap開始（pi)；一直到Ai結(jié)尾。也就是dpi-1+Ai;Ap+Ai-1+Ai=dpi-1+Ai;,最大連續(xù)子序列和（MaximumContinuousSubsequenceSum）,轉(zhuǎn)移方程：dpi=maxAi,dpi-1+Ai邊界：dp0=A0,最大連續(xù)子序列和（MaximumContinuousSubsequenceSum）,代碼：dp0=A0;for(inti=1;in;i+)dpi=max(Ai,dpi-1+Ai)結(jié)果？,動(dòng)態(tài)規(guī)劃的核心,設(shè)計(jì)狀態(tài)和狀態(tài)轉(zhuǎn)移方程,最長(zhǎng)上升子序列（LIS）NOI1759,問(wèn)題描述：（2s,64M）對(duì)于給定的一個(gè)序列1,2,，若存在112，且12，則稱為長(zhǎng)度為的上升子序列。求出最長(zhǎng)上升子序列的長(zhǎng)度。輸入格式：第一行是序列長(zhǎng)度。（11000）第二行是序列中的個(gè)整數(shù)，這些整數(shù)的取值范圍都在0到10000之間。輸出格式：最長(zhǎng)上升子序列的長(zhǎng)度。,最長(zhǎng)上升子序列（LIS）NOI1759,樣例輸入：71735948樣例輸出：4,上升子序列：1,73,4,8最長(zhǎng)上升子序列：1,3,5,91,3,5,8,如何劃分階段？以從左向右數(shù)的個(gè)數(shù)為階段。狀態(tài)如何描述？,狀態(tài)描述及轉(zhuǎn)移,存在問(wèn)題：最長(zhǎng)上升子序列可能不止一個(gè)；需要了解序列的最后數(shù)值才能繼續(xù)拼接。調(diào)整狀態(tài)描述：以結(jié)尾的“最長(zhǎng)上升子序列”的長(zhǎng)度。狀態(tài)又該如何轉(zhuǎn)移？,階段,狀態(tài)描述及轉(zhuǎn)移,狀態(tài)轉(zhuǎn)移：考慮前一個(gè)數(shù)的位置=max0+1(其中)不妨假定存在一個(gè)0，滿足0邊界條件：0=0,階段,求解步驟,核心代碼,a0=-1;f0=-1;/邊界for(inti=1;i=n;i+)/枚舉階段for(intj=0;ji;j+)/枚舉可能的決策if(ajai)fi=max(fi,fj+1);intans=0;for(inti=1;i=n;+i)ans=max(ans,fi);時(shí)間復(fù)雜度：O(n2)思考：如何求一個(gè)最長(zhǎng)上升子序列？,給定兩個(gè)字符串（或數(shù)字序列）A和B（長(zhǎng)度分別為n和m），求一個(gè)字符串，使得這個(gè)字符串是A和B的最長(zhǎng)公共部分（子序列可以不連續(xù)）。如上圖，字符串“sadstory”與“adminsorry”的最長(zhǎng)公共子序列為“adsory”，長(zhǎng)度為6。暴力枚舉？時(shí)間復(fù)雜度為？時(shí)間復(fù)雜度？,例5：最長(zhǎng)公共子序列（LongestCommonSubsequence，LCS）,狀態(tài)定義：令dpij表示字符串A的i號(hào)位和字符串B的j號(hào)位之前的LCS長(zhǎng)度（下標(biāo)從1開始）。如：dp45表示“sads”與“admin”的LCS長(zhǎng)度。轉(zhuǎn)移方程：兩種情況：1.Ai=Bj,試分析dp462.Ai!=Bj,試分析dp33試試看？你能寫出轉(zhuǎn)移方程嗎？,例5：最長(zhǎng)公共子序列（LongestCommonSubsequence，LCS）,狀態(tài)定義：令dpij表示字符串A的i號(hào)位和字符串B的j號(hào)位之前的LCS長(zhǎng)度（下標(biāo)從1開始）。如：dp45表示“sads”與“admin”的LCS長(zhǎng)度。轉(zhuǎn)移方程：兩種情況：dpij=dpi-1j-1+1,Ai=Bjmax(dpi-1j,dpij-1),Ai!=Bj邊界？,例5：最長(zhǎng)公共子序列（LongestCommonSubsequence，LCS）,dpi0=dp0j=0（0=i=n,0=j=m）,intlenA=strlen(A+1);intlenB=strlen(B+1);/核心代碼：for(inti=1;i=lenA;i+)for(intj=1;jlenB;j+)if(Ai=Bj)dpij=dpi-1j-1+1;elsedpij=max(dpi-1j,dpij-1)答案：？,例5：最長(zhǎng)公共子序列（LongestCommonSubsequence，LCS）,動(dòng)態(tài)規(guī)劃入門（下）,騎士游歷問(wèn)題,設(shè)有n*m的棋盤（2=n，m=50)；在棋盤上任意一點(diǎn)有一個(gè)中國(guó)象棋的馬，同時(shí)給出起點(diǎn)P和終點(diǎn)Q，求所有從起點(diǎn)出發(fā)到終點(diǎn)的路徑數(shù)目。（馬跳躍有四個(gè)方向）,設(shè)d(i,j)為從(i,j)位置出發(fā)到Q點(diǎn)的路徑條數(shù)。i為行號(hào)，j為列號(hào)。,考察任意一個(gè)位置（i，j）,d(i-2,j+1),d(i-1,j+2),d(i+1,j+2),d(i+2,j+1),d(i,j)=？邊界條件？,d(i,j)=d(i-2,j+1)+d(i-1,j+2)+d(i+1,j+2)+d(i+2,j+1)邊界條件為越界時(shí)d(i,j)=0，d(Q)=1,最低通行費(fèi)（NOI7614）,試題描述：（1s,64M）一個(gè)商人穿過(guò)一個(gè)N*N的正方形的網(wǎng)格，去參加一個(gè)非常重要的商務(wù)活動(dòng)。他要從網(wǎng)格的左上角進(jìn)，右下角出。每穿越中間1個(gè)小方格，都要花費(fèi)1個(gè)單位時(shí)間。商人必須在(2N-1)個(gè)單位時(shí)間穿越出去。而在經(jīng)過(guò)中間的每個(gè)小方格時(shí)，都需要繳納一定的費(fèi)用。這個(gè)商人期望在規(guī)定時(shí)間內(nèi)用最少費(fèi)用穿越出去。請(qǐng)問(wèn)至少需要多少費(fèi)用？注意：不能對(duì)角穿越各個(gè)小方格（即，只能向上下左右四個(gè)方向移動(dòng)且不能離開網(wǎng)格）。,最低通行費(fèi)（NOI7614）,輸入要求：第一行是一個(gè)整數(shù)，表示正方形的寬度N(1=N100)；后面N行，每行N個(gè)不大于100的整數(shù)，為網(wǎng)格上每個(gè)小方格的費(fèi)用。輸出要求：至少需要的費(fèi)用。,最低通行費(fèi),樣例輸入：51468102571517689182010111219212023252933樣例輸出:109,109=1+2+5+7+9+12+19+21+33,因?yàn)楸仨氃?2N-1)個(gè)單位時(shí)間穿越出去，所以只能向右或者向下走。,最低通行費(fèi),劃分階段：按從上到下、從左及右的順序到達(dá)第i行第j列狀態(tài)描述：表示從左上角出發(fā)，到達(dá)第i行、第j列時(shí)的最低通行費(fèi)用。轉(zhuǎn)移方程：=min1，1+邊界條件：0=0=，11=11答案：,表格化,從左到右，從上到下，注意邊界！,列,行,33=min23，32+33,核心代碼,memset(f,0 x3f,sizeof（f）);f11=a11;for(inti=1;i=n;i+)for(intj=1;jn時(shí)，d(i,j)=0,j=1;i-)for(intj=0;j=vi)fij=max(dij,di+1j-vi+wi);,d(i,j)=maxd(i+1,j),d(i+1,j-vi)+Wi,狀態(tài)的確定2,對(duì)稱的思考：我們用f(i,j)表示把前i個(gè)物品裝到體積是j的背包中的最大總重量。則有f(i,j)=maxf(i-1,j),f(i-1,j-vi)+Wi邊界是i=0時(shí)為0,j0時(shí)為負(fù)無(wú)窮。答案是f(n,c),代碼,for(inti=1;i=vi)fij=max(fij,fi-1j-vi