动态规划
概念
动态规划（Dynamic Programming），因此常用 DP 指代动态规划。如果某一问题有很多重叠子问题，那么使用动态规划是最有效的。
通过将问题分解为相互重叠的子问题，并利用子问题的解来高效求解原问题（利用历史记录，来避免我们重复的计算）
状态定义
- 用数组表示问题的某个阶段或子问题的解，一定要明确 dp 数组
dp[i][j]代表的含义 - 如在背包问题中，
dp[i][j]表示前 i 个物品放入容量为 j 的背包的最大价值
- 用数组表示问题的某个阶段或子问题的解，一定要明确 dp 数组
确定状态转移方程
- 明确如何从子问题的解推导出当前问题的解，即找出数组间关系式，最难最重要的一步
- 通俗讲就是找出 dp[i] 与 dp[i-1]、dp[i-2]之间的关系
- 如斐波那契数列的转移方程：
dp[i] = dp[i-1] + dp[i-2]
初始化边界条件
- 确定初始状态的值，dp 数组的第 n 项结果由状态转移方程求解得到，所以需要知道第 n-1 项，第 n-2 项...第 1 项的值
- 初始化 dp 数组的值，如斐波那契数列中 dp[0] = 0, dp[1] = 1
解题步骤
动规五部曲
- 确定 dp 数组（dp table）以及下标的含义
- 确定递推公式
- dp 数组如何初始化
- 确定遍历顺序
- 举例推导 dp 数组
为何先确定递推公式，在初始化 dp 数组呢？
因为一些情况的递推公式决定了 dp 数组要如何初始化！
动态规划如何 debug
找问题最好的方式就是把 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：
- 输入：2
- 输出：1
- 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
- 输入：3
- 输出：2
- 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
- 输入：4
- 输出：3
- 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：
- 0 <= n <= 30
解题思路
动规五部曲
确定 dp 数组以及下标的含义
dp[i] 代表第 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 数组
按照递推公式，我们推导下 n=10 的时候，dp 数组应该是这个数列：
[0,1,1,2,3,5,8,13,21,34,55]写代码时打印 dp 数组，看和我们推导的数组是否一致
var fib = function (n) {
const dp = [0, 1]
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]
}
console.log(dp)
return dp[n]
}
70. 爬楼梯 🌟
力扣链接 🌟
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
- 输入： 2
- 输出： 2
- 解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
- 输入： 3
- 输出： 3
- 解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
解题思路
注意此处是求到达第 i 层的方法数，而不是具体的步数或花费
先确定条件，每次只能爬一层或两层楼梯，那么
- 第一层 1 种方法：
1 - 第二层 2 种方法：
1+1、2
爬到第三层楼梯时，只有两种方法：
- 爬到第一层，再爬两层到第三层：
1+1+1、1+2 - 爬到第二层，直接一层到第三层：
2+1 - 那么总方法数 = 2 + 1 = 3
爬到第四层楼梯时，只有两种方法：
- 爬到第二层，再爬两层到第四层：
1+1+2、2+2 - 爬到第三层，直接一层到第四层：
1+1+1+1、1+2+1、2+1+1 - 总方法数：2 + 3 = 5
因此，爬到第 i 层楼梯时，也只有两种方法：
- 爬到第 i-2 层，再爬两层到第 i 层：
i-2 + 2 - 爬到第 i-1 层，直接一层到第 i 层：
i-1 + 1 - 总方法数：dp(i - 2) + dp(i - 1)
因为每一步可以选择爬 1 或 2 层，所以到达第 i 层的方法数等于到达第 i-1 层和第 i-2 层的方法数之和，所以可得递推公式 dp(i) = dp(i-2) + dp(i-1)
动规五部曲：
确定 dp 数组以及下标的含义
dp[i] 表示爬到第 i 层楼梯的方法数 （注意：是方法数，不是步数或体力消耗）
确定递推公式
dp[i] = dp[i-2] + dp[i-1]dp 数组初始化
dp[1] = 1, dp[2] = 2确定遍历顺序 从前往后
举例推导 dp 数组
当 n=5 时，dp 数组为：
[1,2,3,5,8]，代码中打印一下
var climbStairs = function (n) {
const dp = [1, 2]
for (let i = 2; i < n; i++) {
dp[i] = dp[i - 2] + dp[i - 1]
}
console.log(dp)
return dp[n - 1]
}
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
解题思路
先确定条件，每次只能爬一个或两个台阶，并且需要花费相应的体力，如何到达楼梯顶部。
以[1,100,1,1,1,100,1,1,100,1]为例：
想要到达第三个台阶，可以选择：
- 从第一个台阶开始，花费 1，到达第三个台阶
- 从第二个台阶开始，花费 100，到达第三个台阶
此时选择花费较小的第一个选择，即 1
想要到达第四个台阶，可以选择：
- 从第二个台阶开始，花费 100，到达第四个台阶
- 从第三个台阶开始，花费 1，到达第四个台阶
此时选择花费较小的第二个选择，即 1 + 1 = 2
那么，想要到达第 i 个台阶时，可以选择：
- 从第 i-2 个台阶开始，花费 cost[i-2]，到达第 i 个台阶
- 从第 i-1 个台阶开始，花费 cost[i-1]，到达第 i 个台阶
选择花费较小的选择，即 dp[i-2] + cost[i-2] 或者 dp[i-1] + cost[i-1]
因此可以得到递推公式：dp(i) = Math.min(dp(i-2) + cost[i-2], dp(i-1) + cost[i-1])
动规五部曲
确定 dp 数组以及下标的含义
dp[i] 表示到达第 i 个台阶的最小花费
确定递推公式
dp[i] = Math.min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1])dp 数组初始化
可以从下标为 0 或者下标为 1 的台阶开始爬楼梯，即
dp[0] = 0, dp[1] = 0确定遍历顺序：从前往后
举例推导 dp 数组
如 cost = [1,100,1,1,1,100,1,1,100,1]，dp 数组为：
[0,0,1,2,2,3,3,4,4,5,6]
var minCostClimbingStairs = function (cost) {
const dp = [0, 0]
for (let i = 2; i <= cost.length; i++) {
dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1])
}
console.log(dp)
return dp[cost.length]
}
京ICP备2022027737号
Copyright © 2022 - present @wangxiang