前言
算法好像已经断更了好久, 十月份没控制住自己, 玩了一整个月, 今天开始争取补回来, 「代码随想录·算法训练营」已经开始第 48 天了, 把打卡表格缩小到 30% 之后才看到我上次打卡的内容, 现在已经开始动态规划部分了, 准备从第 38 天开始追, (Ps: day38 是本篇文章, 也是动态规划的基础题目)
今日任务:
- 动态规划理论基础
- 509. 斐波那契数
- 70. 爬楼梯
- 746. 使用最小花费爬楼梯
动态规划理论基础
什么是动态规划?
某一问题可以分解为很多重叠的子问题，而这些子问题之间存在着递进的状态推导关系。对这类问题的求解方法称为动态规划
动态规划五部曲
- 确定 dp 数组以及下标的含义
- 确定递推公式
- dp 数组如何初始化
- 确认遍历顺序
- 举例推导 dp 数组
重中之重: 如果你看了题解, 也模仿着写出来了, 但是就是通过不了, 那么一定要思考三个问题
- 这道题目我举例推导状态转移公式了么？
- 我打印dp数组的日志了么？
- 打印出来了dp数组和我想的一样么？
509. 斐波那契数
题目描述
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 复制代码
给定 n ，请计算 F(n) 。
示例 1：
输入： n = 2 输出： 1 解释： F(2) = F(1) + F(0) = 1 + 0 = 1 复制代码
示例 2：
输入： n = 3 输出： 2 解释： F(3) = F(2) + F(1) = 1 + 1 = 2 复制代码
示例 3：
输入： n = 4 输出： 3 解释： F(4) = F(3) + F(2) = 2 + 1 = 3 复制代码
提示：
0 <= n <= 30
思路分析
- 确定 dp 数组以及下标的含义
- 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 数组
- 按照递推公式 dp[i] = dp[i-1] + dp[i-2] 进行推导, 假设 n == 10, 那么 dp 数组肯定如下所示
- 0 1 1 2 3 5 8 13 21 34 55
代码展示
class Solution { public int fib(int n) // 当 n<=1 时, 直接返回 n, 不用进行推导 if (n <= 1){ return n; } // 确定 dp 数组大小, 注: n == 10 时, 数组应该有 11 个元素 int[] ints = new int[n+1]; // 初始化数组 ints[0] = 0; ints[1] = 1; // 遍历计算 for (int i = 2; i <= n; i++) { // 使用推导公式计算 dp 数组 ints[i] = ints[i - 1] + ints[i - 2]; } // 返回第 n+1 个元素 return ints[n]; } } 复制代码
提交结果
错误分析
在第一次解答出错的时候, 是数组设置成了长度为 n, 没有想明白, 也是自信了, 没有自己 debug 走一下
第二, 三次解答出错, 分别是因为数组扩容之后 for 循环忘记 i <= n 了, 还有是 return 返回的时候返回成了 ints[n - 1]
70. 爬楼梯
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入： n = 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 复制代码
示例 2：
输入： n = 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶 复制代码
提示：
1 <= n <= 45
思路分析
依旧根据 动态规划五部曲 进行分析
- 确定 dp 数组以及下标的含义
- dp 数组的长度应该是 n, 和台阶数相等, 每一个下标都应该是有多少种不同的方法
- 递推公式 (这里我好半天才理解明白, 重点)
- 由题可知, 每次只能跳 1 个台阶或者 2 个台阶, 那么 dp[n] 只可能由 dp[n-1] 或 dp[n-2] 跳上去
- 所以有 dp[n-1] 种方法和 dp[n-2] 种方法, 跳上 dp[n] 台阶
- 所以 dp[n] = dp[n-1] + dp[n-2]
- dp 数组初始化
- 根据第一步, dp数组及下标含义可知, dp[n] = 第 n 个台阶有多少种方法
- dp[0] = 0, dp[1] = 1, dp[2] = 2
- 确认遍历顺序
- 经过综上分析, 爬楼梯应该是 从前往后 的顺序进行遍历
- 举例推导 dp 数组
- 当 n = 10 时, dp 数组的长度应该为 11
- dp 数组 = [0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
代码展示
public static int climbStairs(int n) { if (n < 3){ return n; } // 确定 dp 数组长度, 并初始化 int[] ints = new int[n+1]; ints[1] = 1; ints[2] = 2; // 遍历, 从 i = 3 开始, 长度为 n+1 for (int i = 3; i < n+1; i++) { // 使用推导公式, 确定到达每个台阶的方法数 ints[i] = ints[i-1] + ints[i-2]; } return ints[n]; } 复制代码
提交结果
746. 使用最小花费爬楼梯
题目描述
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入： cost = [10,15,20] 输出： 15 解释： 你将从下标为 1 的台阶开始。 - 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。 复制代码
示例 2：
输入： cost = [1,100,1,1,1,100,1,1,100,1] 输出： 6 解释： 你将从下标为 0 的台阶开始。 - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。 - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。 - 支付 1 ，向上爬一个台阶，到达楼梯顶部。 总花费为 6 。 复制代码
提示：
2 <= cost.length <= 10000 <= cost[i] <= 999
思路分析
老规矩, 动态规划五部曲
- 确定 dp 数组以及下标的含义
- 到达 dp[i] 最少花费的费用
- 确定递推公式
- 在本题, 一共有两种方式可以得到 dp[i] 的花费, 一种是通过 dp[i-1], 一种是 dp[i-2]
- dp[i] = dp[i-1] + cost[i-1] <== 走了一步到达
- dp[i] = dp[i-2] + cost[i-2] <== 走了两步到达
- 本题要求得最小花费, 那么 dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
- dp 数组初始化
- 由题可知: 你可以选择从下标为
0或下标为1的台阶开始爬楼梯。所以在 dp[0] 和 dp[1] 的情况下是 0 花费的 - dp[0] = 0
- dp[1] = 0
- 举例推导 dp 数组
- 如下图所示
代码展示
public static int minCostClimbingStairs(int[] cost) { // 初始化 dp 数组 int[] dp = new int[cost.length + 1]; // 遍历为 dp 数组赋值, int 数组默认元素为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]; } 复制代码
提交结果
总结
第一次接触 动态规划 目前脑海中对这种类型的题有了初步的解题思路, 但是研究不出来的时候还是要看一眼题解, 今日三道题用时 90 分钟
