數據結構和演算法躬行記（8）——動態規劃
- 2020 年 10 月 26 日
- 筆記
- 數據結構和演算法躬行記
動態規劃（Dynamic Programming，DP）是指在給定的約束條件下求最優值的演算法，在解決問題的過程，需要經歷多個決策階段，每個決策階段都對應著一組狀態。
適用於動態規劃解決的問題包含三個特徵：
（1）最優子結構：通過子問題的最優解，可推導出問題的最優解，即後面階段的狀態可以通過前面階段的狀態推導出來。
（2）無後效性：某階段狀態一旦確定，就不受之後階段的決策影響。即子問題的解一旦確定，就不再改變。
（3）子問題重疊：不同的決策序列，到達某個相同的階段時，可能會產生重複的狀態。即有些子問題會被重複計算多次。
動態規劃對每個子問題只計算一次，然後將其計算結果保存到一張表中記憶化存儲，以便下次需要同一個子問題解時直接查表，從而獲得較高的效率，降低了時間複雜度。
一、0-1背包
在之前《回溯》一文中也提到了0-1背包問題，而此處會在背包重量限制的前提下，計算裝入物品的最大總價值。
假設背包容量為4斤，吉他（1斤，價值1500）、音響（4斤，價值3000）和筆記型電腦（3斤，價值2000），求背包的最大價值（題目來源於《圖解演算法 9.1節》）。
先畫狀態轉移表（如下所示），一般是二維的，在畫之前需要回答三個問題：
（1）單元格中的值是什麼？當前背包中的最大總價值。
（2）如何劃分子問題？考慮容量為1、2、3和4的背包，並且將物品依次放入。
（3）網格的坐標軸是什麼？橫坐標是背包重量，縱坐標是物品。
接下來將計算每個單元格的值。
（1）第一步是將吉他放入背包的四個重量中，而重量1、2和3其實就是在解決各個子問題。
（2）第二步是依次處理音響，判斷是否需要放入，經過比對發現只有最大容量才能放入，更新最大價值為3000。
（3）第三步是依次處理筆記型電腦，在背包容量為3斤時更新最大價值為2000，而在4斤時，可同時放入吉他和筆記型電腦，更新最大價值為3500。
根據狀態表得出狀態轉移方程，先計算當前商品價值和剩餘空間價值，得到的結果與上一個單元格比對，將較大值填充到當前單元格中。
dp[i][j] = max(goods[i].value + dp[i-1][j-goods[i].weight], dp[i-1][j])
具體的程式碼實現如下所示，本文的程式碼僅做參考，沒有經過嚴格的測試用例論證。
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）最長公共子串
最長公共子串是指在不改變字元相對順序的情況下提取兩段字元串中共有的子串，例如fosh和fish，最長公共子串是sh，長度為2（題目來源於《圖解演算法 9.3節》）。例題：300. 最長上升子序列。
在畫狀態表之前先回答三個問題：
（1）單元格中的值是什麼？公共子串的長度。
（2）如何劃分子問題？將兩段字元串分割成字元，從前往後依次比對。
（3）網格的坐標軸是什麼？橫坐標是第一段字元串，縱坐標是第二段字元串。
根據狀態表得出狀態轉移方程，當兩個字元相同時，左上角的單元格加一，否則單元格為0。
dp[i][j] = 0 | dp[i-1][j-1] + 1
具體的程式碼實現如下所示。
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）最長公共子序列
還有一個類似的題目是求最長公共子序列，其實就是提取共有的子序列，例如fosh和fish，最長公共子序列是fsh，例題：1143. 最長公共子序列。狀態轉移表如下所示。
根據狀態表得出狀態轉移方程，當兩個字元相同時，仍然是左上角的單元格加一，否則比較左和上兩個單元格的值，取較大值。
dp[i][j] = (dp[i-1][j-1] + 1) | max(dp[i-1][j], dp[i][j-1])
具體的程式碼實現如下所示。
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）最長上升子序列
求出一個無序的整數數組中最長上升子序列的長度。例題：300. 最長上升子序列。
網上的解法都是用一維狀態轉移方程，此處仍然採用二維的解法（可觀察各個步驟），其中dp[i][j]是指以第 i 個元素結尾的前 j 個元素中的最長上升子序列。
狀態表如下所示，每次只計算dp[i][i]的值，其餘值沿用上一行的結果。
根據狀態表得出狀態轉移方程，當第 i 個元素比第 j 個元素大時，在該值的基礎上加一，否則默認賦為一。
dp[i][i] = 1 | max(dp[i][j]) + 1
具體的程式碼實現如下所示。
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; }
三、錢幣找零
在《貪心演算法》一節中曾提到過錢幣找零的問題，此處會加大難度。
假設有幾種不同面值的紙幣 v1，v2，……，vn（單位是元），如果要支付 w 元，那麼最少需要多少張紙幣，例如有 3 種不同的紙幣，1元、2元、5元，要支付 9元，最少需要 3張紙幣。例題：322. 零錢兌換。
在畫狀態表之前先回答三個問題：
（1）單元格中的值是什麼？最少紙幣數。
（2）如何劃分子問題？考慮要支付1、2…9等金額時，各自需要的最少紙幣數。
（3）網格的坐標軸是什麼？橫坐標是支付金額，縱坐標是可用的紙幣。
根據狀態表得出狀態轉移方程，計算金額減去當前面值的剩餘金額所用的最少紙幣數，將其加一和上一行的最少紙幣數做比較，取小值。
dp[i][j] = min(dp[i-1][j], dp[i][j - coins[i]] + 1)
具體的程式碼實現如下所示，雖然程式碼比較長，但好多都是在判斷邊界條件，以及做各類情況的處理，核心其實還是圍繞著狀態轉移方程。
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; }
