歡迎關(guān)注個人公眾號：愛喝可可牛奶
LeetCode算法訓(xùn)練-動態(tài)規(guī)劃
理論知識
動態(tài)規(guī)劃當(dāng)前狀態(tài)是由前一個狀態(tài)推導(dǎo)出來的，而貪心沒有狀態(tài)的轉(zhuǎn)移
動態(tài)規(guī)劃需要借助dp數(shù)組桥爽，可能是一維也可能是二維的
- 首先要明確dp數(shù)組是用來干什么的纳击，下標(biāo)對應(yīng)什么
- 狀態(tài)如何轉(zhuǎn)移 续扔？ 也就是理清遞推公式
- dp數(shù)組如何初始化
- 如何遍歷
- 舉個栗子模擬推導(dǎo)一遍
LeetCode 509. 斐波那契數(shù)
分析
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. 爬樓梯
分析
錯誤 沒有理清遞推函數(shù)
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]表示到當(dāng)前樓梯有多少種跳法焕数，從這里可以往后跳一步或者兩步纱昧，這樣就建立了前后階梯的關(guān)系，但是不能跳2個一步
<u>當(dāng)前階梯跳數(shù)能由前一個階梯跳一步或前兩個階梯跳兩步得到</u>
代碼
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. 使用最小花費爬樓梯
整數(shù)數(shù)組 cost 堡赔，cost[i] 是從樓梯第 i 個臺階向上爬需要支付的費用砌些。一旦支付此費用，即可選擇向上爬一個或者兩個臺階。
你可以選擇從下標(biāo)為 0 或下標(biāo)為 1 的臺階開始爬樓梯存璃。
請你計算并返回達到樓梯頂部的最低花費仑荐。
分析
根據(jù)測試用例能夠得出臺階頂部在哪里，cost[i] ：從下標(biāo)i-1爬一步纵东，從i-2爬兩步到臺階頂部
dp[i]表示爬到第i個臺階的最小花費粘招，
狀態(tài)轉(zhuǎn)移：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];
}
}
總結(jié)
- 搞清楚dp數(shù)組含義以及對應(yīng)下標(biāo)反映了什么狀態(tài)
- 弄清楚轉(zhuǎn)移公式
- 初始化
- 確定遍歷順序（這個和轉(zhuǎn)移公式緊密相關(guān)）
- 模擬一下
