&emsp;&emsp;動態規劃（Dynamic Programming，DP）是指在給定的約束條件下求最優值的算法，在解決問題的過程，需要經歷多個決策階段，每個決策階段都對應著一組狀態。 &emsp;&emsp;適用于動態規劃解決的問題包含三個特征： &emsp;&emsp;（1）最優子結構：通過子問題的最優解，可推導出問題的最優解，即后面階段的狀態可以通過前面階段的狀態推導出來。 &emsp;&emsp;（2）無后效性：某階段狀態一旦確定，就不受之后階段的決策影響。即子問題的解一旦確定，就不再改變。 &emsp;&emsp;（3）子問題重疊：不同的決策序列，到達某個相同的階段時，可能會產生重復的狀態。即有些子問題會被重復計算多次。 &emsp;&emsp;動態規劃對每個子問題只計算一次，然后將其計算結果保存到一張表中記憶化存儲，以便下次需要同一個子問題解時直接查表，從而獲得較高的效率，降低了時間復雜度。 ## 一、0-1背包 &emsp;&emsp;在之前《[回溯](https://www.cnblogs.com/strick/p/13384038.html)》一文中也提到了0-1背包問題，而此處會在背包重量限制的前提下，計算裝入物品的最大總價值。 &emsp;&emsp;假設背包容量為4斤，吉他（1斤，價值1500）、音響（4斤，價值3000）和筆記本（3斤，價值2000），求背包的最大價值（題目來源于《圖解算法 9.1節》）。 &emsp;&emsp;先畫狀態轉移表（如下所示），一般是二維的，在畫之前需要回答三個問題： &emsp;&emsp;（1）單元格中的值是什么？當前背包中的最大總價值。 &emsp;&emsp;（2）如何劃分子問題？考慮容量為1、2、3和4的背包，并且將物品依次放入。 &emsp;&emsp;（3）網格的坐標軸是什么？橫坐標是背包重量，縱坐標是物品。 &emsp;&emsp;接下來將計算每個單元格的值。 &emsp;&emsp;（1）第一步是將吉他放入背包的四個重量中，而重量1、2和3其實就是在解決各個子問題。 &emsp;&emsp;（2）第二步是依次處理音響，判斷是否需要放入，經過比對發現只有最大容量才能放入，更新最大價值為3000。 &emsp;&emsp;（3）第三步是依次處理筆記本，在背包容量為3斤時更新最大價值為2000，而在4斤時，可同時放入吉他和筆記本，更新最大價值為3500。 :-:  &emsp;&emsp;根據狀態表得出狀態轉移方程，先計算當前商品價值和剩余空間價值，得到的結果與上一個單元格比對，將較大值填充到當前單元格中。 ~~~ dp[i][j] = max(goods[i].value + dp[i-1][j-goods[i].weight], dp[i-1][j]) ~~~ &emsp;&emsp;具體的代碼實現[如下所示](https://codepen.io/strick/pen/bGEyJQq)，本文的代碼僅做參考，沒有經過嚴格的測試用例論證。 ~~~ function knapsack(goods, w) { let max = Number.MIN_VALUE, dp = [new Array(w)], length = goods.length; for (let j = 1; j <= w; j++) { dp[0][j] = goods[0].value; } for (let i = 1; i < length; i++) { dp[i] = []; for (let j = 1; j <= w; j++) { let rest = j - goods[i].weight; //計算減去當前商品重量后的背包容量 if (rest > 0) { //套用狀態轉移方程 dp[i][j] = Math.max(goods[i].value + dp[i - 1][rest], dp[i - 1][j]); } else { dp[i][j] = dp[i - 1][j]; //沿用上一個單元格的價值 } if (max < dp[i][j]) max = dp[i][j]; //計算最大值 } } return max; } ~~~ ## 二、子串和子序列 **1）最長公共子串** &emsp;&emsp;最長公共子串是指在不改變字符相對順序的情況下提取兩段字符串中共有的子串，例如fosh和fish，最長公共子串是sh，長度為2（題目來源于《圖解算法 9.3節》）。例題：[300\. 最長上升子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/)。 &emsp;&emsp;在畫狀態表之前先回答三個問題： &emsp;&emsp;（1）單元格中的值是什么？公共子串的長度。 &emsp;&emsp;（2）如何劃分子問題？將兩段字符串分割成字符，從前往后依次比對。 &emsp;&emsp;（3）網格的坐標軸是什么？橫坐標是第一段字符串，縱坐標是第二段字符串。 :-:  &emsp;&emsp;根據狀態表得出狀態轉移方程，當兩個字符相同時，左上角的單元格加一，否則單元格為0。 ~~~ dp[i][j] = 0 | dp[i-1][j-1] + 1 ~~~ &emsp;&emsp;具體的代碼實現[如下所示](https://codepen.io/strick/pen/jOWooxe)。 ~~~ function longestCommonSubstr(str1, str2) { let len1 = str1.length, len2 = str2.length, max = Number.MIN_VALUE, dp = []; for (let i = 0; i < len1; i++) { dp[i] = []; for (let j = 0; j < len2; j++) { if (str1[i] != str2[j]) { //兩個字符不同 dp[i][j] = 0; continue; } //應對 i-1 或 j-1 小于0的情況 dp[i][j] = i < 1 || j < 1 ? 1 : dp[i - 1][j - 1] + 1; if (max < dp[i][j]) { max = dp[i][j]; } } } return max; } ~~~ **2）最長公共子序列** &emsp;&emsp;還有一個類似的題目是求最長公共子序列，其實就是提取共有的子序列，例如fosh和fish，最長公共子序列是fsh，例題：[1143\. 最長公共子序列](https://leetcode-cn.com/problems/longest-common-subsequence/)。狀態轉移表如下所示。 :-:  &emsp;&emsp;根據狀態表得出狀態轉移方程，當兩個字符相同時，仍然是左上角的單元格加一，否則比較左和上兩個單元格的值，取較大值。 ~~~ dp[i][j] = (dp[i-1][j-1] + 1) | max(dp[i-1][j], dp[i][j-1]) ~~~ &emsp;&emsp;具體的代碼實現[如下所示](https://codepen.io/strick/pen/yLeWdOB)。 ~~~ function longestCommonSubsequence(str1, str2) { let len1 = str1.length, len2 = str2.length, max = Number.MIN_VALUE, dp = []; for (let i = 0; i < len1; i++) { dp[i] = []; for (let j = 0; j < len2; j++) { if (str1[i] != str2[j]) { //兩個字符不同 dp[i][j] = Math.max( i < 1 ? 0 : dp[i - 1][j], j < 1 ? 0 : dp[i][j - 1] ); max = Math.max(max, dp[i][j]); continue; } //應對 i-1 或 j-1 小于0的情況 dp[i][j] = i < 1 || j < 1 ? 1 : dp[i - 1][j - 1] + 1; max = Math.max(max, dp[i][j]); } } return max; } ~~~ **3）最長上升子序列** &emsp;&emsp;求出一個無序的整數數組中最長上升子序列的長度。例題：[300\. 最長上升子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/)。 &emsp;&emsp;網上的解法都是用一維狀態轉移方程，此處仍然采用二維的解法（可觀察各個步驟），其中dp\[i\]\[j\]是指以第 i 個元素結尾的前 j 個元素中的最長上升子序列。 &emsp;&emsp;狀態表如下所示，每次只計算dp\[i\]\[i\]的值，其余值沿用上一行的結果。 :-:  &emsp;&emsp;根據狀態表得出狀態轉移方程，當第 i 個元素比第 j 個元素大時，在該值的基礎上加一，否則默認賦為一。 ~~~ dp[i][i] = 1 | max(dp[i][j]) + 1 ~~~ &emsp;&emsp;具體的代碼實現[如下所示](https://codepen.io/strick/pen/ExPBYRx)。 ~~~ function lengthOfLIS(nums) { let len = nums.length, max = 1, dp = []; dp[0] = [1]; //初始化dp[0][0]的值 for (let i = 1; i < len; i++) { dp[i] = []; dp[i][i] = 1; //初始化dp[i][i]的值 for (let j = 0; j < i; j++) { //讓第i個元素與前j個元素逐一比較 dp[i][j] = dp[i-1][j]; //默認沿用上一行的值 if (nums[i] > nums[j]) { //當第i個元素比第j個元素大時，取其中的較大值 dp[i][i] = Math.max(dp[i][i], dp[i][j] + 1); } } max = Math.max(max, dp[i][i]); } return max; } ~~~ ## 三、錢幣找零 &emsp;&emsp;在《[貪心算法](https://www.cnblogs.com/strick/p/13391105.html)》一節中曾提到過錢幣找零的問題，此處會加大難度。 &emsp;&emsp;假設有幾種不同面值的紙幣 v1，v2，……，vn（單位是元），如果要支付 w 元，那么最少需要多少張紙幣，例如有 3 種不同的紙幣，1元、2元、5元，要支付 9元，最少需要 3張紙幣。例題：[322\. 零錢兌換](https://leetcode-cn.com/problems/coin-change/)。 &emsp;&emsp;在畫狀態表之前先回答三個問題： &emsp;&emsp;（1）單元格中的值是什么？最少紙幣數。 &emsp;&emsp;（2）如何劃分子問題？考慮要支付1、2...9等金額時，各自需要的最少紙幣數。 &emsp;&emsp;（3）網格的坐標軸是什么？橫坐標是支付金額，縱坐標是可用的紙幣。 :-:  &emsp;&emsp;根據狀態表得出狀態轉移方程，計算金額減去當前面值的剩余金額所用的最少紙幣數，將其加一和上一行的最少紙幣數做比較，取小值。 ~~~ dp[i][j] = min(dp[i-1][j], dp[i][j - coins[i]] + 1) ~~~ &emsp;&emsp;具體的代碼實現[如下所示](https://codepen.io/strick/pen/NWxZgZW)，雖然代碼比較長，但好多都是在判斷邊界條件，以及做各類情況的處理，核心其實還是圍繞著狀態轉移方程。 ~~~ function coinChange(coins, amount) { let len = coins.length, min = Number.MAX_VALUE, dp = [new Array(amount)]; for (let j = 1; j <= amount; j++) { //初始化第一行 //紙幣面值比金額大，或金額無法整除紙幣 if(coins[0] > j || (j % coins[0]) > 0) { //對于無法支付金額的情況，賦值為0 dp[0][j] = 0; continue; } dp[0][j] = j / coins[0]; //得到紙幣數量 } for (let i = 1; i < len; i++) { dp[i] = []; for (let j = 1; j <= amount; j++) { let rest = j - coins[i]; if(rest == 0) { //可用當前紙幣支付金額 dp[i][j] = 1; continue; } if(rest < 0) { //當前紙幣比支付金額大 dp[i][j] = dp[i-1][j]; continue; } if(dp[i-1][j] > 0 && dp[i][rest] > 0) { //都可以支付金額 dp[i][j] = Math.min(dp[i-1][j], dp[i][rest] + 1); }else if(dp[i-1][j] > 0) { //只有上一行可以支付金額 dp[i][j] = dp[i-1][j]; }else if(dp[i][rest] > 0) { //只能借助剩余金額的紙幣數支付 dp[i][j] = dp[i][rest] + 1; }else { //無法支付 dp[i][j] = 0; } } } //取金額的最小值 for(let i = 0; i < len; i++) { if(dp[i][amount] == 0) { //過濾掉無法支付的數據 continue; } if(dp[i][amount] > 0) { min = Math.min(min, dp[i][amount]); } } return min == Number.MAX_VALUE ? -1 : min; } ~~~ ***** > 原文出處： [博客園-數據結構和算法躬行記](https://www.cnblogs.com/strick/category/1809992.html) 已建立一個微信前端交流群，如要進群，請先加微信號freedom20180706或掃描下面的二維碼，請求中需注明“看云加群”，在通過請求后就會把你拉進來。還搜集整理了一套[面試資料](https://github.com/pwstrick/daily)，歡迎閱讀。  推薦一款前端監控腳本：[shin-monitor](https://github.com/pwstrick/shin-monitor)，不僅能監控前端的錯誤、通信、打印等行為，還能計算各類性能參數，包括 FMP、LCP、FP 等。