詳解三道一維的動態規劃算法題
摘要：dp[0] = nums[0]。dp[0] = nums[0]。
來源： 知乎
作者： 單金折
前陣子寫了兩篇動態規劃的文章
後面說要給大家講解一些案例，不過一直沒講，由於前陣子手受傷了導致手不能運動，一直沒給大家寫文章，所以呢，我就找一些感覺還不錯的文章供大家消費。
例1: 打家劫舍
動態規劃思考步驟：
1、原問題：
在一條直線上，有n個房屋，每個房屋中有數量不等的財寶，有一個盜 賊希望從房屋中盜取財寶，由於房屋中有報警器，如果同時從相鄰的兩個房屋中盜取財寶就會觸發報警器。問在不觸發報警器的前提下，最多可獲取多少財寶？例如 [5，2，6，3，1，7]，則選擇5，6，7
來源於LeetCode 198. House Robber
2 、子問題：
（1）、只考慮前兩個房間時，誰大選誰
（2）、考慮第三個房間
-
如果偷第三個房間，則意味着第二個房間不投，也就是第三個房間值 + 第一個房間的寶藏數量
-
如果不偷第三個房間，則寶藏數量等於前兩個房間寶藏數量
3、確認狀態：
int [] nums; // 各個房間的寶藏數
int [] flags = new int [n]; // 記錄各個房間有沒有被偷，若flag = 0 則沒偷， flag = 1 則偷了。
int [] dp = new int [n]; // dp[i]表示前i個房間偷到的最大寶藏數
4、初始狀態：
第一個房間：
-
Condistion 1 ：dp[0] = nums[0] ; flags[0] = 1;
-
Condistion 2 ：dp[0] = 0; flags[0] = 0;
第二個房間：
-
Condistion 1 ：when flags[1] = 1; dp[1] = nums[1];
-
Condistion 2 ：whenflags[1] = 0; dp[1] = dp[0];
-
選 Condistion 1 還是 Condistion 2呢？比較 兩種情況下dp[1]的大小
推廣到前i個房間: (i>=2)
-
when flags[i] = 1, dp[i] = nums[i] + dp[i-2]
-
when flags[i] = 0; dp[i] = dp[i-1]
5、狀態轉移方程：
dp[0] = nums[0];
dp[1] = max(nums[0],nums[1]);
for(int i = 2;i<n;i++)
dp[i] = max(nums[i] + dp[i-2],dp[i-1])
6、代碼實現
class Solution {
public int rob(int[] nums) {
if(nums.length == 0)
return 0;
int [] dp = new int[nums.length];
dp[0] = nums[0];
// 每次做數組判定時都需要做數組邊界判定，防止越界
if(nums.length < 2)
return nums[0];
dp[1] = (nums[0]>nums[1]) ? nums[0] : nums[1];
for(int i = 2;i<nums.length;i++)
dp[i] = ((nums[i] + dp[i-2]) > dp[i-1]) ? (nums[i]+dp[i-2]) : dp[i-1];
return dp[nums.length-1];
}
}
例2:最大子段和
動態規劃思考步驟：
1、原問題
給定一個數組，求這個數組的連續子數組中，最大的那一段的和。
如數組[-2,1,-3,4,-1,2,1,-5,4] 的子段爲：[-2,1]、[1,-3,4,-1]、[4,-1,2,1]、…、[-2,1,-3,4,-1,2,1,-5,4]，和最大的是[4,1,2,1]，爲6。
示例： Input: int [] nums = [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
來源於LeetCode 53. Maximum Subarray
2、子問題
-
只考慮第一個元素，則最大子段和爲其本身 DP[0] = nums[0]
-
考慮前兩個元素，最大子段和爲 nums[0],num[1]以及 nums[0] + num[1] 中最大值 設爲DP[1]
-
考慮前三個元素，如何求其最大子段和？還是分爲兩種情況討論，第三個元素在最後的字串內嗎？
-
若第三個元素也包含在最後的字串內，則DP[2] = Max(DP[1]+nums[2] , nums[2])
3、確認狀態
DP[i] 爲 以nums[i]結尾的子段的最大最短和
例如 DP[1]則爲以nums[1]結尾的最大字段和
4、初始狀態
dp[0] = nums[0]
dp[1] = max(dp[0]+nums[1] , nums[1])
5、狀態轉移方程：
dp[i] = max(dp[i-1]+nums[i],nums[i])
6、解題代碼：
public class lc53_MaximumSubarray {
public int maxSubArray(int[] nums) {
int len = nums.length;
if(len == 0)
return 0;
int [] dp = new int[len];
dp[0] = nums[0];
int max = dp[0];
for (int i = 1; i<len;i++){
dp[i] = (dp[i-1]+nums[i] > nums[i]) ? dp[i-1]+nums[i] : nums[i];
if (dp[i]>max)
max = dp[i];
}
return max;
}
}
例3：找零錢
已知不同面值的鈔票，求如 何用最少數量的鈔票組成某個金額，求可 以使用的最少鈔票數量。如果任意數量的已知面值鈔票都無法組成該金額， 則返回-1。
示例： Input: coins = [1, 2, 5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 Input: coins = [2], amount = 3 Output: -1
來源於LeetCode 322. Coin Change
動態規劃解題步驟：
將原問題拆分成子問題
-
已知什麼？顯而易見，鈔票的金額都只需要其本身1張即可
-
如何在已知鈔票的情況下構造出 金額X需要的最少鈔票組合
確認狀態
DP[0] - DP[amount] 表示構造金額amount需要的最小鈔票數
確認邊界狀態（初始條件）
-
DP[coin] = 1 其他的都未知初始值設爲 -1
-
例如coins = [1, 2, 5], amount = 11 已知 dp[1]、dp[2]、dp[5] =1
-
現在已知 DP[coin] 需要求出每一個DP[amount]
狀態轉移方程
dp[i] = min(dp[i-1], dp[i-2], dp[i-5]) + 1
解題代碼：（java）
public int coinChange(int[] coins, int amount) {
int len = coins.length;
if (len == 0 || amount<0)
return -1;
if (amount==0)
return 0;
int [] dp = new int[amount+1];
for (int i = 0; i <= amount; i++){
dp[i] = -1;
}
for (int i = 0; i< len;i++){
if(coins[i] == amount)
return 1;
if(coins[i] < amount)
dp[coins[i]] = 1;
}
// State Transfer Function
for(int i = 1; i <= amount;i++){
for (int j = 0; j < len; j++){
if (i - coins[j] >= 0 && dp[i - coins[j]] != -1){
if (dp[i] == -1 || dp[i] > dp[i - coins[j]] + 1){
dp[i] = dp[i - coins[j]] + 1;
}
}
}
}
return dp[amount];
}
總結
今天實例了三道一維的題，屬於 leetcode 中 medium 級別的題吧，大家也可以根據題號去搜索練練手。
