概念
維基百科的定義如下：
dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.
從中我們知道動態(tài)規(guī)劃關(guān)注三點：
- 把一個問題劃分為若干相似的子問題
- 所有的子問題只需要解決一次
- 存儲子問題的解
動態(tài)規(guī)劃所涉及的幾個重要概念也如下所示：
- 最優(yōu)子結(jié)構(gòu)：每個階段的最優(yōu)狀態(tài)可以從之前某個階段的某個或某些狀態(tài)得到。即思考大問題的最優(yōu)解是如何由小問題的最優(yōu)解得到的。
- 無后效性：如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受此階段以前各段狀態(tài)的影響 - “未來和過去無關(guān)”
- 邊界：通常是問題的結(jié)束條件
- 狀態(tài)轉(zhuǎn)移公式：說明了問題的每一階段與上一個/一些階段的相互關(guān)系
- 子問題重疊性質(zhì)：在用遞歸算法自頂向下對問題進行求解時，每次產(chǎn)生的子問題并不總是新問題，有些子問題會被重復(fù)計算多次。動態(tài)規(guī)劃算法對此進行了優(yōu)化，對每個子問題只需要計算一次，把計算結(jié)果存儲在表格中，便于下次使用
算法設(shè)計
一個動態(tài)規(guī)劃算法基本可以分為以下步驟：
- 從題目中確定最優(yōu)子結(jié)構(gòu)是什么
- 確定問題的邊界條件
- 根據(jù)上述兩步構(gòu)建數(shù)學(xué)模型，得到相應(yīng)的狀態(tài)轉(zhuǎn)移方程
- 根據(jù)數(shù)學(xué)模型進行代碼編寫
例題一
有一座高度是10級臺階的樓梯，從下往上走，每跨一步只能向上1級或者2級臺階。要求用程序來求出一共有多少種走法。
解析
假設(shè)0-9級臺階共有X個走法，0-8級臺階共有Y個走法，則總共的走法共有X+Y個走法，如下圖所示：
對于8級臺階到10臺階，只存在跨越2步這個可能，因為若到了8級臺階之后，每次跨越1步，就到了9級臺階，此種走法包含到了9級臺階的X走法之中。
綜上可知，到9級臺階的所有走法由到第8級臺階和第7級臺階組成….，以此類推。
無后效性體現(xiàn)在8級臺階之后的所有走法不受以前各級走法的影響。
數(shù)學(xué)建模
使用數(shù)學(xué)公式可表示為 F (10) = F (9) + F (8) ，其可以看作為最優(yōu)子結(jié)構(gòu)，則以此類推 F (9) = F (8) + F (7)…, 從而可以得到如下公式：
? F (1) = 1;
? F (2) = 2;
? F (n) = F (n-1) + F (n-2);
從上面的公式可以看出 F (1) = 1，F (2) = 2 稱為問題的邊界，若一個問題沒有邊界，則永遠(yuǎn)無法得到有限的結(jié)果，F (n) = F (n-1) + F (n-2) 是狀態(tài)轉(zhuǎn)移方程，說明了問題的每一階段與上一個/一些階段的相互關(guān)系。
代碼實現(xiàn)
1. 遞歸實現(xiàn)
int getClimbingWays(int n){
if (n < 1){
return 0;
}
if (n == 1){
return 1;
}
if (n == 2){
return 2;
}
return getClimbingWays(n-1) + getClimbingWays(n - 2);
}
如下圖遞歸的次數(shù)類似形成如下二叉樹，每個節(jié)點表示遞歸方法所計算的次數(shù)，二叉樹高度為N-1，節(jié)點個數(shù)接近2的N-1次方個，隨遞歸方法的時間復(fù)雜度為O(N^2)。
2. 備忘錄算法
使用遞歸算法有大量的重復(fù)計算，就像下圖所示，
int getClimbingWays(int n, HashMap<Integer, Integer> memo){
if (n < 1){
return 0;
}
if (n == 1){
return 1;
}
if (n == 2){
return 2;
}
if (memo.containsKey(n)){
return memo.get(n);
}else {
int value = getClimbingWays(n -1,memo) + getClimbingWays(n -2, memo);
memo.put(n,value);
return value;
}
}
此時的時間和空間復(fù)雜度都為O(N)
3. 動態(tài)規(guī)劃算法
就算備忘錄算法對算法進行了優(yōu)化，但是其還是要保持所有的子狀態(tài)，造成空間復(fù)雜度過高，并且遞歸算法和備忘錄算法都是自頂向下進行處理，即從 F (N) 慢慢迭代到 F (1) 和 F (2) ，現(xiàn)嘗試自底向上進行求解，只保存當(dāng)前狀態(tài)的前兩個狀態(tài)。分析過程如下：
- F (1)和F (2)為已知道結(jié)果，第一次迭代后，臺階數(shù)為3，走法數(shù)量為3，可知 F (3) 只依賴 F (2) 和 F (2)，可得下表
- 第二次迭代后，臺階數(shù)為4，走法為5，可知 F (4) 只依賴于 F (3) 和 F (2)
其他迭代也如上所示，可知在每次迭代過程中，只需要保存前兩個狀態(tài)即可。
static int getClimbingWays(int n){
if (n < 1){
return 0;
}
if(n == 1){
return 1;
}
if (n == 2){
return 2;
}
int a = 1;
int b = 2;
int ResultWays = 0;
for (int i = 3; i <= n; i++){
ResultWays = a + b;
a = b;
b = ResultWays;
}
return ResultWays;
}
動態(tài)規(guī)劃算法的時間復(fù)雜度為O(N)，空間復(fù)雜度為O(1)。
例題二
有一個國家發(fā)現(xiàn)了5座金礦，每座金礦的黃金儲量不同，需要參與挖掘的工人數(shù)也不同。參與挖礦工人的總數(shù)是10人。每座金礦要么全挖，要么不挖，不能派出一半人挖取一半金礦。要求用程序求解出，要想得到盡可能多的黃金，應(yīng)該選擇挖取哪幾座金礦？
其中金礦1：400金/5人，金礦2：500金/5人，金礦3：200金/3人，金礦4：300金/4人，金礦5：350金/3人
解析
我們的最終要求解的問題是：10人5金礦時的最優(yōu)選擇，我們可以先假設(shè)最優(yōu)子結(jié)構(gòu)為10個人4個金礦挖出最多黃金，但是第五個金礦存在挖或者不挖的可能性，遂可進行擴展分為兩個最優(yōu)子結(jié)構(gòu)：
- 第五個金礦不挖，最優(yōu)子結(jié)構(gòu)為10個人4個金礦挖出最多黃金
- 第五個金礦挖，最優(yōu)子結(jié)構(gòu)為10 - 第五個金礦所需人數(shù)時挖4個金礦的最優(yōu)選擇 + 第五個金礦的黃金儲量
則五個金礦的最優(yōu)選擇就是（10個人4個金礦的最優(yōu)選擇）和（10 - 第五個金礦所需人數(shù)時挖4個金礦的最優(yōu)選擇 + 第五個金礦的黃金儲量）的最大值。
邊界分為兩種情況，說明如下：
- 只有一個金礦，并且工人數(shù)滿足金礦所需人數(shù)要求，遂得到黃金數(shù)量為第
一個金礦的儲量 - 只有一個金礦，若工人數(shù)不滿足金礦所需人數(shù)要求，則得到的黃金數(shù)量為0
數(shù)學(xué)建模
金礦數(shù)量 = N ，工人數(shù)量 = W ，金礦黃金量 G [] ，每個金礦的用工數(shù)量 P [] 。數(shù)組下標(biāo)都從0開始，則5座金礦和4座金礦的最優(yōu)選擇之間存在如下關(guān)系： F (5,10) = MAX (F (4,10), F (4,10-P [4]) +G (4) ) 。可以得到如下狀態(tài)轉(zhuǎn)移方程：
? F (N W ) =0 (N <= 1, W < P [0]) ; // 金礦數(shù)量小于1或一個金礦但是人數(shù)不足
? F (N,W ) = G [0] (N == 1, W >= P [0]) ; // 金礦數(shù)量為1個，需要挖礦人數(shù)符合
? F (N,W ) = F (N-1, W) (N > 1, W < P [N-1]) ; //金礦數(shù)量大于一個，但是剩余的挖礦人數(shù)已經(jīng)不滿足繼續(xù)挖礦
? F (N,W ) = MAX (F (N-1,W ), F (N-1,W-P [N-1]) +G (N -1) ) ; //金礦數(shù)量大于一個，剩余的挖礦人數(shù)滿足繼續(xù)挖礦要求
代碼實現(xiàn)
1. 遞歸實現(xiàn)
public static int getMostGold(int n, int w, int g[], int p[]){
if (n == 1){
return w < p[n-1] ? 0 : g[n-1];
}
if (w < p[n - 1]){
return getMostGold(n-1,w,g,p);
}
return Math.max(getMostGold(n-1,w,g,p), getMostGold(n-1, w - p[n-1],g,p) + g[n-1]);
}
遞歸實現(xiàn)的時間復(fù)雜度為O(2^N)。
2. 動態(tài)規(guī)劃實現(xiàn)
給出一個表格，表格的列表示金礦（ N ），行表示工人數(shù)（ W ），相對應(yīng)的值給定 N 和 W 之后獲得的黃金數(shù)量。
- 得到第一行數(shù)據(jù)如下：
- 當(dāng)工人數(shù)在5-9期間時，設(shè) S =5~9，F (2, S ) = MAX (F (1, S ), F (1, S -5) +500) , 其中都因為 S -5 < 5 ，則5~9格子中，黃金量為500。而當(dāng) _W = 10 _時，F (2, 10) = MAX (F (1, 10), F (1, 5) + 500) 為900。
- 第三個金礦200儲量，需要3人，第四金礦300儲量，需要4人，第五金礦350
儲量，需要3人，依次計算可得下表：
綜上可得出規(guī)律，每個格子的黃金量都是都前一行的一個或者兩個格子推導(dǎo)而來，例如3金礦8工人時，就來自于2金礦5工人+第三個金礦儲量和2金礦8工人，即MAX (F (2, 8 ), F (2, 5) +200) = MAX (500, 200 + 500) = 700。所以我們只需要存儲前一行的數(shù)據(jù)，就可以推導(dǎo)出新的一行。
public void getMostGold(int n, int w, int[] g, int[] p){
int[] preResult = new int [w]; // 保存前一行結(jié)果
int[] results = new int [w]; // 保存當(dāng)前結(jié)果
// 填充第一個金礦的數(shù)據(jù)
for (int i = 0; i < w; i++){
if (i+1 < p[0]){
preResult[i] = 0; // 對應(yīng)數(shù)學(xué)模型 F(N W)=0 (N<=1,W<P[0]);
}else {
preResult[i] = g[0]; // 對應(yīng)數(shù)學(xué)模型 F(N,W)=G[0] (N==1,W>=P[0]);
}
}
showResults(preResult); // 展示第一行的數(shù)據(jù)
//對其他金礦進行處理，從第二個金礦開始,外層循環(huán)時金礦數(shù)量，內(nèi)層循環(huán)時工人數(shù)
for (int i = 1; i < n; i++){
for (int j = 0; j < w; j++){
if (j + 1 < p[i]){
results[j] = preResult[j]; // 對應(yīng)數(shù)學(xué)模型 F(N,W)=F(N-1,W) (N>1,W<P[N-1]);
}else if (j + 1 == p[i]){
results[j] = Math.max(preResult[j],0 + g[i]); // 特殊情況,擁有工人數(shù)剛好與要挖的下一個金礦的所需工人數(shù)相同 若要挖下一個金礦，則挖前一個金礦的人數(shù)為0
}else {
results[j] = Math.max(preResult[j],preResult[j - p[i]] + g[i]); // 對應(yīng)數(shù)學(xué)模型 F(N,W)=MAX(F(N-1,W),F(N-1,W-P[N-1]+G(N-1));
}
}
showResults(results);
preResult = results.clone();
// preResult = results; 不可直接進行引用的賦值
}
}
public void showResults(int[] results){
for(int i:results){
System.out.print(i+" ");
}
System.out.println();
}
動態(tài)規(guī)劃實現(xiàn)的時間復(fù)雜度為O(N*W)，空間復(fù)雜度為O(W)。
總結(jié)
但是動態(tài)規(guī)劃算法在有些情況下不一定是最好的選擇，當(dāng)5個金礦1000個工人時，因為動態(tài)規(guī)劃的時間和空間復(fù)雜度與W成正比，而遞歸算法與W無關(guān)，其時間和空間復(fù)雜度都不如遞歸算法來的好。
參考資料
[1]. https://mp.weixin.qq.com/s/3h9iqU4rdH3EIy5m6AzXsg
[2]. https://www.zhihu.com/question/23995189
