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

1、動態(tài)規(guī)劃動態(tài)規(guī)劃郭郭 陽陽 東北大學(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)和重疊子問題熟練有向無環(huán)圖（DAG）上動態(tài)規(guī)劃的常見思路、兩種狀態(tài)定義方法和刷表法掌握記憶化搜索在實現(xiàn)方面的注意事項掌握記憶化搜索和遞推中輸出方案的方法動態(tài)規(guī)劃的重要性動態(tài)規(guī)劃是算法競賽的寵兒 幾乎所有算法競賽或招聘中都有這種題目數(shù)字三角形問題問題描述a. 第i層有i個結(jié)點；b. 每個結(jié)點賦予一個非負(fù)整數(shù)；c. 從頂層按箭頭走到底層，如何走使途中數(shù)和盡量大？問題分析 若有n層，則完整路線共有 ? 條； 12n當(dāng)n很大時遍歷法的速度將讓人無法忍受數(shù)字三角形問題狀態(tài)

2、a. 給結(jié)點編號b. 把位置(i,j)看成一個狀態(tài)；c. 定義狀態(tài)(i,j)的指標(biāo)函數(shù)d(i,j)為從結(jié)點(i,j)出發(fā)時能得到的最大和（包括結(jié)點(i,j) 本身的值）注意：在這個狀態(tài)定義下，原問題的解是d(1,1)。數(shù)字三角形問題狀態(tài)轉(zhuǎn)移方程 d(i,j)=a(i,j)+maxd(i+1,j), d(i+1,j+1) 其中a(i,j)是結(jié)點中的值。 原理：如果連“從(i+1,j)出發(fā)走到底部”這部分的和都不是最大，加上a(i,j)之后肯定也不是最大的。這個性質(zhì)稱為最優(yōu)子結(jié)構(gòu)，也描述為“全局最優(yōu)解包含局部最優(yōu)解”數(shù)字三角形問題遞歸算法遞歸算法：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ù)計算；(3) 調(diào)用關(guān)系樹共有 ？ 個結(jié)點 21n11 (1 2 )1+2+4+2211 2nnn程序Prog1數(shù)字三角形問題遞推算法遞推算法：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、保證每個結(jié)點只訪問一次(3) 時間復(fù)雜度： O( )2n程序Prog3數(shù)字三角形問題 - 總結(jié)遍歷法：完整路線有 條，讓人無法忍受；遞歸法：共 個結(jié)點需要計算指標(biāo)，重復(fù)計算；遞推法：共有 個結(jié)點需要計算指標(biāo)，無重復(fù)計算，需要事先確定計算順序（逆序枚舉）；記憶化搜索法：共有 個結(jié)點需要計算指標(biāo)，無重復(fù)計算，不必事先確定各狀態(tài)的計算順序，但需要記錄每個狀態(tài)“是否已經(jīng)計算過”。12n21n(1)/ 2n n(1)/ 2n n22nn計算量從是一個巨大的優(yōu)化??？作業(yè)一：數(shù)字三角形 找出數(shù)字之和最大和最小的路徑分別打印出來找出數(shù)字之和最大和最小的路徑分別打印出來有向無環(huán)圖（DAG）上的動態(tài)規(guī)劃DAG：D

5、irected Acyclic Graph非有向無環(huán)圖：很多問題很多問題 DAG上的最長路、最短路或路徑計數(shù)問題上的最長路、最短路或路徑計數(shù)問題矩形編號DAG模型之一：嵌套矩形問題問題描述問題描述：有n個矩形，每個矩形可用兩整數(shù)a, b描述(長和寬)。矩形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ù)：選出盡量多的矩形排成一行，下一個嵌套前一個。如果有多解，矩形編號的字典序盡量小。分析分析： (1) “可嵌套”是二元關(guān)系，可用圖來建模； (2) 該圖定是DAG，

6、因為自己不能嵌套自己； (3) 本質(zhì)上求DAG上的最長路徑。ABCD 0) return ans; ans = 1; for (int j = 1; j=n; j+) if (Gij) ans = max(ans, dp(j) +1); return ans;引用等于給變量起了另一個名字，用引用名=使用該變量，引用實際是地址傳遞，因為引用名和變量用的是同一個內(nèi)存。用用i=1,，6來表示來表示A,F最終有最終有3條長度為條長度為3的最長嵌套序列，如何確定字典序最小的結(jié)果呢？的最長嵌套序列，如何確定字典序最小的結(jié)果呢？嵌套矩形問題 - 字典序最小有多個最優(yōu)解，如何選擇矩形編號的字典序最小？(1)

7、將所有指標(biāo)d值計算出來后，選擇最大di所對應(yīng)的i。若有多個i, 則選擇最小的i, 以保證字典序最小。如：如：d(A)=d(H)=3; 則選矩形則選矩形A作為最長嵌套序列的起點。作為最長嵌套序列的起點。(2) 然后選擇滿足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個矩形出發(fā)按字典序最小的嵌套結(jié)果個矩形出發(fā)按字典序最小的嵌套結(jié)果程序Prog

8、A1作業(yè)二：嵌套矩形問題已知矩形分別為： 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)問題：找出字典序最小的最長矩形嵌套序列嵌套矩形問題 - 字典序最小問題一：若想打印出所有方案，如何編寫程序？ 問題二：若把狀態(tài)定義為“d(i)表示以結(jié)點i為終點的最長路徑長度”，如何求最優(yōu)值？問題二中很難打印字典序最小的方案，why？因為此時是從右向左確定矩形，從右向左字母都因為此時是從右向左確定矩形，從右向左字母都取最小并不能保證整體字典序最小。例如：取最小并不能保證整體字典序最小。例如：

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

10、dS值表達(dá)“無法到達(dá)”d數(shù)組的長度等于整數(shù)數(shù)組的長度等于整數(shù)S硬幣問題 - 特殊值表示“沒算過”（記憶化搜索）程序：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;固定起點固定起點按位左移，等于按位左移，等于-230. 表表示示S不能正常分解為不能正常分解為0又是引用又是引用硬幣類數(shù)硬幣類數(shù)嵌套問題是滿足嵌套問題是滿足G(i,j)=1可嵌套性，可嵌套性，這里采用的是只要這里采用的是只

11、要大于幣值，就相當(dāng)大于幣值，就相當(dāng)于可嵌套了于可嵌套了程序ProgA2建長度為S的數(shù)組vis, 使visi表示狀態(tài)i是否被訪問過初始化 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;硬幣問題 - 新建數(shù)組標(biāo)簽（記憶化搜索）以占用一些內(nèi)存為代價增強程序的可讀性，減少出錯的可能程序ProgA3硬幣問題 - 遞推法同時求最大和最

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個分量存的是從錢數(shù)個分量存的是從錢數(shù)i到到0的的最小和最大分解長度最小和最大分解長度從小到大額求最小和最大分解長度從小到大額求最小和最大分解長度 設(shè)設(shè)V1

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

14、axv0+1)=2;程序ProgA4硬幣問題 輸出字典序最小的方案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)即可此時此時d=minv此時此時d=maxv從小到大的循環(huán)保證從小到大的循環(huán)保證了字典序最小方案了字典序最小方案分解中第分解中第 i 類硬幣的個數(shù)類硬幣的個數(shù)硬幣問題 遞推同時記錄路徑，最后打印遞推時直接用數(shù)組min_

15、coinS記錄滿足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ù)組避免