Dynamic Programming - 演算法筆記

【註： recursion 和recurrence ，中文都翻譯為「遞迴」，然而兩者意義大不相同， ... 空間複雜度分析：總共XY 個問題，所以需要O(XY) 空間，簡單來說就是二維陣列啦！ DynamicProgramming 長江後浪催前浪，一替新人趲舊人。

《張協狀元》 資之深，則取之左右逢其原。

《孟子》 DynamicProgramming 先透過一個簡單的例子，感受一下「動態規劃」吧！ 範例：階乘（Factorial） 1×2×3×⋯×N。

整數1到N的連乘積。

N階乘。

N!。

N!源自(N-1)!，如此就遞迴分割問題了。

陣列的每一格對應每一個問題。

設定第一格的答案，再以迴圈依序計算其餘答案。

constintN=10; intf[N]; voidfactorial() { f[0]=0; f[1]=1; for(inti=2;i<=N;++i) f[i]=f[i-1]*i; } constintN=10; voidfactorial() { intf=1; for(inti=2;i<=N;++i) f*=i; } UVa6235681022010323 時間複雜度 總共N個問題，每個問題花費O(1)時間，總共花費O(N)時間。

空間複雜度 求1!到N!：總共N個問題，用一條N格陣列儲存全部問題的答案，空間複雜度O(N)。

只求N!：用一個變數累計乘積，空間複雜度O(1)。

DynamicProgramming:recurrence DynamicProgramming=Divide-and-ConquerMethod+Memoization 動態規劃是分治法的延伸。

當分治法分割出來的問題，一而再、再而三出現，就運用記憶法儲存這些問題的答案，避免重複求解，以空間換取時間。

動態規劃的過程，就是反覆地讀取數據、計算數據、儲存數據。

1.把原問題遞迴分割成許多更小的問題。

（recurrence） 1-1.子問題與原問題的求解方式皆類似。

（optimalsub-structure） 1-2.子問題會一而再、再而三的出現。

（overlappingsub-problems） 2.設計計算過程： 2-1.確認每個問題需要哪些子問題來計算答案。

（recurrence） 2-2.確認總共有哪些問題。

（statespace） 2-3.把問題一一對應到表格。

（lookuptable） 2-4.決定問題的計算順序。

（computationalsequence） 2-5.確認初始值、計算範圍。

（initialstates/boundary） 3.實作，主要有兩種方式： 3-1.Top-down 3-2.Bottom-up 1.recurrence 遞迴分割問題時，當子問題與原問題完全相同，只有數值範圍不同，我們稱此現象為recurrence，再度出現、一再出現之意。

【註：recursion和recurrence，中文都翻譯為「遞迴」，然而兩者意義大不相同，讀者切莫混淆。

】 此處以爬樓梯問題當作範例。

先前於遞歸法章節，已經談過如何求踏法，而此處要談如何求踏法數目。

踏上第五階，只能從第四階或從第三階踏過去。

因此「爬到五階」源自兩個子問題：「爬到四階」與「爬到三階」。

「爬到五階」的踏法數目，就是總合「爬到四階」與「爬到三階」的踏法數目。

寫成數學式子是「f(5)=f(4)+f(3)」，其中「f(‧)」表示「爬到某階之踏法數目」。

依樣畫葫蘆，得到「f(4)=f(3)+f(2)」、「f(3)=f(2)+f(1)」。

「爬到兩階」與「爬到一階」無法再分割、沒有子問題，直接得到「f(2)=2」、「f(1)=1」。

整理成一道簡明扼要的遞迴公式： f(n)= {1,ifn=1 {2,ifn=2 {f(n-1)+f(n-2),ifn>=3andn<=5 爬到任何一階的踏法數目，都可以藉由這道遞迴公式求得。

n代入實際數值，遞迴計算即可。

為什麼分割問題之後，就容易計算答案呢？因為分割問題時，同時也分類了這個問題的所有可能答案。

分類使得答案的規律變得單純，於是更容易求得答案。

2-1.recurrence f(n)= {1,ifn=1 {2,ifn=2 {f(n-1)+f(n-2),ifn>=3 2-2.statespace 想要計算第五階的踏法數目。

全部的問題是「爬到一階」、「爬到二階」、「爬到三階」、「爬到四階」、「爬到五階」。

至於「爬到零階」、「爬到負一階」、「爬到負二階」以及「爬到六階」、「爬到七階」沒有必要計算。

2-3.lookuptable 建立六格的陣列，儲存五個問題的答案。

表格的第零格不使用，第一格是「爬到一階」的答案，第二格是「爬到二階」的答案，以此類推。

如果只計算「爬完五階」，也可以建立三個變數交替使用。

2-4.computationalsequence 因為每個問題都依賴「階數少一階」、「階數少二階」這兩個問題，所以必須由階數小的問題開始計算。

計算順序是「爬到一階」、「爬到二階」、……、「爬到五階」。

2-5.initialstates/boundary 最先計算的問題是「爬到一階」與「爬到二階」，必須預先將答案填入表格、寫入程式碼，才能繼續計算其他問題。

心算求得「爬到一階」的答案是1，「爬到二階」的答案是2。

最後計算的問題是原問題「爬到五階」。

為了讓表格更順暢、為了讓程式碼更漂亮，可以加入「爬到零階」的答案，對應到表格的第零格。

「爬到零階」的答案，可以運用「爬到一階」的答案與「爬到兩階」的答案，刻意逆推而得。

最後可以把初始值、尚待計算的部份、不需計算的部分，統整成一道遞迴公式： f(n)= {0,ifn<0[Exterior] {1,ifn=0[InitialState] {1,ifn=1[InitialState] {f(n-1)+f(n-2),ifn>=2andn<=5[Computation] {0,ifn>5[Exterior] UVa11069 3.實作 直接用遞迴實作，而不使用記憶體儲存各個問題的答案，是最直接的方式，也是最慢的方式。

時間複雜度O(f(n))。

問題一而再、再而三的出現，不斷呼叫同樣的函式求解，效率不彰。

剛接觸DP的新手常犯這種錯誤。

intf(intn) { if(n==0||n==1) return1; else returnf(n-1)+f(n-2); } 正確的DP，是一邊計算，一邊將計算出來的數值存入表格，以後便不必重算。

這裡整理了兩種實作方式，各有優缺點： 1.Top-down 2.Bottom-up 3-1.Top-down inttable[6]; //表格，儲存全部問題的答案。

boolsolve[6]; //記錄問題是否已經計算完畢 intf(intn) { //[InitialStates] if(n==0||n==1)returntable[n]=1; //[Computation] //如果已經計算過，就直接讀取表格的答案。

if(solve[n])returntable[n]; //如果不曾計算過，就計算一遍，儲存答案。

table[n]=f(n-1)+f(n-2); //將答案存入表格 solve[n]=true; //已經計算完畢 returntable[n]; } voidstairs_climbing() { for(inti=0;i<=5;i++) solve[i]=false; intn; while(cin>>n&&(n>=0&&n<=5)) cout<>n&&(n>=0&&n<=5)) cout<>n&&(n>=0&&n<=5)) cout<1andm>1andn>=m {n,ifm=1 {1,ifn=1 範例：河內塔（TowerofHanoi） f(n)= {f(n-1)+1+f(n-1),ifn>1 {1,ifn=1 DynamicProgramming:counting/optimization 範例：樓梯路線（StaircaseWalk），計數問題 一個方格棋盤，從左上角走到右下角，每次只能往右走一格或者往下走一格。

請問有幾種走法？ 對於任何一個方格來說，只可能「從左走來」或者「從上走來」，答案是兩者相加。

「從左走來」是一個規模更小的問題，「從上走來」是一個規模更小的問題，答案是兩者相加。

二維陣列的每一格對應每一個問題。

設定第零行、第零列的答案，再以迴圈依序計算其餘答案。

時間複雜度分析：令X和Y分別是棋盤的長和寬。

計算一個問題需要O(1)時間（兩個子問題答案相加的時間）。

總共XY個問題，所以計算所有問題需要O(XY)時間。

空間複雜度分析：總共XY個問題，所以需要O(XY)空間，簡單來說就是二維陣列啦！如果不需要儲存所有問題的答案，只想要得到其中一個特定問題的答案，那只需要一維陣列就夠了，也就是O(min(X,Y))空間。

constintX=8,Y=8; intc[X][Y]; voidstaircase_walk() { //[InitialStates] for(inti=0;i>x>>y) cout<0andi<8[Computation] {andj>0andj<8[Computation] {0,ifi>=8orj>=8[Exterior] c(i,j)：從格子(0,0)走到格子(i,j)的走法數目。

遞歸方向 這個問題雙向都可以遞歸。

對於任何一個方格來說，只可能「向右走出」或者「向下走出」。

範例：樓梯路線（StaircaseWalk），極值問題 動態規劃的問題，可以分為「計數問題」和「極值問題」。

方才介紹「計數問題」，現在介紹「極值問題」。

一個方格棋盤，格子擁有數字。

從左上角走到右下角，每次只能往右走一格或者往下走一格。

請問總和最小的走法？（或者總和最大的走法？） constintX=8,Y=8; inta[X][Y]; intc[X][Y]; voidstaircase_walk() { //[InitialStates] c[0][0]=a[0][0]; for(inti=1;i>x>>y) cout<=0&&j>=0;) { out[n++]=p[i][j]; if(p[i][j]==0)i--; elseif(p[i][j]==1)j--; } //印出路線 for(inti=n-1;i>=0;--i) cout<=c[i][j-1])*/ { c[i][j]=c[i][j-1]+a[i][j]; p[i][j]=1; //從左走來 } //反向追蹤路線源頭 intn=0; //outsize for(inti=X,j=Y;i>0&&j>0;) { out[n++]=p[i][j]; if(p[i][j]==0)i--; elseif(p[i][j]==1)j--; } //印出路線 for(inti=n-1;i>=0;--i) cout<0&&j>0;) { int&d=p[i][j]; out[n++]=d; i-=x[d];j-=x[d]; } //印出路線 for(inti=n-1;i>=0;--i) cout<=i;--j) // for(intj=i;j 同類型的動態規劃問題： MatrixChainMultiplication OptimalBinarySearchTree Hu–TuckerCompression MinimumWeightTriangulationofConvexPolygon Cocke–Younger–KasamiAlgorithm UVa348442 範例：LongestIncreasingSubsequence 把解答編入狀態之中。

詳見「LongestIncreasingSubsequence」。

範例：WeightedIntervalSchedulingProblem 有了權重之後GreedyMethod就不管用了。

範例：WordWrap 一大段英文，適度換行，讓文字不超過紙張邊界，美化版面。

窮舉行數，再窮舉一行擠入多少字數。

自行定義留白的代價。

UVa709848400 範例：BitonicEuclideanTSP ICPC4791 範例：期望值 UVa10900 範例：二進位數字 ICPC48335101 範例：SequenceCombination【尚無正式名稱】 逐步消去一連串同色彩珠，找到步驟最少的消除方式。

UVa1055911523 範例：節省記憶體 ICPC6435 範例：??? ProblemJ:SubwayTiming http://www.csc.kth.se/~austrin/icpc/finals2009solutions.pdf ICPC4454 http://codeforces.com/blog/entry/13007 ICPC6669 DynamicProgramming:bitset bitset bitset是一個二進位數字，每一個bit分別代表每一件東西，1代表開啟，0代表關閉。

例如現在有十個燈泡，編號設定為零到九，其中第零個、第三個、第九個燈泡是亮的，剩下來的燈泡是暗的。

我們用一個10bit的二進位數字1000001001，表示這十個燈泡的亮暗狀態。

建立一個大小為2¹⁰的陣列，便囊括了所有可能的狀態。

陣列的每一格，就代表一種燈泡開關的狀態。

intarray[1<<10]; array[521]=想記錄的數字; /*1000001001(2進位)=521(10進位)*/ 當狀態數量呈指數成長，可以利用bitset作為狀態。

UVa10952ICPC4794 範例：MaximumMatching 以線相連的兩物，可以配對在一起。

求最大配對數目暨配對方式。

「MaximumMatching」有多項式時間演算法，可是很難實作；動態規劃雖然慢了些，是指數時間演算法，但是容易實作。

移除匹配成一對的點，就得到遞迴公式。

f[S+{i}+{j}]=max{f[S]+adj[i,j]}i,j∉S f[S]=max{f[S-{i}-{j}]+adj[i,j]}i,j∉S 使用bitset，已匹配標成1，未匹配標成0。

時間複雜度O(2ᴺN²)，空間複雜度O(2ᴺ)。

這個方法需要大量記憶體，所以無法計算N很大的情況，何況編譯器也不准我們建立太大的陣列，N=28就是極限了。

這個方法同時也需要大量時間，以現在的個人電腦來說，N=17就已經要花上幾分鐘才能求出答案了。

//top-downDP constintN=10; intadj[N][N]; //adjacencymatrix。

連線為1，否則為0。

intdp[1< 這個演算法可以再修正，讓時間複雜度成為O(2ᴺN)。

各位可以試試看。

UVa1088810911114391029611156 範例：HamiltonPath 找到一條路徑，剛好每一個點都去過一次。

有可能找不到。

「HamiltonPath」尚無多項式時間演算法。

直覺的解法是backtracking，窮舉所有點的各種排列方式，一種排列方式當作一條路徑，判斷是不是HamiltonPath。

運用動態規劃，可以減少計算時間。

拆掉一條路徑的最後一條邊，就得到遞迴公式。

需要額外維度，記錄路徑終點。

path[S+{j},j]=or_all{path[S,i]&&adj[i,j]}i∈S,j∉S path[S,j]=or_all{path[S-{j},i]&&adj[i,j]}i∈S,j∉S 時間複雜度O(2ᴺN²)，空間複雜度O(2ᴺ)。

constintN=10; booladj[N][N]; //adjacencymatrix booldp[1< UVa21610068104961081810937109441060510890265 範例：不重複路線（Self-avoidingWalk） 先前介紹過樓梯路線（StaircaseWalk）。

樓梯路線問題，只能往兩個方向走，可以簡單的遞迴分割，得到多項式時間演算法。

不重複路線問題，可以往四個方向走，無法簡單的遞迴分割，只有指數時間演算法。

儘管如此，不重複路線還是可以使用動態規劃。

中文網路稱為「插头DP」或「轮廓线DP」。

UVa1057210531ICPC47894793 範例：DominoTiling UVa11741 DynamicProgramming:stack/deque 概論 F[n]=min/max{F[i]⋅W[i]+C[i]} 0<=i --------------------------------------- stack|F[2]|F[4]|F[6]|...|F[10] --------------------------------------- ^^^^^^^extractmaximum cleantopsuntilmonotonicity thenpushnewF[i]attop F[i]塞入尾端。

塞入前，先彈出尾端數值們，使得F[i]塞入尾端之後，stack呈嚴格遞增。

最大值從尾端彈出。

範例：LargestEmptyRectangle 詳見「LargestEmptyRectangle」。

範例：AllNearestSmallerValues deque 滑動視窗極值。

deque保持嚴格遞增（嚴格遞減），以便即時獲取過往最小值（最大值）、即時移除已處理數值。

minimizeproblem keepmonotoneincreasing----> -------------------------------------- dequeF[2]|F[4]|F[6]|...|F[10] -------------------------------------- ^^^^^^^^^^^^^ extractminimumcleantailsuntilmonotonicity thenpushnewF[i]atend F[i]塞入尾端。

塞入前，先清除尾端數值，使得F[i]塞入尾端之後，deque呈嚴格遞增。

塞入後，再彈出頭端數值們，使得元素個數符合滑動視窗大小。

最小值從頭端彈出。

中文網路稱為「单调队列优化」。

ICPC4327 範例：MaxiumSumSubarray 詳見「MaxiumSumSubarray」。

範例：MaximumAverageSubarray 詳見「MaxiumAverageSubarray」。

由於斜率是關鍵，因此中文網路稱為「斜率优化」。

DynamicProgramming:convexhull 先備知識 先備知識是「ConvexHull」、「Point-LineDuality」、「FenchelDuality」。

概論 F[n]=min/max{F[i]⋅W[n]+C[i]} 0<=i=1;--i) //區間起點 { c[i][k]=1e9; for(intj=i;j<=k;++j) //分割點 if(c[i][j-1]+c[j+1][k]+sum(i,k)=1;--i) //區間起點 { c[i][k]=1e9; for(intj=i;j<=k;++j) //分割點 if(c[i][j-1]+c[j+1][k]