前言

動態規劃的主要思想

• 將原問題分解為更簡單的子問題（重要的事情默念三遍），通過解決子問題來解決原問題。
• 記憶化搜索(存儲子問題的解，解決重疊子問題多次計算的問題)。

動態規劃的三要素:

• 最優子結構：原問題最優解所包含的子問題都是最優的（子問題的最優解能組合成原問題的最優解）則該子問題為原問題的最優子結構。
• 狀態轉移方程：表示前后階段關系的方程（原問題與子問題的關系方程）。
• 邊界：無需繼續分解，可以直接得到值的問題（沒有邊界的問題是無解的）。

這里概括了一下動態規劃的主要思想和要素，讓我們暫時帶著疑問，先來看幾個經典問題。

動態規劃經典問題

書架放法問題

假設有一個書架，最多容納10本書。現在我們要把這個書架放滿，條件是，每次只能放1本或者2本。問：放滿十本書總共有多少種放法?

下圖為其中一種方法：每次只放1本。我們可以表示為1,1,1,1,1,1,1,1,1,1

下圖為其中另外一種方法：每次只放2本。我們可以表示為2,2,2,2,2

顯然上面的這兩種放法都是最簡單的放法，總放法遠遠不止這兩種。還記得我們默念的那一句嗎，我們現在就想這個復雜的問題能不能分解成更簡單的子問題。

文字來描述問題未免過于啰嗦，為了更好地分析問題，我們先對原問題進行建模。

問題建模

我們需要對問題進行建模，用一個方程來普適化表達這一問題。建立方程就需要確定變量（狀態），變量的確定可以看我們在問題的每個階段中做決策時受到什么因素影響。題目中限制死了每次只能放1或2本，那么在書架上能放滿書有多少種放法，只跟書架的容量有關系，因此書架的容量可作為方程中的變量。設F(x)的解為將容量為x的書架放滿書的總放法數，則原問題的解為F(10)。

我們反過來想一下，放滿10本書之前書架的狀態是怎么樣的？在放滿10本書之前：

• 書架已經放滿9本（最后一次放1本，可理解為書架只有9的容量）
• 書架已經放滿8本（最后一次放2本，可理解為書架只有8的容量）

放滿9本和放滿8本，分別對應了最后一次放1本和2本，包含了放滿10前一階段的所有情況。因此書架放10本書的總放法數，等同于書架放9本書的總放法數 + 書架放8本書的總放法數。原問題就可以分解成：F(10) = F(9) + F(8)，F(9)和F(8)為F(10)的最優子結構。推廣到一般情況可得到一個方程F(x) = F(x-1) + F(x-2)，(x>1)，這個方程就是狀態轉移方程。 得到這個方程后，我們很容易就可以得到這個問題的解了，這不就是典型的遞歸問題嘛。

遞歸求解

const bookrackRecur = (window.tempF = (bookrack) => {if (bookrack < 3) {return bookrack;}//根據狀態轉移方程F(x) = F(x-1) + F(x-2)return window.tempF(bookrack - 1) + window.tempF(bookrack - 2); })(10); console.log(bookrackRecur); //89 復制代碼

分解問題的思想讓我們很容易就知道了解題的思路，但是上面遞歸的解法有一種問題。會重復計算相同問題。

如圖可以看到原問題分解成子問題時，會出現很多重疊子問題，因此用遞歸自頂向下求解時，會重復求解一些問題，這個算法的時間復雜度是O(2^n)。那么怎么去優化這個算法呢？現在我們就可以用動態規劃了。上文說了動態規劃的另外一個主要思想是記憶化搜索，我們把之前問題的解存儲下來，那么在求解過程中遇到相同問題時，就可以直接得到值了。

動態規劃求解

下面我們轉變下思路，嘗試著自底向上迭代求解。下面借助一張表來說明，F(x)同樣表示為書架放滿x本書的總放法。

x0123...

F(x)	0	1	2	3 (F(2)+F(1))	...

該問題具有邊界：

• F(1)，只放1本書在書架上的放法只有一種：1。
• F(2)，放2本書在書架上的方法有兩種：1,1和2。

根據狀態轉移方程，我們知道F(3)是只依賴F(1)和F(2)的，我們在程序中保存了前兩個問題的解，就可以得到目前問題的解。

const bookrackDP = ((bookrack) => {//為了問題更好的對應數組下標，加入問題0, F(0) = 0//保存前兩個問題的解F(1) = 1, F(2) = 2;let record = [0, 1, 2];for (let i = 0; i <= bookrack; i++) {if (i >= 3) {//記錄問題的解record[i] = record[i - 1] + record[i - 2];}}//根據記錄直接得到問題的解return record[bookrack]; })(10); console.log(bookrackDP); 復制代碼

這種算法的時間復雜度為O(n)。上面的代碼用了數組存儲子問題的解，其實是可以再優化一下的。我們上面分析了，目前問題的解只依賴于前兩個問題，因此用兩個局部變量存儲前兩個問題的解就行了，這里就不再展示代碼了。我們看一個復雜點的問題。

01背包問題

假設有一個運氣爆棚的獵人進入到了彩虹洞中，地精讓這個人從寶庫中任意拿走物品，直到獵人的背包裝不下為止。寶庫中每個物品都有特定的價值和重量，獵人的背包承重有限。那么問題來了，獵人怎么裝物品才能獲得最大價值呢？假設獵人背包最大承重為20公斤，物品重量及價值如下圖：

思路：這是一個多階段的決策問題，每一階段的決策都會影響到下一階段的決策（裝了物品1，可能就會裝不了物品2...）。還是按照分解問題的思想來，得到解題思路再說。同樣地，文字描述未免太過于啰嗦，我們對問題進行建模。

問題建模

還是先確定方程的變量（狀態）。思考一下會影響我們在各階段做決策的因素有什么(一般問題中能直接找到)？

問題求規定背包承重下，所裝物品的最大價值，顯然第一個變量是背包的承重量，設為c(capacity)。

每個物品的價值和重量都不同，選了物品1很可能會影響到后面物品的選擇，同時物品的選與不選會影響到背包的剩余承重量，跟變量c有著關聯。因此寶庫中提供的物品為另外一個變量，設為i。

現在就可以對問題建立方程了：設F(i, c)的解為，從i件物品中，挑選一些物品放入剩余容量為c（capacity）的背包中，使的背包物品價值最大。則原問題的解為F(5, 20)。思考一下，怎么將F(5, 20)分解呢？

選與不選神器

我們可以考慮面對物品5時，選不選的問題。(這個地方著重理解)

首先背包剩余容量必須大于物品5的重量，否則根本放不下，放不下相當于不用考慮物品5，原問題的解等同于從前4件物品中，挑選一些物品放入背包中（目前背包什么都沒裝），背包物品總價值最大。表示為：F(4, 20)。

選了物品5，問題的解為，選了物品5了，背包價值為物品5的價值，再從前4件物品中，挑選一些物品放入背包中（目前背包已裝物品5），背包物品總價值最大。方程表示為F(4, 20 - 物品5重量) + 物品5價值 = F(4, 16) + 5。

不選物品5，等同于不考慮物品5，問題的解為，從前4件物品中，挑選一些物品放入背包中（目前背包什么都沒裝），背包物品總價值最大。表示為：F(4, 20)。

到底選還是不選，判斷選和不選的情況中，哪種情況的背包總價值高，選價值高的情況。max(F(4, 16) + 5, F(4, 20))

根據上面的分析我們就可以得到這個問題的狀態轉移方程了（同樣的我們發現可能會有重疊子問題）：

F(i, c) = max(F(i-1, c-weights[i]) + values[i] , F(i-1, c))， （i > 0）

很容易就可以得到遞歸的解法了

遞歸解法

let goods = [{value: 0, weight: 0}, //方便對應下標{value: 3, weight: 2},{value: 4, weight: 3},{value: 8, weight: 5},{value: 10, weight: 9},{value: 5, weight: 4} ];const knapsackRecur = ((goods, capacity) => {let recurF = (curIdx, curCapacity) => {if (!curIdx) {return 0;}let weight = goods[curIdx].weight,value = goods[curIdx].value;if (weight > curCapacity) {return recurF(curIdx - 1, curCapacity);}let vPick = recurF(curIdx - 1, curCapacity - weight) + value,vNotPick = recurF(curIdx - 1, curCapacity);return Math.max(vPick, vNotPick);};return recurF(goods.length - 1, capacity); })(goods, 20); console.log(knapsackRecur); //26 復制代碼

我們來看看01背包的動態規劃解法

動態規劃解法

跟書架問題一樣，想辦法將子問題的解記憶化。由于方程里有兩個狀態（變量），因此我們需要用二維數組存儲問題的解。我們先來看看下面這一張表。在線01背包表

可以看到我們將F(i, c)轉換成二維表，i為行（從i件物品中選），c為列(背包容量為c)，每個單元格的值為F(i, c)的解。 我們先隨便看一個單元格。 紅色框起來的單元格（第4行，第13列），意思是：F(3, 12)，從前三件物品中挑選一些物品，使得容量為12的背包價值最大，價值為15。下面我們試著解釋這個值是怎么來的。（可以先是思考一下：選不選神器）

由狀態轉移方程可得：F(3, 12) = max(F(2, 12-5) + 8 , F(2, 12))（綠色部分和藍色部分）所以F(3, 12) = max(F(2, 7) + 8 , F(2, 12)) = max(7+8, 7) = 15。 分析到這里大家應該明白了，現在我們看看自底向上迭代求解的代碼實現。

let goods = [{value: 0, weight: 0}, //方便對應下標{value: 3, weight: 2},{value: 4, weight: 3},{value: 8, weight: 5},{value: 10, weight: 9},{value: 5, weight: 4} ]; const knapsackDP = ((goods, capacity) => {//初始化二維數組，保存子問題的最優解let record = [];for (let i = 0; i < goods.length; i++) {if (!record[i]) {record[i] = [];}let weight = goods[i].weight,value = goods[i].value;for (let c = 0; c <= capacity; c++) {if (!record[i][c]) {record[i][c] = 0;}if (i - 1 < 0) {continue;}//商品i的重量大于背包容量，無法把商品i放到背包里if (weight > c) {record[i][c] = record[i - 1][c];} else {let vPick = record[i - 1][c - weight] + value, //選的情況vNotPick = record[i - 1][c]; //不選的情況record[i][c] = Math.max(vPick, vNotPick); //最優情況}}}return record[goods.length - 1][capacity]; })(goods, 20); console.log(knapsackDP); 復制代碼

總結

動態規劃更像是一種思想，類似分治，把復雜問題分解成多個子問題，簡單化問題。同時記憶化問題的解，爭取每個問題只求解一次，達到優化效果。因此動態規劃適用于含有重疊子問題的問題。解決動態規劃問題的關鍵在于推導出狀態轉移方程。狀態轉移方程的推導過程可以參考如下：

• 在多階段決策問題中，找到影響決策的因素（定義狀態）。
• 根據狀態對問題進行建模（用以狀態為變量的方程來表示問題）。
• 將原問題分解成子問題（確定狀態轉移方程）。

本文屬個人理解，旨在互相學習，有說的不對的地方，師請糾正。轉載請注明原帖

轉載于:https://juejin.im/post/5cf3b2236fb9a07f0052c455

總結

以上是生活随笔為你收集整理的看完就懂系列—动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。