动态规划
· 阅读需 21 分钟
原题
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
伪代码
函数 爬楼梯(台阶数 n)：
如果 n 是 1：
返回 1
如果 n 是 2：
返回 2
否则：
返回 爬楼梯(n-1) + 爬楼梯(n-2)
dp[1] = 1
dp[2] = 2
从 3 开始：
dp[3] = dp[2] + dp[1]
dp[4] = dp[3] + dp[2]
……
dp[n] = dp[n-1] + dp[n-2]
编码
/**
* 推荐写法，优化空间
* @param {number} n
* @return {number}
*/
var climbStairs = function (n) {
// 动态规划自底向上计算，从最小层级开始计算
let arr = new Array(n + 1)
if (n == 1) return 1
if (n == 2) return 2
let a = 1
let b = 2
let res = 0
for (let i = 3; i <= n; i++) {
res = a + b
a = b
b = res
}
return res
}
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function (n) {
if (n == 1) return 1
if (n == 2) return 2
let dp = []
dp[1] = 1
dp[2] = 2
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
}
198 打家劫舍
原题
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 400
误区
并不是间隔偷就是最优解
而是求 每个位置之前偷窃的最优解
拆解就是
1 2 3 1
0 --- nums[0]
1 --- max(0) / nums[1]
2 --- max(1) / max(0) + nums[2]
3 --- max(2) / max(1) + nums[3]
...
n --- max(n-1) / max(n-2) + nums[n]
伪代码
函数 rob(nums):
如果 nums 是空，返回 0
如果 只有 1 个房子，返回 nums[0]
创建数组 dp，长度为 nums.length
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
对 i 从 2 到 nums.length - 1:
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
返回 dp[最后一个位置]
编码
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function (nums) {
// 动态规划的题目都要手动推导一遍，找出规律
if (nums.length == 1) return nums[0]
if (nums.length == 2) return Math.max(nums[0], nums[1])
let max = []
max[0] = nums[0]
max[1] = Math.max(nums[0], nums[1])
for (let i = 2; i < nums.length; i++) {
max[i] = Math.max(max[i - 1], max[i - 2] + nums[i])
}
return max[nums.length - 1]
}
746 使用最小花费爬楼梯
原题
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 <= 1000
0 <= cost[i] <= 999
推导
1 100 1 1 1 100 1 1 100 1
可以爬1/2个台阶，所以如果从最底部向上爬，需要付费为 0
总阶梯数量 花费
n = 0, sum = 0
n = 1， sum = 0
n = 2， sum = 0
n = 3， sum = nums[0] / nums[1] --- min
n = 4， sum = min(3) / min(2)
n = 5, sum = min(4) / min(3)
...
n sum = min(n-1) / min(n - 2)
伪代码
function minCostClimbingStairs(cost):
n = length of cost
dp[0] = 0 // 到达第0阶（起点）不花钱
dp[1] = 0 // 到达第1阶（也可作为起点）不花钱
for i from 2 to n:
// 你可以从 i-1 跨一步，或者从 i-2 跨两步
dp[i] = min(
dp[i - 1] + cost[i - 1],
dp[i - 2] + cost[i - 2]
)
return dp[n]
我的解法
| 点 | 你写法 | 正确写法 |
|---|---|---|
| 状态定义 | 正确 ✅ | 正确 ✅ |
| 状态转移 | 正确 ✅ | 正确 ✅ |
初始化 dp | 多余 ❌ | 精简 ✅ |
额外 min[2] | 不必要 ❌ | 不需要，循环中计算 ✅ |
/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function (cost) {
// 求最小花费 + 每次可以跨1或者2个台阶
// ==> 求到最后一个台阶的花费
// ==> 倒数第二个台阶+到倒数第二个台阶的花费 ~ 倒数第一个台阶+到倒数第一个台阶的花费
// ==> 求两个花费得最小值
if (cost.length <= 1) return 0
let min = []
min[0] = 0
min[1] = 0
min[2] = Math.min(cost[0], cost[1])
for (let i = 3; i <= cost.length; i++) {
min[i] = Math.min(min[i - 2] + cost[i - 2], min[i - 1] + cost[i - 1])
}
// console.log({ min, target: min[cost.length] })
return min[cost.length]
}
/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function (cost) {
if (cost.length <= 1) return 0
let min = [0, 0] // 0 1 位置的最小花费都是 0
for (let i = 2; i <= cost.length; i++) {
min[i] = Math.min(min[i - 2] + cost[i - 2], min[i - 1] + cost[i - 1])
}
return min[cost.length]
}
/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function (cost) {
if (cost.length <= 1) return 0
let prev = 0 // dp[i-2]
let curr = 0 // dp[i-1]
for (let i = 2; i <= cost.length; i++) {
const next = Math.min(prev + cost[i - 2], curr + cost[i - 1])
prev = curr
curr = next
}
return curr
}
1137 第 N 个斐波那契数
原题
1137. 第 N 个泰波那契数
提示
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
示例 1：
输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2：
输入：n = 25
输出：1389537
提示：
0 <= n <= 37
答案保证是一个 32 位整数，即 answer <= 2^31 - 1。
伪代码
函数 Tribonacci(n):
如果 n 等于 0，返回 0
如果 n 小于 3，返回 1
初始化数组 prev 为 [0, 1, 1]
从 i = 3 到 n，进行以下操作：
prev[i] = prev[i - 3] + prev[i - 2] + prev[i - 1]
返回 prev[n]
编码
/**
* @param {number} n
* @return {number}
*/
var tribonacci = function (n) {
if (n == 0) return 0
if (n < 3) return 1
let prev = [0, 1, 1]
for (let i = 3; i <= n; i++) {
prev[i] = prev[i - 3] + prev[i - 2] + prev[i - 1]
}
return prev[n]
}
213 打家劫舍 Ⅱ
原题
伪代码
函数 rob(nums):
如果只有 1 个房子：
返回它的钱
情况一：偷第 0 到 n-2 号房子（不偷最后一间）
情况二：偷第 1 到 n-1 号房子（不偷第一间）
分别计算这两种情况的最大偷盗金额：
max1 = 偷[0, n-2] 之间的最大金额
max2 = 偷[1, n-1] 之间的最大金额
返回 max(max1, max2)
函数 偷[start, end]:
dp[i] 表示偷到第 i 间房子为止，最多偷到多少钱
dp[start] = nums[start]
dp[start + 1] = max(nums[start], nums[start + 1])
从 i = start + 2 到 end：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
返回 dp[end]
注意点
- 如果 dp[i] 表示的是偷到第 i 个房子，就直接用 nums[i]；
- 如果 dp[i] 表示的是偷到第 i - 1 个房子，就用 nums[i - 1]。
编码
/**
* 小偷专用函数：打家劫舍 II（房子围成一圈）
* @param {number[]} nums - 每间房子的现金列表
* @return {number} - 最多能偷到多 少钱
*/
var rob = function (nums) {
/**
* 小偷的助手函数：负责在一条直线上的房子里偷东西
* @param {number[]} nums - 所有房子里的现金
* @param {number} start - 从第几个房子开始
* @param {number} end - 偷到第几个房子结束
* @return {number} - 从 start 到 end 之间最多能偷多少钱
*/
function rob_item(nums, start, end) {
// 如果房子是空的，啥都偷不到
if (nums.length == 0) return 0
// 如果只有一个房子，那就直接偷它！
if (nums.length == 1) return nums[0]
// 如果 start 和 end 是同一个房子，就只能偷这一家
if (start == end) return nums[start]
// 创建一个记账本 dp，用来记每一步最多能偷多少钱
let dp = []
// 第一个能偷的房子是 start，把它偷了
dp[start] = nums[start]
// 第二个房子是 start+1，这时我们要选：偷 start 还是 start+1，谁钱多偷谁
dp[start + 1] = Math.max(nums[start], nums[start + 1])
// 从第三个房子开始（也就是 start + 2），我们一个一个往后看
for (let i = start + 2; i <= end; i++) {
// 有两个选择：
// 1. 不偷这一家，那就保持前一个的偷法（dp[i - 1]）
// 2. 偷这一家，那前一家不能偷，所以是 dp[i - 2] + nums[i]
// 然后比较这两个选项，选钱多的那个
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
}
// 最后返回偷到第 end 家时最多能偷多少钱
return dp[end]
}
const len = nums.length - 1
// 特别情况：如果只有一间房子，那直接偷它就好
if (nums.length === 1) return nums[0]
// 情况一：不偷最后一家 → 偷第 0 到 len-1 家
const max1 = rob_item(nums, 0, len - 1)
// 情况二：不偷第一家 → 偷第 1 到 len 家
const max2 = rob_item(nums, 1, len)
// 比较两个方案哪个偷的钱更多，返回最多的那个
const res = Math.max(max1, max2)
return res
}
740 删除并获得点数
原题
740. 删除并获得点数
提示
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。
示例 2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。
提示：
1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104
思路
-
理解题目，选中数 i 的之后，
i-1和i+1也要被移除，获得点数 i，即，i 一旦被移除掉，旁边两个数值也得被移除掉 ====> 数据需要按照大小排列，想办法让数值和 index 关联起来 ====> 用哈希表存储，key值 ~ value出现次数 -
那么，如果存在相同的 i 呢？ -----> 一旦第一个 i 被移除掉，就会直接删掉相邻的点，后面再遇到相同的 i 不需要再删除相邻 点数了，因此有 x 个 i，就有
x*i的点数 -
所以用于最后计算的哈希表要和总分挂钩，由
key值 ~ value出现个数得到key值 ~ value总分 -
然后逐个分析规律
- 处理到第一个元素的最大得分是 dp[i] = nums[i]
- 处理到第二个元素的最大得分是 dp[i] = max(dp[i-1], nums[i])
- 处理到第三个元素的最大得分是 dp[i] = max(dp[i-1], dp[i-2]+nums[i]) 【可能最后一个选中的值是 nums[i] ，也可能是 num[i-1],如果最后一个是 num[i-1] 那么 nums[i] 会被删除不处理；如果最后一个是 num[i] ，那就需要计算 dp[i-2]+nums[i]】
-
由此发现这个问题其实是
打家劫舍问题的变形
联想
✅ 转化为打家劫舍问题如果你选择了数字 x，就不能选择 x-1 和 x+1 可以先把同一个数字的总得分算出来，比如：
- nums = [2, 2, 3, 3, 3, 4] =>
- count[2] = 4 // 2 + 2
- count[3] = 9 // 3 + 3 + 3
- count[4] = 4 // 4
然后你要在 count[i] 上做选择：选 i 就不能选 i-1，就成了打家劫舍问题的动态规划形式：
dp[i] = max(dp[i-1], dp[i-2] + count[i])
想象你在“吃糖果”：
- 每种数字是一种糖果，吃一个数字就把它全都吃光（得分 = 数字 × 数量）
- 但吃掉一种糖果之后，相邻的糖果就会被扔掉（不能再得分）
- 所以你要聪明地安排先吃哪些，后吃 哪些，才能得到最多糖果！
编码
/**
* @param {number[]} nums
* @return {number}
*/
var deleteAndEarn = function (nums) {
// 1. 边界处理
if (nums.length == 0) return 0
if (nums.length == 1) return nums[0]
// 2. 不关注排序，只关注最大值
const maxVal = Math.max(...nums)
// 3. 初始化总数数组，避免数组越界
let count = new Array(maxVal + 1).fill(0)
// 4. 遍历数组，获取 总数-下标 关联数组
for (let num of nums) {
count[num] += num
}
let prev2 = count[0] // 相当于 dp[i - 2]
let prev1 = Math.max(count[0], count[1]) // 相当于 dp[i - 1]
for (let i = 2; i <= maxVal; i++) {
const curr = Math.max(prev1, prev2 + count[i])
prev2 = prev1
prev1 = curr
}
return prev1
}
62 不同的路径
原题
问题理解
- 一个 m x n 的网格
- 机器人只能 向右 或 向下 移动
- 起点是左上角 (0, 0)，终点是右下角 (m-1, n-1)
- 问：有多少种路径从起点走到终点？
动态规划思路
-
定义一个二维数组 dp[i][j] 表示从起点到 (i, j) 位置的路径总数
-
初始化第一行和第一列：机器人只能一直往右/往下走，所以路径数都是 1
-
状态转移方程：
dp[i][j] = dp[i-1][j] + dp[i][j-1] 从上面来一步：dp[i-1][j]
从左边来一步：dp[i][j-1]
最终答案是：dp[m-1][n-1]
伪代码
function uniquePaths(m, n):
创建二维数组 dp，大小为 m x n，所有元素初始为 1
for i 从 1 到 m-1:
for j 从 1 到 n-1:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
返回 dp[m-1][n-1]
举例说明（m = 3, n = 3）
初始状态：
1 1 1
1 ? ?
1 ? ?
一步步填充：
1 1 1
1 2 3
1 3 6
最后的答案是：6
分析
✅ 我使用的写法：用 Array.from() 一步搞定
const dp = Array.from({ length: m }, () => Array(n).fill(1))
🔍 它做的事情就是：
- { length: m }：只是告诉 Array.from 要生成 m 个元素
- () => Array(n).fill(1)：告诉它每一项该填啥 —— 就是一个 n 长度、值全是 1 的数组
编码
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function (m, n) {
let dp = Array.from({ length: m }, () => Array(n).fill(1))
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
// 计算到 (i,j) 的路径，限制只能向右向下
// 所以可以从 dp[i-1][j]，dp[i][j-1] 两个点过来
}
}
return dp[m - 1][n - 1]
}