動(dòng)態(tài)規(guī)劃forXP

1、動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃郭郭 陽(yáng)陽(yáng) 東北大學(xué)數(shù)學(xué)系東北大學(xué)數(shù)學(xué)系 2015 2015年年6 6月月學(xué)習(xí)目標(biāo)理解狀態(tài)和狀態(tài)轉(zhuǎn)移方程理解最優(yōu)子結(jié)構(gòu)和重疊子問(wèn)題熟練有向無(wú)環(huán)圖（DAG）上動(dòng)態(tài)規(guī)劃的常見(jiàn)思路、兩種狀態(tài)定義方法和刷表法掌握記憶化搜索在實(shí)現(xiàn)方面的注意事項(xiàng)掌握記憶化搜索和遞推中輸出方案的方法動(dòng)態(tài)規(guī)劃的重要性動(dòng)態(tài)規(guī)劃是算法競(jìng)賽的寵兒 幾乎所有算法競(jìng)賽或招聘中都有這種題目數(shù)字三角形問(wèn)題問(wèn)題描述a. 第i層有i個(gè)結(jié)點(diǎn)；b. 每個(gè)結(jié)點(diǎn)賦予一個(gè)非負(fù)整數(shù)；c. 從頂層按箭頭走到底層，如何走使途中數(shù)和盡量大？問(wèn)題分析 若有n層，則完整路線(xiàn)共有 ? 條； 12n當(dāng)n很大時(shí)遍歷法的速度將讓人無(wú)法忍受數(shù)字三角形問(wèn)題狀態(tài)

2、a. 給結(jié)點(diǎn)編號(hào)b. 把位置(i,j)看成一個(gè)狀態(tài)；c. 定義狀態(tài)(i,j)的指標(biāo)函數(shù)d(i,j)為從結(jié)點(diǎn)(i,j)出發(fā)時(shí)能得到的最大和（包括結(jié)點(diǎn)(i,j) 本身的值）注意：在這個(gè)狀態(tài)定義下，原問(wèn)題的解是d(1,1)。數(shù)字三角形問(wèn)題狀態(tài)轉(zhuǎn)移方程 d(i,j)=a(i,j)+maxd(i+1,j), d(i+1,j+1) 其中a(i,j)是結(jié)點(diǎn)中的值。 原理：如果連“從(i+1,j)出發(fā)走到底部”這部分的和都不是最大，加上a(i,j)之后肯定也不是最大的。這個(gè)性質(zhì)稱(chēng)為最優(yōu)子結(jié)構(gòu)，也描述為“全局最優(yōu)解包含局部最優(yōu)解”數(shù)字三角形問(wèn)題遞歸算法遞歸算法：int solve(int i, int j) r

3、eturn aij + (i=n?0:max(solve(i+1,j), solve(i+1,j+1);(1) 輸入solve(1,1)即可遞歸出結(jié)果；(2) 正確但效率低，大量重復(fù)計(jì)算；(3) 調(diào)用關(guān)系樹(shù)共有 ？ 個(gè)結(jié)點(diǎn) 21n11 (1 2 )1+2+4+2211 2nnn程序Prog1數(shù)字三角形問(wèn)題遞推算法遞推算法：int i, j; for(j=1; j=1; i-) for(j=1; j=0 ) return dij; return dij =aij + (i = n ? 0 : max(solve(i+1, j), solve(i+1, j+1); (2) 雖遞歸，但判斷dij=0

4、保證每個(gè)結(jié)點(diǎn)只訪(fǎng)問(wèn)一次(3) 時(shí)間復(fù)雜度： O( )2n程序Prog3數(shù)字三角形問(wèn)題 - 總結(jié)遍歷法：完整路線(xiàn)有 條，讓人無(wú)法忍受；遞歸法：共 個(gè)結(jié)點(diǎn)需要計(jì)算指標(biāo)，重復(fù)計(jì)算；遞推法：共有 個(gè)結(jié)點(diǎn)需要計(jì)算指標(biāo)，無(wú)重復(fù)計(jì)算，需要事先確定計(jì)算順序（逆序枚舉）；記憶化搜索法：共有 個(gè)結(jié)點(diǎn)需要計(jì)算指標(biāo)，無(wú)重復(fù)計(jì)算，不必事先確定各狀態(tài)的計(jì)算順序，但需要記錄每個(gè)狀態(tài)“是否已經(jīng)計(jì)算過(guò)”。12n21n(1)/ 2n n(1)/ 2n n22nn計(jì)算量從是一個(gè)巨大的優(yōu)化！？作業(yè)一：數(shù)字三角形 找出數(shù)字之和最大和最小的路徑分別打印出來(lái)找出數(shù)字之和最大和最小的路徑分別打印出來(lái)有向無(wú)環(huán)圖（DAG）上的動(dòng)態(tài)規(guī)劃DAG：D

5、irected Acyclic Graph非有向無(wú)環(huán)圖：很多問(wèn)題很多問(wèn)題 DAG上的最長(zhǎng)路、最短路或路徑計(jì)數(shù)問(wèn)題上的最長(zhǎng)路、最短路或路徑計(jì)數(shù)問(wèn)題矩形編號(hào)DAG模型之一：嵌套矩形問(wèn)題問(wèn)題描述問(wèn)題描述：有n個(gè)矩形，每個(gè)矩形可用兩整數(shù)a, b描述(長(zhǎng)和寬)。矩形X(a,b)可以嵌套在矩形Y(c,d)中，當(dāng)且僅當(dāng)ac, bd, 或者ad, bc。 例如: (1, 5) is in (6, 2), but not in (3, 4).任務(wù)任務(wù)：選出盡量多的矩形排成一行，下一個(gè)嵌套前一個(gè)。如果有多解，矩形編號(hào)的字典序盡量小。分析分析： (1) “可嵌套”是二元關(guān)系，可用圖來(lái)建模； (2) 該圖定是DAG，

6、因?yàn)樽约翰荒芮短鬃约海?(3) 本質(zhì)上求DAG上的最長(zhǎng)路徑。ABCD 0) return ans; ans = 1; for (int j = 1; j=n; j+) if (Gij) ans = max(ans, dp(j) +1); return ans;引用等于給變量起了另一個(gè)名字，用引用名=使用該變量，引用實(shí)際是地址傳遞，因?yàn)橐妹妥兞坑玫氖峭粋€(gè)內(nèi)存。用用i=1,，6來(lái)表示來(lái)表示A,F最終有最終有3條長(zhǎng)度為條長(zhǎng)度為3的最長(zhǎng)嵌套序列，如何確定字典序最小的結(jié)果呢？的最長(zhǎng)嵌套序列，如何確定字典序最小的結(jié)果呢？嵌套矩形問(wèn)題 - 字典序最小有多個(gè)最優(yōu)解，如何選擇矩形編號(hào)的字典序最小？(1)

7、將所有指標(biāo)d值計(jì)算出來(lái)后，選擇最大di所對(duì)應(yīng)的i。若有多個(gè)i, 則選擇最小的i, 以保證字典序最小。如：如：d(A)=d(H)=3; 則選矩形則選矩形A作為最長(zhǎng)嵌套序列的起點(diǎn)。作為最長(zhǎng)嵌套序列的起點(diǎn)。(2) 然后選擇滿(mǎn)足d(i)=d(j)+1中字典序最小的j。void print_ans(int i) printf (“%d”, i); for (int j=1; j=n; j+) if (Gij) & (di=dj+1) print_ans(j); break; 它們保證了輸出的是從第它們保證了輸出的是從第i個(gè)矩形出發(fā)按字典序最小的嵌套結(jié)果個(gè)矩形出發(fā)按字典序最小的嵌套結(jié)果程序Prog

8、A1作業(yè)二：嵌套矩形問(wèn)題已知矩形分別為： A(1,2), B(5,8), C(5,9), D(6,9), E(6,8), F(7,9), G(7,10), H(6,10), I(5,10), J(8,11)問(wèn)題：找出字典序最小的最長(zhǎng)矩形嵌套序列嵌套矩形問(wèn)題 - 字典序最小問(wèn)題一：若想打印出所有方案，如何編寫(xiě)程序？ 問(wèn)題二：若把狀態(tài)定義為“d(i)表示以結(jié)點(diǎn)i為終點(diǎn)的最長(zhǎng)路徑長(zhǎng)度”，如何求最優(yōu)值？問(wèn)題二中很難打印字典序最小的方案，why？因?yàn)榇藭r(shí)是從右向左確定矩形，從右向左字母都因?yàn)榇藭r(shí)是從右向左確定矩形，從右向左字母都取最小并不能保證整體字典序最小。例如：取最小并不能保證整體字典序最小。例如：

9、ABCF ABDE硬幣問(wèn)題問(wèn)題描述問(wèn)題描述： 有n種不同面值的硬幣(每種無(wú)限多)。 任務(wù)任務(wù)： 給定非負(fù)整數(shù)S，可以選用多少個(gè)硬幣，使得面值之和恰好為S？輸出硬幣數(shù)目的最小值和最大值。12,nV VV硬幣問(wèn)題固定終點(diǎn)的最長(zhǎng)路和最短路 (求法類(lèi)似)定義狀態(tài)：d(i)為從結(jié)點(diǎn)i出發(fā)到結(jié)點(diǎn)0最長(zhǎng)路徑長(zhǎng)度(1) 與嵌套矩形問(wèn)題相似(2) 不同之處：a. 硬幣問(wèn)題中路徑長(zhǎng)度可以為0（當(dāng)S=0時(shí)），所以不能用d(i)=0來(lái)表示“還沒(méi)有算過(guò)”，即不能把d全設(shè)為0來(lái)初始化，而應(yīng)該賦予一個(gè)一般情況下都取不到的值，如-1，memset(d, -1, sizeof(d)b. 結(jié)點(diǎn)S不一定真的能到達(dá)結(jié)點(diǎn)0，需用特殊的

10、dS值表達(dá)“無(wú)法到達(dá)”d數(shù)組的長(zhǎng)度等于整數(shù)數(shù)組的長(zhǎng)度等于整數(shù)S硬幣問(wèn)題 - 特殊值表示“沒(méi)算過(guò)”（記憶化搜索）程序：int dp(int S) int & ans = dS;if(ans != -1) return ans;ans = -(130);for (int i = 1; i=Vi) ans = max(ans, dp(S-Vi)+1);return ans;固定起點(diǎn)固定起點(diǎn)按位左移，等于按位左移，等于-230. 表表示示S不能正常分解為不能正常分解為0又是引用又是引用硬幣類(lèi)數(shù)硬幣類(lèi)數(shù)嵌套問(wèn)題是滿(mǎn)足嵌套問(wèn)題是滿(mǎn)足G(i,j)=1可嵌套性，可嵌套性，這里采用的是只要這里采用的是只

11、要大于幣值，就相當(dāng)大于幣值，就相當(dāng)于可嵌套了于可嵌套了程序ProgA2建長(zhǎng)度為S的數(shù)組vis, 使visi表示狀態(tài)i是否被訪(fǎng)問(wèn)過(guò)初始化 memset(vis, 0, sizeof(vis)int dp(int S) if (visS) return dS;visS = 1;int & ans = dS;ans = -(130);for (int i = 1; i=Vi) ans = max(ans, dp(S-Vi)+1);return ans;硬幣問(wèn)題 - 新建數(shù)組標(biāo)簽（記憶化搜索）以占用一些內(nèi)存為代價(jià)增強(qiáng)程序的可讀性，減少出錯(cuò)的可能程序ProgA3硬幣問(wèn)題 - 遞推法同時(shí)求最大和最

12、小minv0 = maxv0=0;for(int i=1; i=S; i+) minvi = INF; maxvi = -INF; for(int i = 1; i=S; i+) for (int j =1; j= Vj ) minvi = min(minvi, minvi-Vj+1); maxvi = max(maxvi, maxvi-Vj+1); printf(“%d %dn”, minvS, maxvS);minv和和maxv中第中第i個(gè)分量存的是從錢(qián)數(shù)個(gè)分量存的是從錢(qián)數(shù)i到到0的的最小和最大分解長(zhǎng)度最小和最大分解長(zhǎng)度從小到大額求最小和最大分解長(zhǎng)度從小到大額求最小和最大分解長(zhǎng)度 設(shè)設(shè)V1

13、=3; V2=6; 當(dāng)當(dāng)i=3時(shí)時(shí), minv3 = min(minv3, minvi-V1+1)=min(INF, minv0+1)=1;同理，同理，maxv3=1; 當(dāng)當(dāng)i=5時(shí)？時(shí)？當(dāng)當(dāng)i=6, j=1時(shí)，時(shí)，minv6=min(minv6, minv6-V1+1)=min(INF, minv3+1)= 2; maxv6=max(maxv6,maxv6-V1+1)=max(-INF,maxv3+1)=2;當(dāng)當(dāng)i=6, j=2時(shí)，時(shí)， minv6=min(minv6, minv6-V2+1)= min(2, 1)=1; maxv6=max(maxv6,maxv6-V2+1)=max(2,m

14、axv0+1)=2;程序ProgA4硬幣問(wèn)題 輸出字典序最小的方案void print_ans(int* d, int S) for(int i =1; i=Vi & dS = dS-Vi+1) printf(%d, i); numi +; print_ans(d, S-Vi); break; 執(zhí)行print_ans(minv, S)和print_ans(maxv, S)即可此時(shí)此時(shí)d=minv此時(shí)此時(shí)d=maxv從小到大的循環(huán)保證從小到大的循環(huán)保證了字典序最小方案了字典序最小方案分解中第分解中第 i 類(lèi)硬幣的個(gè)數(shù)類(lèi)硬幣的個(gè)數(shù)硬幣問(wèn)題 遞推同時(shí)記錄路徑，最后打印遞推時(shí)直接用數(shù)組min_

15、coinS記錄滿(mǎn)足minvS=minvS-Vj+1的最小的j。for(int i = 1; i=S; i+) for (int j =1; j= Vj ) if (minvi (minvi-Vj +1) minvi = minvi-Vj+1; min_coini = j; if (maxvi (maxvi-Vj+1) maxvi = maxvi-Vj+1; max_coini = j; 求出min_coin和max_coin后，調(diào)用print_ans(min_coin, S)和print_ans(max_coin, S)即可得各自字典序最小路徑。void print_ans(int* d, int S) while(S) printf(%d, dS); numdS +; S -= VdS; 典型的“用空間換時(shí)間”：用數(shù)組避免