Day32–动态规划–509. 斐波那契数，70. 爬楼梯，746. 使用最小花费爬楼梯
《代码随想录》：
动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的。
这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
动态规划五步曲：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
509. 斐波那契数
方法：递归法
思路：
// 递归法
class Solution {
public int fib(int n) {
// 前两个数是初始化，无法通过递归得出
if (n == 0 || n == 1) {
return n;
} else {
// 公式递归
return fib(n - 1) + fib(n - 2);
}
}
}
方法：动态规划
思路：
动态规划五步曲：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
class Solution {
public int fib(int n) {
if (n == 0 || n == 1) {
return n;
}
// 1.dp[i]指的是第i个数的斐波那契数值
// 从0到n是有n+1个数值
int[] dp = new int[n + 1];
// 3.初始化
dp[0] = 0;
dp[1] = 1;
// 4.遍历顺序，从前往后
for (int i = 2; i <= n; i++) {
// 2.递推公式
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
方法：动态规划
思路：
优化空间。其实只需要三个空间就可以完成了。
可以发现当计算完dp[i] = dp[i-1]+dp[i-2]之后，dp[i-2]就没用了。
此轮的dp[i-1]会变成下一轮的dp[i-2]，所以整个数组左移一位，动态覆盖就好。
// 动态规划（空间优化版）
class Solution {
public int fib(int n) {
if (n == 0 || n == 1) {
return n;
}
int[] dp = new int[3];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
// 递推公式
dp[2] = dp[0] + dp[1];
// 计算完dp[2]之后，dp[0]就没用了，整体往前一个位置。
dp[0] = dp[1];
dp[1] = dp[2];
}
return dp[2];
}
}
70. 爬楼梯
方法：递归，回溯
思路：
超时，太暴力了。时间复杂度是2^n，指数级别的，很恐怖。
// 回溯法（超时，太暴力了）
class Solution {
int count = 0;
int pathSum = 0;
public int climbStairs(int n) {
backtracking(n);
return count;
}
private void backtracking(int n) {
if (pathSum == n) {
count++;
return;
}
if (pathSum > n) {
return;
}
// 每一轮选1或者2
for (int i = 1; i <= 2; i++) {
pathSum += i;
backtracking(n);
pathSum -= i;
}
}
}
方法：动态规划
思路：
- 因为每一次可以走一步或者两步，当n是3的时候，肯定是从1或者2那里跳过来的
- 所以1或者2有几种可能，3就是它俩的总和
- 由此得出递推公式：dp[i] = dp[i-1]+ dp[i-2];（这不就是斐波那契数列吗？）
// 动态规划
class Solution {
public int climbStairs(int n) {
if (n == 1 || n == 2) {
return n;
}
// 虽然从1到n只有n个数，但是0是无意义的，所以初始化要从1开始，数组长度要n+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];
}
}
同样，这里可以进行空间优化，仅用3个空间。参考上一题的实现。不再赘述。
746. 使用最小花费爬楼梯
方法：动态规划
思路：
- 这里可以理解为，跳了之后才收费。dp[i]看是从dp[i-1]跳上来的，还是dp[i-2]跳上来的，对应加上那个格子的cost[]
- 注意：n+1才是楼顶，在索引n的地方
// 动态规划
// 这里可以理解为，跳了之后才收费。dp[i]看是从dp[i-1]跳上来的，还是dp[i-2]跳上来的，对应加上那个格子的cost[]
// 注意：n+1才是楼顶，在索引n的地方
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n + 1];
// 从下标为 0 或下标为 1 的台阶开始，因此支付费用为0
dp[0] = 0;
dp[1] = 0;
// 计算到达每一层台阶的最小费用
for (int i = 2; i <= n; i++) {
// dp是前面的跳到那个位置的累加和，因为是跳了之后才收费，所以要加上对应的cost[]
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
}
测试用例的dp[]情况：
n:3
cost:[10,15,20]
dp:[0,0,10,15]
index:[0,1,2,n]
n:10
cost:[1,100,1,1,1,100,1,1,100,1]
dp:[0,0,1,2,2,3,3,4,4,5,6]
index:[0,1,2,3,4,5,6,7,8,9,n]
n+1才是楼顶，在索引n的地方