青島網(wǎng)站設(shè)計微動力百家號推廣團隊
算法通關(guān)村第十九關(guān)——動態(tài)規(guī)劃高頻問題（白銀）
- 前言
- 1 最少硬幣數(shù)
- 2 最長連續(xù)遞增子序列
- 3 最長遞增子序列
- 4 完全平方數(shù)
- 5 跳躍游戲
- 6 解碼方法
- 7 不同路徑 II
前言
摘自：代碼隨想錄
動態(tài)規(guī)劃五部曲：
- 確定dp數(shù)組（dp table）及其下標的含義
- 確定遞推公式
- 初始化dp數(shù)組
- 確定遍歷順序
- 舉例推導dp數(shù)組
1 最少硬幣數(shù)
leetcode 322. 零錢兌換
動規(guī)五部曲分析如下：
- 確定dp數(shù)組以及下標的含義
dp[j]：湊足總額為 j 所需錢幣的最少個數(shù)為dp[j]
- 確定遞推公式
湊足總額為j - coins[i]的最少個數(shù)為dp[j - coins[i]]，
那么只需要加上一個錢幣coins[i]即dp[j - coins[i]] + 1就是dp[j]（考慮coins[i]）
所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
遞推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
- dp數(shù)組如何初始化
首先湊足總金額為0所需錢幣的個數(shù)一定是0，那么dp[0] = 0;
其他下標對應的數(shù)值呢？
考慮到遞推公式的特性，dp[j]必須初始化為一個最大的數(shù)，否則就會在min(dp[j - coins[i]] + 1, dp[j])比較的過程中被初始值覆蓋。
所以下標非0的元素都是應該是最大值。
int[] dp = new int[amount + 1];
// 往數(shù)組dp里面填充某個數(shù)，這里選擇amount+1，就是最大的值
Arrays.fill(dp, amount+1);
dp[0] = 0;
- 確定遍歷順序
有兩種方式：
第一種：外循環(huán)遍歷金額，內(nèi)循環(huán)遍歷硬幣面額。
第二種：外循環(huán)遍歷硬幣面面額，內(nèi)循環(huán)遍歷金額。
這兩種遍歷順序?qū)囊饬x如下：
-
外循環(huán)遍歷金額，內(nèi)循環(huán)遍歷硬幣面額：
這種遍歷順序的意義是在計算找零過程中，我們首先考慮金額的變化，然后再考慮不同的硬幣面額。
也就是說，我們固定一個金額，嘗試使用不同的硬幣面額來找零。這樣做的好處是可以利用之前已經(jīng)計算出來的金額的最少硬幣數(shù)，快速得到當前金額的最優(yōu)解。由于金額是從小到大遞增的，所以我們在計算每個金額的最優(yōu)解時，可以利用前面較小金額的最優(yōu)解已經(jīng)被計算出來的特點。
// 遍歷金額
for (int i = 1; i <= amount; i++) {// 遍歷硬幣面額for (int j = 0; j < coins.length; j++) {if (coins[j] <= i) {dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);}}
}
-
外循環(huán)遍歷硬幣面額，內(nèi)循環(huán)遍歷金額：
這種遍歷順序的意義是在計算找零過程中，我們首先考慮不同的硬幣面額，然后再考慮不同的金額。
也就是說，我們固定一個硬幣面額，嘗試在不同的金額下進行找零。這樣做的好處是可以保證我們將所有可能的硬幣面額都考慮到，并且在計算每個金額的最優(yōu)解時，可以利用之前已經(jīng)計算出來的較小金額的最優(yōu)解。由于硬幣面額是從小到大遞增的，所以我們在計算每個金額的最優(yōu)解時，可以利用之前較小硬幣面額的最優(yōu)解已經(jīng)被計算出來的特點。
// 遍歷硬幣面額
for (int coin : coins){// 遍歷金額for (int i = 1; i <= amount; i++) {if(coin <= i){dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}
}
全部代碼如下：
第一種：
class Solution {public int coinChange(int[] coins, int amount) {// 初始化dp數(shù)組int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1);dp[0] = 0;// 遍歷金額for (int i=1; i <= amount; i++) {// 遍歷硬幣面額for (int j=0; j < coins.length; j++){if(coins[j] <= i){dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];}
}
第二種：
class Solution {public int coinChange(int[] coins, int amount) {// 初始化dp數(shù)組int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1);dp[0] = 0;// 遍歷硬幣面額for (int coin : coins){// 遍歷金額for (int i = 1; i <= amount; i++) {if(coin <= i){dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];}
}
2 最長連續(xù)遞增子序列
leetcode 674. 最長連續(xù)遞增序列
動規(guī)五部曲分析如下：
- 確定dp數(shù)組以及下標的含義
dp數(shù)組：表示以當前元素為結(jié)尾的最長連續(xù)遞增序列的長度。
dp[i]表示以nums[i]為結(jié)尾的最長連續(xù)遞增序列的長度。
- 確定遞推公式
如果nums[i] > nums[i-1]，則dp[i] = dp[i-1] + 1；否則dp[i] = 1。
- dp數(shù)組如何初始化
我們將dp數(shù)組的所有元素初始化為1，因為每個元素都可以作為一個單獨的遞增序列。
- 確定遍歷順序
從第二個元素開始遍歷：
for(int i=0; i < nums.length; i++){if(i > 0 && nums[i] > nums[i-1]){dp[i] = dp[i-1] + 1;}else{dp[i] = 1;}
}
- 舉例說明
舉例說明：給定數(shù)組nums = [1, 3, 5, 4, 7]。
遍歷過程如下：
- 對于nums[1] = 3，nums[0] = 1 < nums[1]，所以dp[1] = dp[0] + 1 = 2。
- 對于nums[2] = 5，nums[1] = 3 < nums[2]，所以dp[2] = dp[1] + 1 = 3。
- 對于nums[3] = 4，nums[2] = 5 > nums[3]，所以dp[3] = 1。
- 對于nums[4] = 7，nums[3] = 4 < nums[4]，所以dp[4] = dp[3] + 1 = 2。
最終的最長連續(xù)遞增序列的長度為dp數(shù)組的最大值，即為3。
最后代碼如下：
class Solution {public int findLengthOfLCIS(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int[] dp = new int[nums.length];dp[0] = 1;for(int i=1; i < nums.length; i++){if(nums[i] > nums[i-1]){dp[i] = dp[i-1] + 1;}else{dp[i] = 1;}}return Arrays.stream(dp).max().getAsInt();}
}
不是使用stream的方式：
class Solution {public int findLengthOfLCIS(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int[] dp = new int[nums.length];dp[0] = 1;int maxLength = 1;for(int i=1; i < nums.length; i++){if(nums[i] > nums[i-1]){dp[i] = dp[i-1] + 1;}else{dp[i] = 1;}maxLength = Math.max(maxLength, dp[i]);}return maxLength;}
}
還可以得到dp[i]，再遍歷一遍得到最大值，這就不寫了
3 最長遞增子序列
leetcode 300. 最長遞增子序列
-
確定dp數(shù)組（dp table）及其下標的含義：
- dp數(shù)組：dp[i] 表示以第i個數(shù)字結(jié)尾的最長遞增子序列的長度。
- 下標的含義：dp[i] 表示以第i個數(shù)字結(jié)尾的最長遞增子序列的長度。
-
確定遞推公式：
- 如果nums[i] > nums[j]，則：dp[i] = max(dp[i], dp[j] + 1)。
為啥呢？？
這里的i和j表示數(shù)組
nums的索引。具體來說，i表示當前遍歷到的元素的索引，而j表示在i之前的元素的索引。當我們遍歷到第i個元素時，我們需要尋找在i之前的元素中比nums[i]小的元素。這樣，我們就可以利用這個小于nums[i]的元素來構(gòu)成一個更長的遞增子序列。
所以，當nums[i] > nums[j]時，表示nums[i]比nums[j]大，我們可以將以j結(jié)尾的最長遞增子序列的長度加1，然后與以i結(jié)尾的最長遞增子序列的長度進行比較，取較大的值作為以i結(jié)尾的最長遞增子序列的長度。也就是遞推公式中的
dp[i] = max(dp[i], dp[j] + 1)。 -
初始化dp數(shù)組：
- 初始時，dp數(shù)組中的每個元素都設(shè)為1，因為最短的遞增子序列長度為1。
-
確定遍歷順序：
- 外層循環(huán)遍歷數(shù)組nums，從左到右依次計算dp[i]的值。
- 內(nèi)層循環(huán)遍歷數(shù)組nums，從數(shù)組開始到i的位置，尋找前面的數(shù)字nums[j]是否小于nums[i]，如果是，則根據(jù)遞推公式更新dp[i]的值。
-
舉例推導dp數(shù)組：
如果nums[i] > nums[j]，則dp[i] = max(dp[i], dp[j] + 1)。
逐個元素計算dp[i]的值：
- 當i = 1時，nums[i] = 9，此時沒有比9小的元素，所以以9結(jié)尾的最長遞增子序列長度仍為1。
nums: 10 9 2 5 3 7 101 18
dp: 1 1 1 1 1 1 1 1- 當i = 2時，nums[i] = 2，此時在2之前有9和10兩個元素，都比2大，所以以2結(jié)尾的最長遞增子序列長度仍為1。
nums: 10 9 2 5 3 7 101 18
dp: 1 1 1 1 1 1 1 1- 當i = 3時，nums[i] = 5，此時在5之前有2和9兩個元素，其中2比5小，所以以5結(jié)尾的最長遞增子序列長度為dp[2] + 1 = 2。
nums: 10 9 2 5 3 7 101 18
dp: 1 1 1 2 1 1 1 1- 當i = 4時，nums[i] = 3，此時在3之前有2和5兩個元素，其中2比3小，所以以3結(jié)尾的最長遞增子序列長度為dp[2] + 1 = 2。
nums: 10 9 2 5 3 7 101 18
dp: 1 1 1 2 2 1 1 1
后面略~~~~~~
完整代碼如下：
class Solution {public int lengthOfLIS(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int n = nums.length;int[] dp = new int[n];dp[0] = 1; int result = 1; for (int i = 1; i < n; i++) {dp[i] = 1; for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); }}result = Math.max(result, dp[i]); }return result;}
}
4 完全平方數(shù)
leetcode 279. 完全平方數(shù)
動態(tài)規(guī)劃五部曲：
- 確定dp數(shù)組（dp table）及其下標的含義
**dp[i]：**表示數(shù)字i的最少完全平方數(shù)的個數(shù)。
- 確定遞推公式
對于數(shù)字 i 來說，我們需要遍歷所有小于等于 i 的完全平方數(shù) j（ j 從 1 到 sqrt(i) ），然后將當前數(shù)字 i 減去 j 得到差值，即 i - j 。我們需要找到 dp[ i - j * j ] 的最小值，然后再加上1（表示當前完全平方數(shù) j ），即可得到dp[i]的值。
遞推公式為：dp[i] = Math.min(dp[i], dp[i - j * j] + 1)，其中 j * j <= i。
- 初始化dp數(shù)組
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
- 確定遍歷順序
// 遍歷dp數(shù)組
for (int i = 1; i <= n; i++) {// 遍歷小于等于i的完全平方數(shù)j*jfor (int j = 1; j * j <= i; j++) {// 更新dp[i]dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}
}
- 舉例推導dp數(shù)組
略。。。
完整代碼：
class Solution {public int numSquares(int n) {// 定義dp數(shù)組int[] dp = new int[n + 1];// 初始化dp數(shù)組Arrays.fill(dp, n+1);dp[0] = 0;// 遍歷dp數(shù)組for (int i = 1; i <= n; i++) {// 遍歷小于等于i的完全平方數(shù)j*jfor (int j = 1; j * j <= i; j++) {// 更新dp[i]dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}return dp[n]; }
}
當然，這個代碼可以再優(yōu)化一下：（使用Math的api）
減少內(nèi)層循環(huán)的次數(shù)：對于小于等于 i 的完全平方數(shù) j ，我們可以通過計算 i - j * j 的平方根得到 j 的最大值，并從最大值開始遍歷，這樣可以減少內(nèi)層循環(huán)的次數(shù)。
class Solution {public static int numSquares(int n) {// 定義dp數(shù)組int[] dp = new int[n + 1];// 初始化dp數(shù)組Arrays.fill(dp, n + 1);dp[0] = 0;// 遍歷dp數(shù)組for (int i = 1; i <= n; i++) {// 獲取當前數(shù)字i的最大完全平方數(shù)j*jint maxSquare = (int) Math.sqrt(i);// 遍歷完全平方數(shù)j*jfor (int j = maxSquare; j >= 1; j--) {// 更新dp[i]dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}return dp[n];}
}
5 跳躍游戲
leetcode 55. 跳躍游戲
動態(tài)規(guī)劃五部曲：
- 確定dp數(shù)組（dp table）及其下標的含義
dp[i]表示從起點位置到達位置i時能否跳躍到最后一個位置。
- 確定遞推公式
dp[i] = (dp[j] && nums[j] >= i - j)，其中0 <= j < i
- 初始化dp數(shù)組
初始化dp數(shù)組所有位置為false。
- 確定遍歷順序
外層循環(huán)遍歷i從1到n-1，內(nèi)層循環(huán)遍歷j從0到i-1。
- 舉例推導dp數(shù)組
以數(shù)組nums = [2, 3, 1, 1, 4]為例進行推導：
初始狀態(tài)：
dp = [false, false, false, false, false]
推導dp[1]：
dp[1] = (dp[0] && nums[0] >= 1 - 0) = (false && 2 >= 1) = false
推導dp[2]：
dp[2] = (dp[0] && nums[0] >= 2 - 0) || (dp[1] && nums[1] >= 2 - 1) = (false && 2 >= 2) || (false && 3 >= 2) = false
推導dp[3]：
dp[3] = (dp[0] && nums[0] >= 3 - 0) || (dp[1] && nums[1] >= 3 - 1) || (dp[2] && nums[2] >= 3 - 2) = (false && 2 >= 3) || (false && 3 >= 3) || (false && 1 >= 3) = false
完整代碼如下：
class Solution {public boolean canJump(int[] nums) {// 獲取數(shù)組長度int n = nums.length;// 定義dp數(shù)組boolean[] dp = new boolean[n];// 初始化dp數(shù)組dp[0] = true;// 遍歷dp數(shù)組for (int i = 1; i < n; i++) {// 內(nèi)層循環(huán)遍歷jfor (int j = 0; j < i; j++) {// 更新dp[i]dp[i] = dp[j] && nums[j] >= i - j;// 如果dp[i]為true，則跳出內(nèi)層循環(huán)if (dp[i]) {break;}}}return dp[n - 1];}
}
6 解碼方法
leetcode 91. 解碼方法
動態(tài)規(guī)劃五部曲：
- 確定dp數(shù)組（dp table）及其下標的含義
dp[i]表示從字符串的起始位置到第i個字符時的解碼方法總數(shù)。
- 確定遞推公式
對于dp數(shù)組中的每個位置i，我們需要考慮兩個情況：
- 如果第i個字符能夠單獨解碼（即不為0），則dp[i] = dp[i-1]，因為第i個字符自身可以作為一個解碼方法；
- 如果第i個字符與前一個字符組成的兩位數(shù)能夠解碼（即與前一個字符組成的數(shù)字在1到26之間），則dp[i] += dp[i-2]，因為組成的兩位數(shù)可以作為一個解碼方法。
則，遞推公式為：dp[i] = dp[i-1] + dp[i-2]，其中0 <= i < n。
- 初始化dp數(shù)組
初始化dp數(shù)組的長度為n+1，初始值為0。
- 確定遍歷順序
for (int i = 1; i <= n; i++) {// 如果第i個字符能夠單獨解碼（即不為0）if (s.charAt(i - 1) != '0') {dp[i] += dp[i - 1];}// 如果第i個字符與前一個字符組成的兩位數(shù)能夠解碼（即與前一個字符組成的數(shù)字在1到26之間）if (i >= 2 && isValidEncoding(s.substring(i - 2, i))) {dp[i] += dp[i - 2];}
}
// 判斷字符串編碼是否在1到26之間
private static boolean isValidEncoding(String s) {if (s.charAt(0) == '0') {return false;}int num = Integer.parseInt(s);return num >= 1 && num <= 26;
}
- 舉例推導dp數(shù)組
以字符串s = "226"為例進行推導：
初始狀態(tài)：
dp = [1, 0, 0, 0]
推導dp[1]：
如果第1個字符為2，能夠單獨解碼為"2"，所以dp[1] = dp[0] = 1
推導dp[2]：
如果第2個字符為2，能夠單獨解碼為"2"，所以dp[2] = dp[1] = 1
如果第1個字符與第2個字符組成的兩位數(shù)為26，能夠解碼為"26"，所以dp[2] += dp[0]，即dp[2] = dp[1] + dp[0] = 1 + 1 = 2
推導dp[3]：
如果第3個字符為6，能夠單獨解碼為"6"，所以dp[3] = dp[2] = 2
如果第2個字符與第3個字符組成的兩位數(shù)為26，能夠解碼為"26"，所以dp[3] += dp[1]，即dp[3] = dp[2] + dp[1] = 2 + 1 = 3
最終結(jié)果：
dp = [1, 1, 2, 3]
完整代碼：
class Solution {public static int numDecodings(String s) {// 獲取字符串的長度int n = s.length();// 定義dp數(shù)組int[] dp = new int[n + 1];// 初始化dp數(shù)組dp[0] = 1;// 遍歷dp數(shù)組for (int i = 1; i <= n; i++) {// 如果第i個字符能夠單獨解碼（即不為0）if (s.charAt(i - 1) != '0') {dp[i] += dp[i - 1];}// 如果第i個字符與前一個字符組成的兩位數(shù)能夠解碼（即與前一個字符組成的數(shù)字在1到26之間）if (i >= 2 && isValidEncoding(s.substring(i - 2, i))) {dp[i] += dp[i - 2];}}return dp[n];}// 判斷字符串編碼是否在1到26之間private static boolean isValidEncoding(String s) {if (s.charAt(0) == '0') {return false;}int num = Integer.parseInt(s);return num >= 1 && num <= 26;}
}
不過可以簡化一下，就是比較難理解一點，意義一樣滴：
class Solution {public int numDecodings(String s) {int n = s.length();int[] f = new int[n + 1];f[0] = 1;for (int i = 1; i <= n; ++i) {if (s.charAt(i - 1) != '0') {f[i] += f[i - 1];}if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {f[i] += f[i - 2];}}return f[n];}
}
7 不同路徑 II
leetcode 63. 不同路徑 II
這題就是62的改版，所以復雜了很多，還是建議看代碼隨想錄：動態(tài)規(guī)劃——不同路徑
動規(guī)五部曲：
- 確定dp數(shù)組（dp table）以及下標的含義
**dp[i] [j] ：**表示從（0 ，0）出發(fā)，到(i, j) 有dp[i] [j]條不同的路徑。
- 確定遞推公式
遞推公式和62.不同路徑一樣，dp[i] [j] = dp[i - 1] [j] + dp[i] [j - 1]。
但這里需要注意一點，因為有了障礙，(i, j)如果就是障礙的話應該就保持初始狀態(tài)（初始狀態(tài)為0）。
所以代碼為：
if (obstacleGrid[i][j] == 0) { // 當(i, j)沒有障礙的時候，再推導dp[i][j]dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
- dp數(shù)組如何初始化
因為從(0, 0)的位置到(i, 0)的路徑只有一條，所以dp[i] [0]一定為1，dp[0] [j]也同理。
但如果(i, 0) 這條邊有了障礙之后，障礙之后（包括障礙）都是走不到的位置了，所以障礙之后的dp[i] [0]應該還是初始值0。
如圖：
下標(0, j)的初始化情況同理。
所以本題初始化代碼為：
int[][] dp = new int[m][n];
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {dp[i][0] = 1;
}
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {dp[0][j] = 1;
}
注意代碼里for循環(huán)的終止條件，一旦遇到obstacleGrid[i] [0] == 1的情況就停止dp[i] [0]的賦值1的操作，dp[0] [j]同理
- 確定遍歷順序
從遞歸公式dp[i] [j] = dp [i - 1] [j] + dp[i] [j - 1] 中可以看出，一定是從左到右一層一層遍歷，這樣保證推導dp[i] [j]的時候，dp[i - 1] [j] 和 dp[i] [j - 1]一定是有數(shù)值。
代碼如下：
for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;}
}
- 舉例推導dp數(shù)組
完整代碼如下：
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];//如果在起點或終點出現(xiàn)了障礙，直接返回0if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {return 0;}for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {dp[i][0] = 1;}for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {dp[0][j] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;}}return dp[m - 1][n - 1];}
}
至于118，119我個人覺得并不合適使用動態(tài)規(guī)劃的方式，所以就不寫了，over~~