前置知識(shí)
做題步驟：
- 找問題的最好方式就是把dp數(shù)組打印出來，搞清楚每一個(gè)值代表的含義
- 遞推公式
- dp數(shù)組初始化运敢、遍歷順序
509. 斐波那契數(shù)
題目鏈接/文字講解：斐波那契數(shù)
題設(shè)：斐波那契數(shù)（通常用 F(n) 表示）形成的序列稱為 斐波那契數(shù)列 盯质。該數(shù)列由 0 和 1 開始，后面的每一項(xiàng)數(shù)字都是前面兩項(xiàng)數(shù)字的和刨沦。也就是：
F(0) = 0，F(xiàn)(1) = 1
F(n) = F(n - 1) + F(n - 2)膘怕，其中 n > 1
給定 n 想诅，請(qǐng)計(jì)算 F(n) 。
思路：動(dòng)規(guī)五部曲：
要用一個(gè)一維dp數(shù)組來保存遞歸的結(jié)果
1.確定dp數(shù)組以及下標(biāo)的含義-dp[i]的定義為：第i個(gè)數(shù)的斐波那契數(shù)值是dp[i]
2.確定遞推公式-狀態(tài)轉(zhuǎn)移方程 dp[i] = dp[i - 1] + dp[i - 2];
3.dp數(shù)組如何初始化
4.確定遍歷順序-dp[i]是依賴 dp[i - 1] 和 dp[i - 2]岛心，那么遍歷的順序一定是從前到后遍歷的
5.舉例推導(dǎo)dp數(shù)組
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 i = 2; i < dp.length; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
70. 爬樓梯
題目鏈接/文字講解：爬樓梯
題設(shè)：假設(shè)你正在爬樓梯来破。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階忘古。你有多少種不同的方法可以爬到樓頂呢徘禁？
思路：動(dòng)規(guī)五部曲：
定義一個(gè)一維數(shù)組來記錄不同樓層的狀態(tài)
1.確定dp數(shù)組以及下標(biāo)的含義-dp[i]： 爬到第i層樓梯，有dp[i]種方法
2.確定遞推公式-dp[i] = dp[i - 1] + dp[i - 2] 髓堪。
3.dp數(shù)組如何初始化-再回顧一下dp[i]的定義：爬到第i層樓梯送朱，有dp[i]種方法。
題目中說了n是一個(gè)正整數(shù)干旁，題目根本就沒說n有為0的情況驶沼。
只初始化dp[1] = 1，dp[2] = 2争群，然后從i = 3開始遞推回怜，這樣才符合dp[i]的定義。
4.確定遍歷順序-從遞推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出换薄，遍歷順序一定是從前向后遍歷的
5.舉例推導(dǎo)dp數(shù)組
class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i < dp.length; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
和斐波那契基本沒區(qū)別玉雾。當(dāng)然，還可以拓展一下专控，若是每步可走1-m怎么辦抹凳，這種情況其實(shí)和背包問題相似。
746. 使用最小花費(fèi)爬樓梯
題目鏈接/文字講解：使用最小花費(fèi)爬樓梯
題設(shè)：給你一個(gè)整數(shù)數(shù)組 cost 伦腐，其中 cost[i] 是從樓梯第 i 個(gè)臺(tái)階向上爬需要支付的費(fèi)用赢底。一旦你支付此費(fèi)用，即可選擇向上爬一個(gè)或者兩個(gè)臺(tái)階。
你可以選擇從下標(biāo)為 0 或下標(biāo)為 1 的臺(tái)階開始爬樓梯幸冻。請(qǐng)你計(jì)算并返回達(dá)到樓梯頂部的最低花費(fèi)屯烦。
思路：動(dòng)規(guī)五部曲：
1.確定dp數(shù)組以及下標(biāo)的含義-dp[i]： 爬到第i層樓梯贩耐，消耗的最少費(fèi)用津函。
2.確定遞推公式-當(dāng)前為第i個(gè)臺(tái)階张抄，爬過它所需要的最少消耗為其本身消耗+min(第i-1個(gè)臺(tái)階消耗,第i-2個(gè)臺(tái)階消耗)。
3.dp數(shù)組如何初始化-再回顧一下dp[i]的定義：dp[0]=cost[0],dp[1]=cost[1]碑定。(可以選擇從0/1開始)
4.確定遍歷順序-從下往上爬流码，遍歷順序一定是從前向后遍歷的。不需要考慮數(shù)組長度為0延刘，1的情況漫试。
5.舉例推導(dǎo)dp數(shù)組。
class Solution {
public int minCostClimbingStairs(int[] cost) {
if (cost.length == 2) return Math.min(cost[1], cost[0]);
int[] dp = new int[cost.length];
dp[0] = cost[0];
dp[1] = cost[1];
for (int i = 2; i < dp.length; i++) {
dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
}
return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
}
}
