動(dòng)態(tài)規(guī)劃
不知道大家有沒有聽說這樣的說法
? 貪心：一條路走到黑寇损，就一次機(jī)會(huì)藻茂，只能哪邊看著順眼走哪邊驹暑；
? 回溯：一條路走到黑，無數(shù)次重來的機(jī)會(huì)辨赐，還怕我走不出來优俘；
? 動(dòng)態(tài)規(guī)劃：擁有上帝視角，手握無數(shù)平行宇宙的歷史存檔肖油， 同時(shí)發(fā)展出無數(shù)個(gè)未來兼吓；
因此動(dòng)態(tài)規(guī)劃是一種很好用的算法。
經(jīng)典的動(dòng)態(tài)規(guī)劃問題：0-1背包森枪、0-1背包升級(jí)版视搏、青蛙跳變態(tài)版、棋盤的最小路徑等县袱。
什么時(shí)候可以用動(dòng)態(tài)規(guī)劃浑娜？
雖然說有一個(gè)模型三個(gè)特征，但個(gè)人還是通過一個(gè)流程來判斷是否可以使用動(dòng)態(tài)規(guī)劃式散。
【注】一個(gè)模型：多階段決策最優(yōu)解模型
? 三個(gè)特征：最優(yōu)子結(jié)構(gòu)筋遭、無后效性和重復(fù)子問題
個(gè)人總結(jié)流程
我們假設(shè)背包的最大承載重量是 9。我們有 5 個(gè)不同的物品暴拄，每個(gè)物品的重量分別是 2漓滔，2，4乖篷，6响驴，3。在滿足背包最大重量限制的前提下撕蔼，背包中物品總重量的最大值是多少豁鲤？
看問題判斷：
- 找最優(yōu)解
- 是否多階段
畫遞歸樹：
- 從第一個(gè)階段開始（根節(jié)點(diǎn)），觀察有多少種決策可以選擇鲸沮。
- 從第二個(gè)階段開始（子樹）琳骡，從觀察有多少種決策可以選擇。
- 好讼溺，停楣号。這時(shí)候你就大概會(huì)有一種感覺，就是”重復(fù)“。
如上圖是0-1背包問題的遞歸樹竖席，遞歸樹中的每個(gè)節(jié)點(diǎn)表示一種狀態(tài)耘纱，我們用（i, cw）來表示敬肚。其中毕荐，i 表示將要決策第幾個(gè)物品是否裝入背包，cw 表示當(dāng)前背包中物品的總重量艳馒。
PS.圖參考自王爭(zhēng)《數(shù)據(jù)結(jié)構(gòu)與算法之美》
畫狀態(tài)轉(zhuǎn)移表：
- 先畫二維的狀態(tài)轉(zhuǎn)移表憎亚；（這里行列數(shù)代表的意義要明確）
- 手工填一部分狀態(tài)轉(zhuǎn)移表；
- 找到狀態(tài)轉(zhuǎn)移的規(guī)律弄慰；
- 總結(jié)出狀態(tài)轉(zhuǎn)移狀態(tài)方程第美；
代碼實(shí)現(xiàn)
weight: 物品重量，n: 物品個(gè)數(shù)陆爽，w: 背包可承載重量
public int knapsack(int[] weight, int n, int w) {
boolean[][] states = new boolean[n][w+1]; // 默認(rèn)值 false
states[0][0] = true; // 第一行的數(shù)據(jù)要特殊處理什往，可以利用哨兵優(yōu)化
states[0][weight[0]] = true;
for (int i = 1; i < n; ++i) { // 動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移
for (int j = 0; j <= w; ++j) {// 不把第 i 個(gè)物品放入背包
if (states[i-1][j] == true) states[i][j] = states[i-1][j];
}
for (int j = 0; j <= w-weight[i]; ++j) {// 把第 i 個(gè)物品放入背包
if (states[i-1][j]==true) states[i][j+weight[i]] = true;
}
}
for (int i = w; i >= 0; --i) { // 輸出結(jié)果
if (states[n-1][i] == true) return i;
}
return 0;
}
多寫多練，就能有自己的一套方法和技巧慌闭。
推薦從0-1背包和青蛙跳變態(tài)版開始練别威。
補(bǔ)充
還有的動(dòng)態(tài)規(guī)劃問題，是從多個(gè)“方向”而來驴剔。
如棋盤的最短路徑問題：
假設(shè)我們有一個(gè) n 乘以 n 的矩陣 w省古。矩陣存儲(chǔ)的都是正整數(shù)向叉。棋子起始位置在右下角吏颖。我們將棋子從左上角移動(dòng)到右下角腿倚。每次只能向右或者向下移動(dòng)一位济蝉。從左上角到右下角甲葬，會(huì)有很多不同的路徑可以走瘾英。我們把每條路徑經(jīng)過的數(shù)字加起來看作路徑的長(zhǎng)度浩村。那從左上角移動(dòng)到右下角的最短路徑長(zhǎng)度是多少呢露戒？
那么他就會(huì)從兩個(gè)方向來描验，只有可能從 (i, j-1) 或者 (i-1, j) 來白嘁。
因此狀態(tài)轉(zhuǎn)移表變成下圖
我的動(dòng)態(tài)規(guī)劃之路還有很多要學(xué)，大家一起進(jìn)步挠乳！
參考資料
數(shù)據(jù)結(jié)構(gòu)與算法之美 https://time.geekbang.org/column/article/75702
