1. 怎么看动态规划题

动态规划的核心不是“建一个 dp 数组”,而是:把大问题拆成会重复出现的子问题,保存子问题答案,再按照依赖关系逐步推出最终答案。

一道题可能适合动态规划,通常会有这些信号:

  • 求最大值、最小值、方案数,或者问某个目标是否可行。
  • 暴力递归的参数会反复出现,同一个子问题被计算很多次。
  • 每一步有有限种选择,比如选或不选、买或卖、偷或不偷。
  • 题目能用“前 i 个元素”“容量 j”“两个字符串的前缀”“区间 [i, j]”描述子问题。
  • 当前状态只依赖已经解决的较小状态,不需要保留完整选择历史。

但看到“最大、最小、方案数”不代表一定是 DP:

  • 如果一个局部选择做完后永远不需要后悔,可能是贪心。
  • 如果要列出所有具体方案,可能是回溯。
  • 如果状态是图上的节点和边,可能是 BFS、最短路或拓扑排序。

动态规划和记忆化搜索本质上是在解同一类状态:

  • 记忆化搜索是自顶向下:从答案出发递归,需要哪个状态就计算哪个状态。
  • 递推 DP 是自底向上:先算小状态,再按依赖顺序填完整张表。

写题时不要先想“这是一维还是二维”。先用一句完整的话定义状态;维度只是状态里有几个会变化的参数。

2. DP 五步法:先定义,再递推

每道动态规划题都可以按下面五步检查。

步骤 要回答的问题 常见错误
1. 定义状态 dp[i] 或 dp[i][j] 到底表示什么? 只写公式,不写状态含义
2. 写递推公式 当前状态来自哪些更小状态?最后一步做了什么? 漏掉一种选择,或读到未计算状态
3. 初始化 最小问题的答案是什么?不可达状态用什么值? 计数题忘记 dp[0] = 1
4. 确定遍历顺序 转移依赖的状态是否已经算好? 0-1 背包把容量写成正序
5. 确定答案位置 答案是 dp[-1]、max(dp),还是 dp[m][n]? “以 i 结尾”却直接返回最后一格

2.1 状态定义必须是一句话

例如 70. 爬楼梯:

1
dp[i] 表示到达第 i 阶楼梯的方法数。

那么到达第 i 阶的最后一步只有两种可能:

1
2
从 i - 1 走 1 阶过来
从 i - 2 走 2 阶过来

所以:

1
dp[i] = dp[i - 1] + dp[i - 2]

如果状态定义成“从第 i 阶走到楼顶的方法数”,公式可能长得相似,但初始化和答案位置都会改变。状态定义、递推、初始化和遍历顺序必须是一套完整语义。

2.2 初始化由问题类型决定

常见中性值可以这样记:

问题类型 常见初始化 含义
最大值 -inf 或题目允许的最小值 尚未得到合法方案
最小值 inf 尚未到达,不能让 0 干扰取最小值
计数 dp[0] = 1 什么都不选,构成总和 0 的空方案有 1 种
可行性 dp[0] = True 总和 0 可以由空集合组成

初始化不是固定模板。每个初值都应该能用状态定义解释。

2.3 遍历顺序由依赖方向决定

如果递推式读取:

1
2
dp[i - 1]
dp[i - 2]

那么 i 要从小到大遍历。如果区间 DP 读取 dp[i + 1][j - 1],那么 i 通常要从大到小遍历。背包的一维压缩更依赖遍历方向:方向写错,题型会直接从 0-1 背包变成完全背包。

调试 DP 时,先用最小样例打印整张表:

1
print(dp)

逐格确认“这一格为什么是这个值”,比只检查最终答案有效得多。

3. 基础一维 DP:状态只依赖前几个位置

3.1 斐波那契与爬楼梯

509. 斐波那契数 是最简单的状态递推:

1
2
3
4
5
6
7
8
9
10
11
12
def fib(n: int) -> int:
if n < 2:
return n

prev2 = 0
prev1 = 1

for _ in range(2, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current

return prev1

这里原本可以使用 dp[i],但每次只依赖前两个状态,所以压缩成两个变量。空间压缩前要先理解完整状态依赖,不要为了省几个元素让代码语义变乱。

70. 爬楼梯 的递推形式一样:

1
2
3
4
5
6
7
8
9
10
11
12
def climb_stairs(n: int) -> int:
if n <= 2:
return n

prev2 = 1
prev1 = 2

for _ in range(3, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current

return prev1

公式相同不代表问题相同。斐波那契的状态是数列第 i 项,爬楼梯的状态是到达第 i 阶的方法数。

3.2 使用最小花费爬楼梯:先说清楚“到达”

746. 使用最小花费爬楼梯 中,踩上台阶 i 才支付 cost[i]。定义:

1
dp[i] 表示到达位置 i 的最小花费。

楼顶可以看作位置 n,到达它的最后一步来自 n - 1 或 n - 2:

1
2
3
4
5
6
7
8
9
10
11
def min_cost_climbing_stairs(cost: list[int]) -> int:
n = len(cost)
dp = [0] * (n + 1)

for i in range(2, n + 1):
dp[i] = min(
dp[i - 1] + cost[i - 1],
dp[i - 2] + cost[i - 2],
)

return dp[n]

dp[0] = dp[1] = 0,因为题目允许从下标 0 或 1 开始,还没有踩上任何需要付费的台阶。

一维 DP 最常见的两种状态含义:

  • dp[i] 表示处理完前 i 个位置的最优答案,答案通常在最后一格。
  • dp[i] 表示必须以位置 i 结尾的答案,最终答案可能是 max(dp)。

后面的最长递增子序列就是第二种。

4. 网格 DP:当前位置来自上方和左方

4.1 不同路径:先初始化第一行和第一列

62. 不同路径 中,机器人只能向右或向下。定义:

1
dp[row][col] 表示从左上角走到 (row, col) 的路径数。

进入当前位置的最后一步只能来自上方或左方:

1
2
3
4
5
6
7
8
def unique_paths(m: int, n: int) -> int:
dp = [[1] * n for _ in range(m)]

for row in range(1, m):
for col in range(1, n):
dp[row][col] = dp[row - 1][col] + dp[row][col - 1]

return dp[m - 1][n - 1]

第一行只能一直向右,第一列只能一直向下,所以没有障碍时它们都初始化为 1。

Python 二维数组不要写成:

1
dp = [[0] * n] * m  # 错误:所有行指向同一个列表

修改一行时,其他行也会一起变化。正确写法是列表推导式,每一行单独创建。

4.2 有障碍时,障碍格直接归零

63. 不同路径 II 增加障碍。可以使用一维滚动数组:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def unique_paths_with_obstacles(grid: list[list[int]]) -> int:
rows = len(grid)
cols = len(grid[0])
dp = [0] * cols
dp[0] = 1

for row in range(rows):
for col in range(cols):
if grid[row][col] == 1:
dp[col] = 0
elif col > 0:
dp[col] += dp[col - 1]

return dp[-1]

此时:

  • 更新前的 dp[col] 是从上方到达的路径数。
  • 当前行刚更新的 dp[col - 1] 是从左方到达的路径数。
  • 障碍位置必须设为 0,因为任何路径都不能经过这里。

64. 最小路径和 的状态形状相同,只是把“上方加左方的方案数”换成“上方和左方取较小值,再加当前格子值”。这说明二维表长得一样时,状态语义和聚合方式仍然可能不同。

5. 拆分与计数:枚举最后一部分

5.1 整数拆分:直接拆和继续拆都要比较

343. 整数拆分 要把整数 n 拆成至少两个正整数,使乘积最大。定义 dp[i] 为拆分 i 后能得到的最大乘积。

枚举第一部分 j 时,剩下的 i - j 有两种处理方式:

  • 不再拆,乘积是 j * (i - j)。
  • 继续拆,乘积是 j * dp[i - j]。
1
2
3
4
5
6
7
8
9
10
11
12
13
def integer_break(n: int) -> int:
dp = [0] * (n + 1)
dp[2] = 1

for total in range(3, n + 1):
for first in range(1, total):
dp[total] = max(
dp[total],
first * (total - first),
first * dp[total - first],
)

return dp[n]

最容易漏的是 first * (total - first)。dp[x] 强制要求继续拆分,而当前剩余部分也可能不拆更优。

5.2 不同二叉搜索树:根节点切开左右规模

96. 不同的二叉搜索树 只关心节点数,不关心具体值。定义 dp[n] 为 n 个不同节点能组成的 BST 数量。

若选第 root 个节点当根:

1
2
3
左子树有 root - 1 个节点
右子树有 n - root 个节点
组合数 = 左子树方案数 × 右子树方案数
1
2
3
4
5
6
7
8
9
10
11
def num_trees(n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1

for nodes in range(1, n + 1):
for root in range(1, nodes + 1):
left_size = root - 1
right_size = nodes - root
dp[nodes] += dp[left_size] * dp[right_size]

return dp[n]

dp[0] = 1 表示空子树有一种组合方式,但不表示存在一个值为空的实际节点。这个初值能让只有一侧子树的组合正确相乘。

6. 0-1 背包:每件物品最多选一次

普通 0-1 背包通常不是贪心问题。物品不能拆分时,眼前性价比最高的物品可能占掉容量,使后面无法组成更优组合;因此需要同时比较“选”和“不选”。

标准模型:

1
2
3
4
有 n 件物品,第 i 件重量为 weight[i],价值为 value[i]
背包容量为 capacity
每件物品最多使用一次
求不超过容量时的最大价值

6.1 二维状态:选或不选都来自上一行

定义:

1
dp[i][j] 表示只考虑前 i 件物品、容量上限为 j 时能得到的最大价值。

处理第 i 件物品时:

1
2
不选:dp[i - 1][j]
选择:dp[i - 1][j - weight] + value

容量不足时只能继承上一行;容量足够时才比较选与不选:

1
2
3
4
5
6
7
if j < weight:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(
dp[i - 1][j],
dp[i - 1][j - weight] + value,
)

选择来源仍然是上一行,这保证第 i 件物品不会在同一轮被重复选择。

下面用重量 [1, 3, 4]、价值 [15, 20, 30]、容量 4 逐格填写二维表。重点看蓝色“不选来源”和绿色“选择来源”怎样共同决定当前格。

0-1 背包:逐格比较选与不选重量 [1, 3, 4] · 价值 [15, 20, 30] · 容量 4
当前物品:初始化 当前容量:— 当前最优:0
不选当前物品—
选择当前物品—
写入当前格dp[0][0] = 0

表格最终得到 dp[3][4] = 35,对应选择重量 1、价值 15 和重量 3、价值 20 的两件物品。单独选择重量 4 的物品只有价值 30,所以“看起来最完整地装满容量”也不一定最优。

6.2 压缩成一维时,容量必须倒序

二维转移的当前行只依赖上一行,可以压缩为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def zero_one_knapsack(
weights: list[int],
values: list[int],
capacity: int,
) -> int:
dp = [0] * (capacity + 1)

for weight, value in zip(weights, values):
for current in range(capacity, weight - 1, -1):
dp[current] = max(
dp[current],
dp[current - weight] + value,
)

return dp[capacity]

容量从大到小,是为了让 dp[current - weight] 仍然表示“还没有使用当前物品”时的上一层状态。

如果容量从小到大:

1
2
for current in range(weight, capacity + 1):
dp[current] = max(dp[current], dp[current - weight] + value)

较小容量刚写入的结果会立刻被较大容量读取,同一件物品可能在一轮内反复使用,题型就变成了完全背包。

下面把同一维 dp 数组的原地更新过程拆开。先看正确的容量倒序:橙色是正在写入的 dp[j],蓝色是来源 dp[j - weight],绿色是本轮已经处理过的较大容量。切到“错误正序”后,红色来源表示它已经在本轮包含了当前物品。

一维滚动数组:遍历方向决定物品能用几次同一组物品 · 容量 4
当前物品:初始化 遍历方向:4 → 1 当前容量:—
本轮容量顺序
原值—
选择当前物品—
写回—

这个对照的关键不是“倒序是一条需要背的规则”,而是看来源属于哪一层:

1
2
倒序:dp[j - weight] 还没有在本轮更新 → 读取上一层 → 当前物品最多一次
正序:dp[j - weight] 可能刚在本轮更新 → 读取当前层 → 当前物品可以重复

6.3 分割等和子集:背包能否恰好装满

416. 分割等和子集 要把数组分成和相等的两部分。若总和为 total,问题等价于:能否从每个数字最多选一次,组成 total // 2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def can_partition(nums: list[int]) -> bool:
total = sum(nums)

if total % 2 == 1:
return False

target = total // 2
dp = [False] * (target + 1)
dp[0] = True

for num in nums:
for current in range(target, num - 1, -1):
dp[current] = dp[current] or dp[current - num]

return dp[target]

这里 dp[current] 表示能否从已经处理的数字中选出一些,使总和恰好等于 current。dp[0] = True 表示空集合可以组成 0。

1049. 最后一块石头的重量 II 也是把石头分成两组,让两组重量尽量接近。背包尽量装到 total // 2,若能装到的最大重量为 best,最终差值就是:

1
total - 2 * best

6.4 目标和:从可行性变成方案计数

494. 目标和 给每个非负整数添加正号或负号。设添加正号的数字和为 positive,添加负号的数字和为 negative:

1
2
3
positive - negative = target
positive + negative = total
positive = (total + target) / 2

问题转化为:从数组中选一些数字,使和为 bag,一共有多少种选法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def find_target_sum_ways(nums: list[int], target: int) -> int:
total = sum(nums)

if abs(target) > total or (total + target) % 2 == 1:
return 0

bag = (total + target) // 2
dp = [0] * (bag + 1)
dp[0] = 1

for num in nums:
for current in range(bag, num - 1, -1):
dp[current] += dp[current - num]

return dp[bag]

计数题中 dp[0] = 1 非常关键。相同数值出现在不同下标时,仍然是不同的选择对象。数字 0 也会被正确处理:处理一个 0 时,dp[current] += dp[current],所有已有方案数翻倍,对应给这个 0 添加正号或负号。

474. 一和零 则是二维容量的 0-1 背包:每个字符串消耗若干个 0 和若干个 1,两个容量都必须倒序遍历。

7. 完全背包:物品可以重复使用

完全背包与 0-1 背包的状态公式很像,关键区别是容量正序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def complete_knapsack(
weights: list[int],
values: list[int],
capacity: int,
) -> int:
dp = [0] * (capacity + 1)

for weight, value in zip(weights, values):
for current in range(weight, capacity + 1):
dp[current] = max(
dp[current],
dp[current - weight] + value,
)

return dp[capacity]

正序让当前物品刚更新出的较小容量状态,可以继续参与更大容量的计算,因此同一物品能重复使用。

7.1 零钱兑换 II:求组合数,硬币放外层

518. 零钱兑换 II 求组成金额的硬币组合数。1 + 2 和 2 + 1 是同一种组合,所以硬币放外层,保证每组硬币只按固定顺序生成。

1
2
3
4
5
6
7
8
9
def change(amount: int, coins: list[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1

for coin in coins:
for current in range(coin, amount + 1):
dp[current] += dp[current - coin]

return dp[amount]

7.2 组合总和 IV:题名叫组合,实际求排列数

377. 组合总和 IV 中不同选择顺序要分别统计。例如 [1, 2] 和 [2, 1] 是两种答案,所以先遍历容量,再遍历数字:

1
2
3
4
5
6
7
8
9
10
def combination_sum4(nums: list[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1

for current in range(1, target + 1):
for num in nums:
if current >= num:
dp[current] += dp[current - num]

return dp[target]

两道题的递推式都是:

1
dp[current] += dp[current - item]

但循环顺序决定了是否区分排列顺序:

目标 外层循环 内层循环
组合数 物品 容量正序
排列数 容量正序 物品

这条“组合与排列”的结论主要用于计数题。最大值和最小值问题仍然要先分析状态依赖,不要机械套表。

7.3 零钱兑换:最少硬币要用无穷大初始化

322. 零钱兑换 求凑成金额的最少硬币数:

1
2
3
4
5
6
7
8
9
10
11
12
def coin_change(coins: list[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0

for coin in coins:
for current in range(coin, amount + 1):
dp[current] = min(
dp[current],
dp[current - coin] + 1,
)

return -1 if dp[amount] == float('inf') else dp[amount]

如果把所有位置初始化为 0,min 会永远保留这个并不存在的 0 个硬币方案。最小值问题常用 inf 表示尚不可达。

279. 完全平方数 可以把 1, 4, 9, ... 看成可无限使用的硬币,转移和零钱兑换相同。

8. 多重背包与分组背包:限制使用次数和选择范围

8.1 多重背包:每件物品最多使用若干次

多重背包给每件物品一个数量上限 count。直接做法是枚举当前物品使用几件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def multiple_knapsack(
weights: list[int],
values: list[int],
counts: list[int],
capacity: int,
) -> int:
dp = [0] * (capacity + 1)

for weight, value, count in zip(weights, values, counts):
for current in range(capacity, -1, -1):
max_count = min(count, current // weight)

for used in range(1, max_count + 1):
dp[current] = max(
dp[current],
dp[current - used * weight] + used * value,
)

return dp[capacity]

容量倒序保证读取的是处理当前物品之前的较小容量状态。但直接枚举 used 时,一件物品最多有 count 种取法;数量上限很大时,这一层循环会成为主要开销。

二进制分组:把多件相同物品打包成虚拟物品

二进制分组(也叫二进制拆分)的想法是:不再逐个枚举“使用 0 件、1 件、2 件……”,而是把若干件相同物品捆成一组,并把每组看成一件只能选择一次的 0-1 物品。

原物品的重量是 weight、价值是 value。把 amount 件捆成一组后,这件虚拟物品就是:

1
2
虚拟重量 = amount * weight
虚拟价值 = amount * value

每个虚拟物品最多选择一次,因此可以直接套用 0-1 背包的容量倒序更新。问题只剩下:组的大小应该怎样设计,才能表示从 0 到 count 的所有使用数量?

答案是依次取 1, 2, 4, ...,最后不足下一个二次幂的部分作为一组。以最多 13 件为例:

1
13 = 1 + 2 + 4 + 6

这里不是在求 13 的普通二进制表示。普通二进制表示 13 = 1 + 4 + 8 只能说明怎样凑出 13;多重背包要求这些组的不同子集能够表示使用 0..13 件的每一种情况。

1, 2, 4, 6 的覆盖过程是:

已生成的组 可以表示的使用数量
1 0..1
1, 2 0..3
1, 2, 4 0..7
1, 2, 4, 6 0..13

前三组已经能够表示 0..7。最后一组大小为 6:

  • 不选最后一组,仍然表示 0..7。
  • 选择最后一组,再搭配前三组,可以表示 6..13。
  • 两个范围合起来覆盖 0..13,没有缺口。

更一般地说,假设已有分组能够连续表示 0..S,那么下一组只要不超过 S + 1,就能把连续范围扩展到 0..S + group。每次取 1, 2, 4, ...,正好以最快速度扩大这个范围;最后的余数不会超过下一个二次幂,因此仍然不会产生缺口。

假设某种物品的重量为 2、价值为 3、最多有 13 件,拆分后得到四件虚拟物品:

组内原物品数量 虚拟重量 虚拟价值
1 2 3
2 4 6
4 8 12
6 12 18

例如选择大小为 1、4、6 的三组,就表示使用了 11 件原物品,总重量为 22,总价值为 33。因为每组只能选择一次,最多只能使用 1 + 2 + 4 + 6 = 13 件,不会超过原来的数量上限。

代码可以写成:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def multiple_knapsack_binary(
weights: list[int],
values: list[int],
counts: list[int],
capacity: int,
) -> int:
dp = [0] * (capacity + 1)

for weight, value, count in zip(weights, values, counts):
# 容量最多只能装下 capacity // weight 件,多余库存无需拆分。
remaining = min(count, capacity // weight)
group = 1

# 依次生成 1、2、4……件的组,把最后余数留作一组。
while group < remaining:
bundle_weight = group * weight
bundle_value = group * value

# 每个组是一件 0-1 物品,所以容量必须倒序。
for current in range(capacity, bundle_weight - 1, -1):
dp[current] = max(
dp[current],
dp[current - bundle_weight] + bundle_value,
)

remaining -= group
group *= 2

if remaining > 0:
bundle_weight = remaining * weight
bundle_value = remaining * value

for current in range(capacity, bundle_weight - 1, -1):
dp[current] = max(
dp[current],
dp[current - bundle_weight] + bundle_value,
)

return dp[capacity]

以 count = 13 为例,循环依次取出 1、2、4,此时 remaining = 6;因为下一组 8 已经大于剩余数量,最后单独处理 6,于是得到 1、2、4、6。

为什么这样做更快

设背包容量为 C,第 i 件物品在容量限制下实际最多能使用 m_i 次:

  • 直接枚举件数,需要大约 O(C * sum(m_i)) 的时间;若统一把数量上限记为 M,最坏可写成 O(n * C * M)。
  • 二进制分组把每种物品拆成 O(log(m_i + 1)) 个虚拟物品,时间降为 O(C * sum(log(m_i + 1))),通常记作 O(n * C * log M)。
  • 两种写法都只使用一个一维数组,额外空间都是 O(C)。

二进制分组的优势不只有复杂度:

  1. 数量上限越大,减少的枚举次数越明显。
  2. 拆完以后只需要复用熟悉的 0-1 背包模板,不必在每个状态中再枚举使用件数。
  3. 每组最多选择一次,而且所有组的数量之和等于上限,数量约束会自然得到保证。
  4. 相比单调队列优化,它更容易实现、调试和在面试中解释。

它也不是任何情况下都最优:如果 count >= capacity // weight,数量限制实际上不会生效,这种物品可以直接按完全背包正序更新;当容量和数量都非常大、题目又严格卡时间时,才需要进一步考虑 O(n * C) 的单调队列优化。

单调队列优化:把枚举件数变成滑动窗口最大值

如果还不熟悉单调队列,可以先复习栈与队列笔记中的滑动窗口最大值。那里解决的是“窗口每移动一步,怎样快速得到窗口最大值”;多重背包优化做的事情,就是先把状态转移改写成同一种问题。

先固定一种重量为 weight、价值为 value、最多使用 count 次的物品。处理它之前的数组记为 previous,处理之后的数组仍记为 dp。直接转移是:

1
2
3
4
5
dp[current] = max(
previous[current - used * weight] + used * value
)

其中 0 <= used <= count,且 used * weight <= current。

慢的原因是:每个 current 都要重新枚举一遍 used。想去掉这一层枚举,需要先观察哪些容量之间会发生转移。

第一步:按照容量除以重量的余数分组

每次选择当前物品,容量只会增加 weight,因此能够互相转移的容量,对 weight 的余数一定相同。

例如 weight = 3,容量会被拆成三条互不影响的序列:

1
2
3
余数 0:0, 3, 6, 9, 12, ...
余数 1:1, 4, 7, 10, 13, ...
余数 2:2, 5, 8, 11, 14, ...

对于某个固定余数 remainder,把这条序列中的容量写成:

1
current = remainder + step * weight

这里的 step 是容量在当前余数序列中的位置,不是使用了几件物品。

以 weight = 3、value = 4、count = 2 为例。在余数为 1 的序列中计算容量 10,也就是 step = 3 时,合法来源只有:

使用当前物品数量 上一层来源 候选价值
0 previous[10] previous[10]
1 previous[7] previous[7] + 4
2 previous[4] previous[4] + 8

到了容量 13,候选来源变为 previous[13]、previous[10]、previous[7]。来源沿着同一余数序列向右滑动,而且窗口始终只保留最近 count + 1 个位置,这已经很像滑动窗口最大值。

第二步:把转移式整理成窗口最大值

令 source_step 表示来源容量在同一余数序列中的位置,那么:

1
used = step - source_step

代入原转移:

1
2
3
4
5
dp[remainder + step * weight]
= max(
previous[remainder + source_step * weight]
+ (step - source_step) * value
)

把只与当前 step 有关的部分提到最大值外面:

1
2
3
4
5
6
dp[remainder + step * weight]
= step * value
+ max(
previous[remainder + source_step * weight]
- source_step * value
)

其中来源位置必须满足:

1
step - count <= source_step <= step

因此,当 step 依次增加时,需要维护的就是一个长度最多为 count + 1 的滑动窗口。窗口里的候选分数是:

1
2
3
score(source_step)
= previous[remainder + source_step * weight]
- source_step * value

最大的 score 永远放在队首,就能在 O(1) 时间得到当前状态的最优来源。

第三步:队列怎样维护候选来源

队列中保存 (source_step, score),并让 score 从队首到队尾单调递减。每来到一个新的 step,依次做三件事:

  1. 如果队首的 source_step < step - count,说明使用数量已经超过上限,把队首弹出。
  2. 当前候选的 score 如果大于等于队尾,就把队尾弹出。旧候选分数不更大、位置还更靠左,以后不可能优于当前候选。
  3. 当前候选入队;此时队首就是当前窗口的最大分数。

下面只跟踪 weight = 3、value = 4、count = 2 这件物品,并专门观察余数为 1 的容量序列 1、4、7、10、13。previous 表示处理当前物品之前已经冻结的上一层结果;其他两个余数序列的处理方式完全相同。

多重背包单调队列:把来源变成滑动窗口 w = 3 · v = 4 · count = 2 · 观察 remainder = 1
动作: 当前位置: 合法来源窗口:
按 current % weight 分组 score = previous[current] - step * value front < step-count:popleft() tail.score <= score:pop() queue.append((step, score)) dp[current] = step*value + queue[0].score
余数 1 序列:每张卡是一种“从上一层出发”的候选
单调队列:队首 → 队尾
已经写回的状态

完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from collections import deque


def multiple_knapsack_monotonic(
weights: list[int],
values: list[int],
counts: list[int],
capacity: int,
) -> int:
dp = [0] * (capacity + 1)

for weight, value, count in zip(weights, values, counts):
# 所有候选都必须来自处理当前物品之前的同一层。
previous = dp[:]
effective_count = min(count, capacity // weight)

if effective_count == 0:
continue

# 同一个余数序列中的容量才可能互相转移。
for remainder in range(min(weight, capacity + 1)):
queue = deque()
max_step = (capacity - remainder) // weight

for step in range(max_step + 1):
min_source_step = step - effective_count

# 队首已经离开合法窗口。
while queue and queue[0][0] < min_source_step:
queue.popleft()

current = remainder + step * weight
current_score = previous[current] - step * value

# 保持分数从队首到队尾单调递减。
while queue and queue[-1][1] <= current_score:
queue.pop()

queue.append((step, current_score))
best_score = queue[0][1]
dp[current] = step * value + best_score

return dp[capacity]

这里有两个关键点:

  • 必须从 previous 计算候选分数。如果直接读取正在更新的 dp,当前物品就可能越过数量上限被重复使用。
  • 队列里比较的不是原始 previous[current],而是减去 step * value 后的 score。只有经过这个变换,不同使用数量的候选才可以放进同一个窗口比较。

每个来源位置最多入队一次、从队首或队尾出队一次,因此每个余数序列都是线性扫描。所有余数序列合起来只覆盖容量 0..capacity 一遍,所以处理一种物品是 O(C),处理 n 种物品就是 O(n * C)。

三种写法可以这样选择:

做法 时间复杂度 优点 适用情况
直接枚举使用件数 O(n * C * M) 最直观 数量上限很小
二进制分组 O(n * C * log M) 复用 0-1 背包,容易实现 大多数多重背包题
单调队列优化 O(n * C) 不受数量上限 M 的线性影响 数据规模大、严格卡时间

复习时不需要把公式一次背下来。先记住这条思路链:

1
2
3
4
同一重量只在相同余数的容量之间转移
→ 每条余数序列上,合法来源是一个固定长度窗口
→ 变换候选分数后,需要反复求窗口最大值
→ 用单调队列把枚举件数降为线性扫描

8.2 分组背包:每组最多选一个选项

分组背包把物品分成若干组,每组最多选一个。稳妥写法是每处理一组就保存上一层:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def group_knapsack(
groups: list[list[tuple[int, int]]],
capacity: int,
) -> int:
dp = [0] * (capacity + 1)

for group in groups:
previous = dp[:]

for current in range(capacity + 1):
for weight, value in group:
if current >= weight:
dp[current] = max(
dp[current],
previous[current - weight] + value,
)

return dp[capacity]

关键是所有组内选项都从 previous 转移。如果把组内物品逐件当普通 0-1 背包处理,就可能从同一组选出多个选项。

背包类型可以用一张表区分:

类型 每件物品限制 一维容量方向 关键点
0-1 背包 最多一次 倒序 读取上一层,防止重复使用
完全背包 无限次 正序 允许读取本轮更新结果
多重背包 最多 count 次 倒序枚举、二进制分组,或按余数分组维护单调队列 防止超过数量上限
分组背包 每组最多选一个 每组读取同一份上一层 组内选项不能互相转移

9. 打家劫舍:当前选择会限制相邻状态

9.1 线性房屋:偷当前房就不能偷前一间

198. 打家劫舍 定义:

1
dp[i] 表示考虑下标 0..i 的房屋时,能偷到的最大金额。

最后一间有两种选择:

1
2
不偷 i:dp[i - 1]
偷 i:dp[i - 2] + nums[i]

可以压缩成两个变量:

1
2
3
4
5
6
7
8
9
def rob(nums: list[int]) -> int:
prev2 = 0
prev1 = 0

for money in nums:
current = max(prev1, prev2 + money)
prev2, prev1 = prev1, current

return prev1

prev1 是已经处理到前一间的最优答案,不代表一定偷了前一间。因此“不偷当前房”直接继承 prev1。

9.2 环形房屋:首尾不能同时出现

213. 打家劫舍 II 首尾相邻。一个合法方案一定属于下面至少一种情况:

  • 不考虑最后一间,只处理 nums[:-1]。
  • 不考虑第一间,只处理 nums[1:]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def rob_circle(nums: list[int]) -> int:
if len(nums) == 1:
return nums[0]

def rob_line(houses: list[int]) -> int:
prev2 = 0
prev1 = 0

for money in houses:
prev2, prev1 = prev1, max(prev1, prev2 + money)

return prev1

return max(rob_line(nums[:-1]), rob_line(nums[1:]))

9.3 树形房屋:每个节点返回偷与不偷

337. 打家劫舍 III 把房屋放在二叉树上,父子节点不能同时偷。后序遍历每个节点,返回两个状态:

1
2
skip:不偷当前节点时的最大金额
take:偷当前节点时的最大金额
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def rob_tree(root: TreeNode | None) -> int:
def dfs(node: TreeNode | None) -> tuple[int, int]:
if node is None:
return 0, 0

left_skip, left_take = dfs(node.left)
right_skip, right_take = dfs(node.right)

take = node.val + left_skip + right_skip
skip = max(left_skip, left_take) + max(right_skip, right_take)

return skip, take

return max(dfs(root))

不偷当前节点时,孩子可以偷也可以不偷,所以左右孩子都取各自两个状态的最大值;不要误写成“不偷父节点就必须偷孩子”。

10. 股票问题:统一成持有与不持有状态

股票题不要为每道题单独背一份代码。先统一两个基础状态:

1
2
hold:今天结束时,持有一只股票的最大利润
cash:今天结束时,不持有股票的最大利润

状态表示一天结束后的最优结果,不代表今天一定发生了买入或卖出。

10.1 一次交易和无限次交易,只差买入来源

121. 买卖股票的最佳时机 最多交易一次:

先保留完整的二维 DP 表:

1
2
dp[day][0]:第 day 天结束时,持有股票的最大利润
dp[day][1]:第 day 天结束时,不持有股票的最大利润
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def max_profit_once(prices: list[int]) -> int:
if not prices:
return 0

days = len(prices)
dp = [[0, 0] for _ in range(days)]

# 第 0 天:可以买入,或者什么也不做。
dp[0][0] = -prices[0]
dp[0][1] = 0

for day in range(1, days):
price = prices[day]

# 今天持股:昨天已经持股,或者今天进行唯一一次买入。
dp[day][0] = max(
dp[day - 1][0],
-price,
)

# 今天不持股:昨天就不持股,或者今天卖出。
dp[day][1] = max(
dp[day - 1][1],
dp[day - 1][0] + price,
)

return dp[-1][1]

这两个转移可以直接按“今天做什么”理解:

  • 今天结束后持股:要么延续昨天的持股状态,要么今天第一次买入。
  • 今天结束后不持股:要么昨天就没有股票,要么把昨天持有的股票在今天卖出。

因为整道题最多只能完成一次交易,所以买入时不能使用之前卖出赚到的利润,买入来源只能是 0 - price,也就是 -price。理解二维表以后,再把上一天的两个状态压缩成 hold 和 cash 即可。

122. 买卖股票的最佳时机 II 允许反复交易,卖出后的利润可以用于下一次买入:

1
2
3
4
5
6
7
8
9
10
11
def max_profit_unlimited(prices: list[int]) -> int:
hold = float('-inf')
cash = 0

for price in prices:
previous_hold = hold
previous_cash = cash
hold = max(previous_hold, previous_cash - price)
cash = max(previous_cash, previous_hold + price)

return cash

两个模板的核心区别:

1
2
一次交易买入:-price
无限交易买入:previous_cash - price

10.2 冷冻期:卖出后的次日不能立刻买入

309. 买卖股票的最佳时机含冷冻期 可以维护三个状态:

1
2
3
dp[day][0]:第 day 天结束时持有股票
dp[day][1]:第 day 天结束时刚刚卖出股票
dp[day][2]:第 day 天结束时不持股,并且今天没有卖出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def max_profit_with_cooldown(prices: list[int]) -> int:
if not prices:
return 0

days = len(prices)
dp = [[0, 0, 0] for _ in range(days)]

# 第 0 天可以买入或休息,但不可能完成卖出。
dp[0][0] = -prices[0]
dp[0][1] = float('-inf')
dp[0][2] = 0

for day in range(1, days):
price = prices[day]

# 今天持股:延续昨天的持股,或者从昨天的休息状态买入。
dp[day][0] = max(
dp[day - 1][0],
dp[day - 1][2] - price,
)

# 今天刚卖出:只能卖掉昨天持有的股票。
dp[day][1] = dp[day - 1][0] + price

# 今天休息:昨天已经休息,或者昨天刚卖出后进入冷冻期。
dp[day][2] = max(
dp[day - 1][2],
dp[day - 1][1],
)

# 最后必须处于不持股状态,利润才真正落袋。
return max(dp[-1][1], dp[-1][2])

冷冻期体现在买入转移里:dp[day][0] 只能从昨天的持股状态或休息状态得到,不能从昨天刚卖出的 dp[day - 1][1] 买入。昨天卖出后,今天必须先进入休息状态;最早只能在明天再次买入。

10.3 最多两次交易:把五个阶段写成状态

123. 买卖股票的最佳时机 III 最多完成两次交易。一笔交易由一次买入和一次卖出组成,可以把每天结束后的进度分成五个状态:

1
2
3
4
5
dp[day][0]:还没有进行任何操作
dp[day][1]:完成第一次买入,当前持股
dp[day][2]:完成第一次卖出,当前不持股
dp[day][3]:完成第二次买入,当前持股
dp[day][4]:完成第二次卖出,当前不持股
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def max_profit_two_transactions(prices: list[int]) -> int:
if not prices:
return 0

days = len(prices)
negative_infinity = float('-inf')
dp = [[negative_infinity] * 5 for _ in range(days)]

# 第 0 天只能什么也不做,或者完成第一次买入。
dp[0][0] = 0
dp[0][1] = -prices[0]

for day in range(1, days):
price = prices[day]

dp[day][0] = dp[day - 1][0]
dp[day][1] = max(
dp[day - 1][1],
dp[day - 1][0] - price,
)
dp[day][2] = max(
dp[day - 1][2],
dp[day - 1][1] + price,
)
dp[day][3] = max(
dp[day - 1][3],
dp[day - 1][2] - price,
)
dp[day][4] = max(
dp[day - 1][4],
dp[day - 1][3] + price,
)

# 题目要求最多两次,可以不交易、完成一次或完成两次。
return max(dp[-1][0], dp[-1][2], dp[-1][4])

每个状态都有两种来源:昨天已经处于这个状态,今天什么也不做;或者今天完成进入该状态所需的买入或卖出。使用 -inf 表示第 0 天不可能完成的操作,可以防止非法状态参与后面的最大值比较。

10.4 最多 K 次交易:展开成 2K + 1 个动作状态

188. 买卖股票的最佳时机 IV 是上一题的推广。把“第几次交易”和“是否持股”合并成一个状态编号,就可以继续使用二维数组:

1
2
3
4
5
6
7
dp[day][0]:没有进行任何操作
dp[day][1]:完成第 1 次买入,当前持股
dp[day][2]:完成第 1 次卖出,当前不持股
dp[day][3]:完成第 2 次买入,当前持股
dp[day][4]:完成第 2 次卖出,当前不持股
...
dp[day][2 * k]:完成第 k 次卖出,当前不持股

状态 0 加上每笔交易的买入和卖出两个状态,一共需要 2 * k + 1 个状态。奇数下标表示买入后持股,偶数下标表示卖出后不持股。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def max_profit_k_transactions(k: int, prices: list[int]) -> int:
if not prices or k == 0:
return 0

days = len(prices)
states = 2 * k + 1
negative_infinity = float('-inf')
dp = [
[negative_infinity] * states
for _ in range(days)
]

# 第 0 天只能什么也不做,或者完成第 1 次买入。
dp[0][0] = 0
dp[0][1] = -prices[0]

for day in range(1, days):
price = prices[day]
dp[day][0] = 0

for transaction in range(1, k + 1):
buy_state = 2 * transaction - 1
sell_state = 2 * transaction

# 第 transaction 次买入:继续持股,或者从上一次卖出状态买入。
dp[day][buy_state] = max(
dp[day - 1][buy_state],
dp[day - 1][buy_state - 1] - price,
)

# 第 transaction 次卖出:继续不持股,或者今天卖出。
dp[day][sell_state] = max(
dp[day - 1][sell_state],
dp[day - 1][sell_state - 1] + price,
)

# 最多交易 k 次,因此答案可能停在任意一个偶数状态。
return max(
dp[-1][state]
for state in range(0, states, 2)
)

当 k = 2 时,一行正好是 [无操作, 第一次买入, 第一次卖出, 第二次买入, 第二次卖出],也就是上一题的五状态 DP。代码只是把固定的五个状态推广成 2 * k + 1 个状态。

这段代码的时间复杂度是 O(n * k),空间复杂度也是 O(n * k)。理解完整状态后,可以只保存前一天,把空间压缩到 O(k)。

10.5 含手续费:在完成交易时扣一次费用

714. 买卖股票的最佳时机含手续费 允许完成任意多次交易,只是在每笔交易中需要支付一次手续费。仍然使用持股和不持股两个状态:

1
2
dp[day][0]:第 day 天结束时持股的最大利润
dp[day][1]:第 day 天结束时不持股的最大利润
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def max_profit_with_fee(prices: list[int], fee: int) -> int:
if not prices:
return 0

days = len(prices)
dp = [[0, 0] for _ in range(days)]

dp[0][0] = -prices[0]
dp[0][1] = 0

for day in range(1, days):
price = prices[day]

# 今天持股:继续持有,或者用昨天的不持股利润买入。
dp[day][0] = max(
dp[day - 1][0],
dp[day - 1][1] - price,
)

# 今天不持股:继续不持股,或者今天卖出并支付手续费。
dp[day][1] = max(
dp[day - 1][1],
dp[day - 1][0] + price - fee,
)

return dp[-1][1]

手续费放在买入或卖出时扣都可以,但一笔交易只能扣一次。这里统一在卖出时减去 fee,状态含义最直观。

这几道题的变化可以归纳为:交易次数有限时增加买卖动作状态;存在冷冻期时限制买入来源;存在手续费时修改卖出收益。完整二维表理解清楚以后,再根据“当前状态只依赖前一天”做空间压缩。

11. 子序列 DP:先看状态是一维、双前缀还是区间

子序列问题最容易混,因为题目都在处理数组或字符串,但状态形状不同:

状态形状 典型含义 代表题
dp[i] 必须以位置 i 结尾 最长递增子序列、最大子数组和
dp[i][j] 两个序列前 i、前 j 个元素的答案 最长公共子序列、编辑距离
dp[i][j] 闭区间 [i, j] 的答案 回文子串、最长回文子序列

11.1 最长递增子序列:答案是 max(dp)

300. 最长递增子序列 定义:

1
dp[i] 表示必须以 nums[i] 结尾的最长严格递增子序列长度。
1
2
3
4
5
6
7
8
9
10
11
12
def length_of_lis(nums: list[int]) -> int:
if not nums:
return 0

dp = [1] * len(nums)

for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)

return max(dp)

因为最长序列不一定以最后一个元素结尾,所以答案是 max(dp),不是 dp[-1]。

674. 最长连续递增序列 要求连续,dp[i] 只需要看 dp[i - 1];300 不要求连续,所以要枚举所有 j < i。看到“连续”与否,要马上改变依赖范围。

11.2 最长公共子序列:相等看左上,不等看上方和左方

1143. 最长公共子序列 定义:

1
dp[i][j] 表示 text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
def longest_common_subsequence(text1: str, text2: str) -> int:
rows = len(text1) + 1
cols = len(text2) + 1
dp = [[0] * cols for _ in range(rows)]

for i in range(1, rows):
for j in range(1, cols):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

return dp[-1][-1]

下面用 text1 = "abcde"、text2 = "ace" 逐格填写 DP 表。先观察第 0 行和第 0 列为什么都是 0,再重点比较字符相等与不相等时的来源。

LCS:逐格填写二维 DP 表 text1 = "abcde" · text2 = "ace"
当前动作: 比较位置: 当前结果:
行:text1 前缀列:text2 前缀
当前格 依赖来源 采用的来源

1035. 不相交的线 与 LCS 完全同构:相同数字连线且不能相交,等价于保持两个数组中的相对顺序。

连续版本 718. 最长重复子数组 在元素不等时必须归零,因为公共连续片段不能跳过中间元素;LCS 不要求连续,所以不等时可以丢掉其中一个末尾字符继续比较。

11.3 编辑距离:增、删、改对应三个来源

72. 编辑距离 定义:

1
dp[i][j] 表示 word1 前 i 个字符变成 word2 前 j 个字符的最少操作数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def min_distance(word1: str, word2: str) -> int:
rows = len(word1) + 1
cols = len(word2) + 1
dp = [[0] * cols for _ in range(rows)]

for i in range(rows):
dp[i][0] = i

for j in range(cols):
dp[0][j] = j

for i in range(1, rows):
for j in range(1, cols):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(
dp[i - 1][j], # 删除 word1 的末尾字符
dp[i][j - 1], # 插入 word2 的末尾字符
dp[i - 1][j - 1], # 替换末尾字符
)

return dp[-1][-1]

下面用 word1 = "horse"、word2 = "ros" 逐格计算。表格中的上方、左方和左上方,分别对应删除、插入和替换;字符相等时则直接继承左上方,不增加操作次数。

编辑距离:逐格选择最少操作 word1 = "horse" · word2 = "ros"
当前动作: 比较位置: 当前结果:
行:word1 前缀列:word2 前缀
当前格 上方:删除 左方:插入 左上:匹配/替换 采用来源

两个前缀 DP 可以用来源快速区分:

问题 元素不相等时怎么做
LCS max(上方, 左方)
最长公共连续子数组 归零
编辑距离 1 + min(上方, 左方, 左上)
不同子序列计数 只能丢弃源串末尾,读取上方

11.4 回文区间:i 倒序,j 正序

647. 回文子串 定义 dp[i][j] 表示闭区间 s[i:j+1] 是否为回文串:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def count_substrings(s: str) -> int:
n = len(s)
dp = [[False] * n for _ in range(n)]
count = 0

for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (
j - i <= 1 or dp[i + 1][j - 1]
):
dp[i][j] = True
count += 1

return count

当前区间依赖更靠里的 dp[i + 1][j - 1],所以 i 必须倒序,j 从 i 向右遍历。

516. 最长回文子序列 同样使用区间状态,但聚合方式不同。单字符区间先初始化为 1,再从短区间推向长区间:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def longest_palindrome_subseq(s: str) -> int:
n = len(s)

if n == 0:
return 0

dp = [[0] * n for _ in range(n)]

for i in range(n):
dp[i][i] = 1

for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

return dp[0][n - 1]

这里 i 倒序、j 从 i + 1 正序,保证 dp[i + 1][j - 1]、dp[i + 1][j] 和 dp[i][j - 1] 都已经计算。

回文子串要求连续,保存真假;回文子序列可以跳过字符,保存最大长度。

12. 遍历顺序与常见错误

12.1 背包循环方向速查

问题 外层 内层 为什么
0-1 背包最大值/可行性/计数 物品 容量倒序 每件物品最多使用一次
完全背包最大值/最小值 物品 容量正序 当前物品可以重复使用
完全背包组合数 物品 容量正序 不区分物品排列顺序
完全背包排列数 容量正序 物品 不同选择顺序分别统计

12.2 状态定义决定答案位置

1
2
3
dp[i] = 处理前 i 个元素的最优答案  → 通常返回最后一格
dp[i] = 必须以 i 结尾的最优答案 → 通常返回 max(dp)
dp[i][j] = 两个完整前缀的答案 → 通常返回 dp[m][n]

不要看到一维数组就默认返回 dp[-1]。

12.3 滚动数组会隐藏依赖方向

二维压缩成一维后,代码更短,但“上一行”和“当前行”不再显式出现。第一次整理一道题时,先写清二维状态来源,再判断:

  • 当前格只依赖上一行吗?
  • 需要保留哪些方向的旧值?
  • 正序会不会读到本轮刚更新的状态?

这些问题决定能否压缩以及应该怎样遍历。

12.4 一份实用的 DP 检查清单

  1. 能否用一句话完整解释 dp 每个下标的含义?
  2. 当前状态的所有合法来源是否都列出来了?
  3. 初始化能否由状态定义直接解释?
  4. 不可达状态应该是 False、inf 还是 -inf?
  5. 当前循环顺序下,读取的状态已经计算了吗?
  6. 答案是最后一格还是整张表的最大值?
  7. 空数组、单元素、容量 0、目标 0、全负数是否正确?
  8. Python 二维数组是否误用了 [[...]] * rows?
  9. 多状态转移是否错误读取了当天刚更新的值?
  10. 用最小样例打印 DP 表时,每一格是否符合手算结果?

13. 复习总览

  • 动态规划把重复子问题的答案保存下来,按照依赖顺序从小状态推出大状态。
  • 五步法是:定义状态、写递推、做初始化、定遍历顺序、确定答案位置。
  • 状态定义必须是一句完整的话;公式、初始化和遍历方向都要服从这个定义。
  • 一维基础题常依赖前一两个位置;网格题常来自上方和左方。
  • 0-1 背包每件物品最多一次,一维容量倒序;完全背包可以重复使用,容量正序。
  • 计数组合时物品在外层;计数排列时容量在外层。
  • dp[0] = 1 在计数题中表示空方案,dp[0] = True 在可行性题中表示空集合可组成 0。
  • 多重背包限制每件数量,分组背包限制每组最多选一个,不能让组内选项互相转移。
  • 打家劫舍是在“偷与不偷”之间转移;树形版本让每个节点同时返回两个状态。
  • 股票题统一维护持有和不持有状态,限制次数、冷冻期、手续费只是修改状态或来源。
  • LIS 使用“以 i 结尾”的一维状态;LCS 和编辑距离使用两个前缀;回文题常使用区间状态。
  • 递推式决定遍历顺序。滚动数组只是空间优化,不应该掩盖原本的依赖关系。

动态规划最难的不是把模板背下来,而是把状态说清楚。复习时先问“这一格代表什么、它从哪里来”,再写循环;只要状态语义稳定,初始化、遍历顺序和答案位置就会自然连起来。

avatar
LittlePyx
小P的学习、研究、生活记录
Follow Me
公告
教育经历
本科:杭州电子科技大学
研究生:电子科技大学

研究方向
AI Agent 开发、计算成像、深度学习、光学

新增:代码随想录算法刷题笔记整理中,按题型与算法模板归纳。
目录
  1. 1. 怎么看动态规划题
  2. 2. DP 五步法:先定义,再递推
    1. 2.1 状态定义必须是一句话
    2. 2.2 初始化由问题类型决定
    3. 2.3 遍历顺序由依赖方向决定
  3. 3. 基础一维 DP:状态只依赖前几个位置
    1. 3.1 斐波那契与爬楼梯
    2. 3.2 使用最小花费爬楼梯:先说清楚“到达”
  4. 4. 网格 DP:当前位置来自上方和左方
    1. 4.1 不同路径:先初始化第一行和第一列
    2. 4.2 有障碍时,障碍格直接归零
  5. 5. 拆分与计数:枚举最后一部分
    1. 5.1 整数拆分:直接拆和继续拆都要比较
    2. 5.2 不同二叉搜索树:根节点切开左右规模
  6. 6. 0-1 背包:每件物品最多选一次
    1. 6.1 二维状态:选或不选都来自上一行
    2. 6.2 压缩成一维时,容量必须倒序
    3. 6.3 分割等和子集:背包能否恰好装满
    4. 6.4 目标和:从可行性变成方案计数
  7. 7. 完全背包:物品可以重复使用
    1. 7.1 零钱兑换 II:求组合数,硬币放外层
    2. 7.2 组合总和 IV:题名叫组合,实际求排列数
    3. 7.3 零钱兑换:最少硬币要用无穷大初始化
  8. 8. 多重背包与分组背包:限制使用次数和选择范围
    1. 8.1 多重背包:每件物品最多使用若干次
      1. 二进制分组:把多件相同物品打包成虚拟物品
      2. 为什么这样做更快
      3. 单调队列优化:把枚举件数变成滑动窗口最大值
        1. 第一步:按照容量除以重量的余数分组
        2. 第二步:把转移式整理成窗口最大值
        3. 第三步:队列怎样维护候选来源
    2. 8.2 分组背包:每组最多选一个选项
  9. 9. 打家劫舍:当前选择会限制相邻状态
    1. 9.1 线性房屋:偷当前房就不能偷前一间
    2. 9.2 环形房屋:首尾不能同时出现
    3. 9.3 树形房屋:每个节点返回偷与不偷
  10. 10. 股票问题:统一成持有与不持有状态
    1. 10.1 一次交易和无限次交易,只差买入来源
    2. 10.2 冷冻期:卖出后的次日不能立刻买入
    3. 10.3 最多两次交易:把五个阶段写成状态
    4. 10.4 最多 K 次交易:展开成 2K + 1 个动作状态
    5. 10.5 含手续费:在完成交易时扣一次费用
  11. 11. 子序列 DP:先看状态是一维、双前缀还是区间
    1. 11.1 最长递增子序列:答案是 max(dp)
    2. 11.2 最长公共子序列:相等看左上,不等看上方和左方
    3. 11.3 编辑距离:增、删、改对应三个来源
    4. 11.4 回文区间:i 倒序,j 正序
  12. 12. 遍历顺序与常见错误
    1. 12.1 背包循环方向速查
    2. 12.2 状态定义决定答案位置
    3. 12.3 滚动数组会隐藏依赖方向
    4. 12.4 一份实用的 DP 检查清单
  13. 13. 复习总览
最新文章
网站信息
文章数目 :
18
最后更新时间 :