歡迎關注個人公眾號：愛喝可可牛奶
LeetCode演算法訓練-動態規劃
理論知識
動態規劃當前狀態是由前一個狀態推匯出來的，而貪心沒有狀態的轉移
動態規劃需要借助dp陣列，可能是一維也可能是二維的
- 首先要明確dp陣列是用來干什么的，下標對應什么
- 狀態如何轉移 ？ 也就是理清遞推公式
- dp陣列如何初始化
- 如何遍歷
- 舉個栗子模擬推導一遍
LeetCode 509. 斐波那契數
分析
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
代碼
class Solution {
public int fib(int n) {
if (n <= 1) return n;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int index = 2; index <= n; index++){
dp[index] = dp[index - 1] + dp[index - 2];
}
return dp[n];
}
}
LeetCode 70. 爬樓梯
分析
錯誤 沒有理清遞推函式
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2]+2;
}
return dp[n];
}
}
dp[i]表示到當前樓梯有多少種跳法，從這里可以往后跳一步或者兩步，這樣就建立了前后階梯的關系，但是不能跳2個一步
當前階梯跳數能由前一個階梯跳一步或前兩個階梯跳兩步得到
代碼
class Solution {
public int climbStairs(int n) {
if(n == 1){
return 1;
}
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
LeetCode 746. 使用最小花費爬樓梯
整數陣列 cost ，cost[i] 是從樓梯第 i 個臺階向上爬需要支付的費用，一旦支付此費用，即可選擇向上爬一個或者兩個臺階，
你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯，
請你計算并回傳達到樓梯頂部的最低花費，
分析
根據測驗用例能夠得出臺階頂部在哪里，cost[i] ：從下標i-1爬一步，從i-2爬兩步到臺階頂部
dp[i]表示爬到第i個臺階的最小花費，
狀態轉移：dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
代碼
class Solution {
public int minCostClimbingStairs(int[] cost) {
int len = cost.length;
int[] dp = new int[len+1];
// 初始化
dp[0] = 0;
dp[1] = 0;
for(int i = 2; i <= len; i++){
dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
}
return dp[len];
}
}
總結
- 搞清楚dp陣列含義以及對應下標反映了什么狀態
- 弄清楚轉移公式
- 初始化
- 確定遍歷順序（這個和轉移公式緊密相關）
- 模擬一下
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/545520.html
標籤：Java
下一篇：Java 根據模板匯出PDF