代码随想录算法训练营第三十八天 | LeetCode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯
1. 动态规划理论基础
1.1 动态规划能解决什么题目
- 动规基础
- 背包问题
- 打家劫舍
- 股票问题
- 子序列问题
1.2 什么是动态规划
动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。
但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。
所以贪心解决不了动态规划的问题。
其实大家也不用死扣动规和贪心的理论区别，后面做做题目自然就知道了。
大家只要知道动规是由前一个状态推导出来的，而贪心是局部直接选最优的。
1.3 动态规划的解题步骤
对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例打印推导dp数组
一些同学可能想为什么要先确定递推公式，然后在考虑初始化呢？
因为一些情况是递推公式决定了dp数组要如何初始化！
1.4 动态规划如何debug
找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！
很多人对于dp的学习是黑盒的状态，就是不清楚dp数组的含义，不懂为什么这么初始化，递推公式背下来了，遍历顺序靠习惯就是这么写的，然后一鼓作气写出代码，如果代码能通过万事大吉，通过不了的话就凭感觉改一改
做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。
然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。
如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。
如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。
如果发现自己的代码和题解一样但是通过不了，就灵魂三问：
- 这道题目我举例推导状态转移公式了么？
- 我打印dp数组的日志了么？
- 打印出来了dp数组和我想的一样么？
如果这灵魂三问自己都做到了，基本上这道题目也就解决了，或者更清晰的知道自己究竟是哪一点不明白，是状态转移不明白，还是实现代码不知道该怎么写，还是不理解遍历dp数组的顺序。
以上关于动态规划的理论基础来源于代码随想录Carl
2. LeetCode 509. 斐波那契数
2.1 思路
- 简单题有很多方法直接上动态规划步骤：
- 确定 dp[i] 数组含义及下标：dp[i] 第 i 个斐波那契数为 dp[i]
- 递推公式：dp[i]=dp[i-1]+dp[i-2]。这题简单就简单在这里题目已经告诉了
- dp 数组如何初始化：dp[0]=0；dp[1]=1
- 遍历顺序：从前向后遍历，这样才能保证 dp[i] 是由 dp[i-1] 和 dp[i-2] 构成的
- 打印 dp 数组：主要用来 debug
- 注意：我们创建 dp 数组的长度是 n+1，因为 n+1 是数组长度，下标是 0~n。然后 for 循环遍历里 i<dp.length 也可以，i<=n 也可以，因为其实第 n 个斐波那契数是在 dp[n] 这个位置的，这也就是为什么我们要从定义长度为 n+1，遍历时 <=n 的原因。最后是 return dp[n]
- 也可以不用定义数组，就定义三个变量，a=0，b=1，c=0；在 for 循环中 c=a+b；a=b；b=c。最后 return c 即可
2.2 代码
// //非压缩状态的版本 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]; } } //压缩状态的版本 class Solution { public int fib(int n) { if (n < 2) return n; int a = 0, b = 1, c = 0; for (int i = 1; i < n; i++) { c = a + b; a = b; b = c; } return c; } }
3. LeetCode 70. 爬楼梯
3.1 思路
- 有 n 阶楼梯，爬了 n 阶楼梯到达楼顶有多少种方法。举例推导，假设是 1 阶，从 0 到 1，1 种方法。2 阶，从 0 到 2，从 1 到 2，2 种方法。3 阶，从 1 到 3，从 2 到 3，不能从 0 到 3，而 1 阶、2 阶和 3 阶有什么关系，就是前 2 种方法相加，因此是 3 种。不要混淆，走到 1 阶有 1 种方法，从 1 阶再走到 3 不是另一种方法，不是 1+1=2，误认为 2 的是因为把方法理解成步数了
- 确定 dp 数组及下标的含义：达到 i 阶有 dp[i] 种方法。
- 确定递推公式：dp[i] 是由前两阶的方法相机的，dp[i]=dp[i-1]+dp[i-2]
- 初始化 dp 数组：注意题目的 n 给的是正整数，n 不为 0。 因此 dp[0] 没有意义，因为我们 dp[i] 的含义是"达到 i 阶有 dp[i] 种方法"。因此初始化 dp[1]=1，dp[2]=2 即不考虑 0 阶的情况
- 遍历顺序：只有从前向后遍历，这样才能保证 dp[i] 是由 dp[i-1] 和 dp[i-2] 相加构成的
- 打印 dp 数组：自己推导模拟一下后面几阶。
- 这题和509. 斐波那契数的区别在于 0 下标的 dp[0] 是没意义的
3.2 代码
// // 常规方式 public int climbStairs(int n) { int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } 用变量记录代替数组 class Solution { public int climbStairs(int n) { if(n <= 2) return n; int a = 1, b = 2, sum = 0; for(int i = 3; i <= n; i++){ sum = a + b; // f(i - 1) + f(i - 2) a = b; // 记录f(i - 1)，即下一轮的f(i - 2) b = sum; // 记录f(i)，即下一轮的f(i - 1) } return b; } }
4. LeetCode 746. 使用最小花费爬楼梯
4.1 思路
- 模糊点 1：比如 [10,15,20]，假设我们是站在下标 0 的位置，消耗的是 10，那我是站在 0 位置花费 10 还是从 0 开始跳上去后花费 10 呢？是后者，站在上面是不花费的。
- 模糊点 2：楼顶在哪？比如 [10,15,20]，我们的楼顶是下标 2 的位置吗？不是，因此应该是下标 3 的位置。这题相当于70. 爬楼梯的消费版
- 确定 dp 数组及下标的含义：dp[i] 表示到达 i 位置最小花费为 dp[i]
- 递推公式：dp[i]=Math.min（dp[i-1]+cost[i-1]，dp[i-2]+cost[i-2]），回顾一下 dp[i] 的意思，到达 dp[i] 位置的最小花费，要想到达下一步就要花费对应的 cost[i] 才行，而我们要的是最小化费，因此需要取两者最小值
- 初始化 dp 数组：由于题目说可以从下标 0 和 1 的位置开始，往上跳的时候才花费对应位置的体力。因此 dp[1] 和 dp[0] 都初始化为 0，因为我们从这两个位置开始是不花费体力的，往上跳才花费
- 遍历顺序：正常的从前往后
- 打印 dp 数组：用于 debug，看看是不是按照我们预想的出来的
4.2 代码
// // 方式一：第一步不支付费用 class Solution { public int minCostClimbingStairs(int[] cost) { int len = cost.length; int[] dp = new int[len + 1]; // 从下标为 0 或下标为 1 的台阶开始，因此支付费用为0 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]; } }
