理论基础
动态规划五部曲
- 确定dp数组
- 递推公式
- dp数组如何初始化
- 确定遍历顺序
- 打印dp数组
509. 斐波那契数
本题比较简单，直接套用动态规划五部曲即可
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 < n + 1; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
70. 爬楼梯
70. 爬楼梯 - 力扣（LeetCode）
本题主要能看出走n阶方法=n-1阶的方法+n-2阶的方法（因为前提是只能走1或2步），那么本质就是斐波那契数
class Solution {
public int climbStairs(int n) {
int dp[] = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i < n + 1; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
746. 使用最小花费爬楼梯
746. 使用最小花费爬楼梯 - 力扣（LeetCode）
本题要明白一个前提，楼顶并不是数组最后一个元素，而是在其下一位，也就是超出数组范围，所以dp数组大小应该是是length+1，而dp数组的含义就是到达i层需要的最小花费
class Solution {
public int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length + 1];
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i < dp.length; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[cost.length];
}
}
