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 | 从 i - 1 走 1 阶过来 |
所以:
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 | dp[i - 1] |
那么 i 要从小到大遍历。如果区间 DP 读取 dp[i + 1][j - 1],那么 i 通常要从大到小遍历。背包的一维压缩更依赖遍历方向:方向写错,题型会直接从 0-1 背包变成完全背包。
调试 DP 时,先用最小样例打印整张表:
1 | print(dp) |
逐格确认“这一格为什么是这个值”,比只检查最终答案有效得多。
3. 基础一维 DP:状态只依赖前几个位置
3.1 斐波那契与爬楼梯
509. 斐波那契数 是最简单的状态递推:
1 | def fib(n: int) -> int: |
这里原本可以使用 dp[i],但每次只依赖前两个状态,所以压缩成两个变量。空间压缩前要先理解完整状态依赖,不要为了省几个元素让代码语义变乱。
70. 爬楼梯 的递推形式一样:
1 | def climb_stairs(n: int) -> int: |
公式相同不代表问题相同。斐波那契的状态是数列第 i 项,爬楼梯的状态是到达第 i 阶的方法数。
3.2 使用最小花费爬楼梯:先说清楚“到达”
746. 使用最小花费爬楼梯 中,踩上台阶 i 才支付 cost[i]。定义:
1 | dp[i] 表示到达位置 i 的最小花费。 |
楼顶可以看作位置 n,到达它的最后一步来自 n - 1 或 n - 2:
1 | def min_cost_climbing_stairs(cost: list[int]) -> int: |
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 | def unique_paths(m: int, n: int) -> int: |
第一行只能一直向右,第一列只能一直向下,所以没有障碍时它们都初始化为 1。
Python 二维数组不要写成:
1 | dp = [[0] * n] * m # 错误:所有行指向同一个列表 |
修改一行时,其他行也会一起变化。正确写法是列表推导式,每一行单独创建。
4.2 有障碍时,障碍格直接归零
63. 不同路径 II 增加障碍。可以使用一维滚动数组:
1 | def unique_paths_with_obstacles(grid: list[list[int]]) -> int: |
此时:
- 更新前的
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 | def integer_break(n: int) -> int: |
最容易漏的是 first * (total - first)。dp[x] 强制要求继续拆分,而当前剩余部分也可能不拆更优。
5.2 不同二叉搜索树:根节点切开左右规模
96. 不同的二叉搜索树 只关心节点数,不关心具体值。定义 dp[n] 为 n 个不同节点能组成的 BST 数量。
若选第 root 个节点当根:
1 | 左子树有 root - 1 个节点 |
1 | def num_trees(n: int) -> int: |
dp[0] = 1 表示空子树有一种组合方式,但不表示存在一个值为空的实际节点。这个初值能让只有一侧子树的组合正确相乘。
6. 0-1 背包:每件物品最多选一次
普通 0-1 背包通常不是贪心问题。物品不能拆分时,眼前性价比最高的物品可能占掉容量,使后面无法组成更优组合;因此需要同时比较“选”和“不选”。
标准模型:
1 | 有 n 件物品,第 i 件重量为 weight[i],价值为 value[i] |
6.1 二维状态:选或不选都来自上一行
定义:
1 | dp[i][j] 表示只考虑前 i 件物品、容量上限为 j 时能得到的最大价值。 |
处理第 i 件物品时:
1 | 不选:dp[i - 1][j] |
容量不足时只能继承上一行;容量足够时才比较选与不选:
1 | if j < weight: |
选择来源仍然是上一行,这保证第 i 件物品不会在同一轮被重复选择。
下面用重量 [1, 3, 4]、价值 [15, 20, 30]、容量 4 逐格填写二维表。重点看蓝色“不选来源”和绿色“选择来源”怎样共同决定当前格。
——dp[0][0] = 0表格最终得到 dp[3][4] = 35,对应选择重量 1、价值 15 和重量 3、价值 20 的两件物品。单独选择重量 4 的物品只有价值 30,所以“看起来最完整地装满容量”也不一定最优。
6.2 压缩成一维时,容量必须倒序
二维转移的当前行只依赖上一行,可以压缩为:
1 | def zero_one_knapsack( |
容量从大到小,是为了让 dp[current - weight] 仍然表示“还没有使用当前物品”时的上一层状态。
如果容量从小到大:
1 | for current in range(weight, capacity + 1): |
较小容量刚写入的结果会立刻被较大容量读取,同一件物品可能在一轮内反复使用,题型就变成了完全背包。
下面把同一维 dp 数组的原地更新过程拆开。先看正确的容量倒序:橙色是正在写入的 dp[j],蓝色是来源 dp[j - weight],绿色是本轮已经处理过的较大容量。切到“错误正序”后,红色来源表示它已经在本轮包含了当前物品。
———这个对照的关键不是“倒序是一条需要背的规则”,而是看来源属于哪一层:
1 | 倒序:dp[j - weight] 还没有在本轮更新 → 读取上一层 → 当前物品最多一次 |
6.3 分割等和子集:背包能否恰好装满
416. 分割等和子集 要把数组分成和相等的两部分。若总和为 total,问题等价于:能否从每个数字最多选一次,组成 total // 2。
1 | def can_partition(nums: list[int]) -> bool: |
这里 dp[current] 表示能否从已经处理的数字中选出一些,使总和恰好等于 current。dp[0] = True 表示空集合可以组成 0。
1049. 最后一块石头的重量 II 也是把石头分成两组,让两组重量尽量接近。背包尽量装到 total // 2,若能装到的最大重量为 best,最终差值就是:
1 | total - 2 * best |
6.4 目标和:从可行性变成方案计数
494. 目标和 给每个非负整数添加正号或负号。设添加正号的数字和为 positive,添加负号的数字和为 negative:
1 | positive - negative = target |
问题转化为:从数组中选一些数字,使和为 bag,一共有多少种选法。
1 | def find_target_sum_ways(nums: list[int], target: int) -> int: |
计数题中 dp[0] = 1 非常关键。相同数值出现在不同下标时,仍然是不同的选择对象。数字 0 也会被正确处理:处理一个 0 时,dp[current] += dp[current],所有已有方案数翻倍,对应给这个 0 添加正号或负号。
474. 一和零 则是二维容量的 0-1 背包:每个字符串消耗若干个 0 和若干个 1,两个容量都必须倒序遍历。
7. 完全背包:物品可以重复使用
完全背包与 0-1 背包的状态公式很像,关键区别是容量正序:
1 | def complete_knapsack( |
正序让当前物品刚更新出的较小容量状态,可以继续参与更大容量的计算,因此同一物品能重复使用。
7.1 零钱兑换 II:求组合数,硬币放外层
518. 零钱兑换 II 求组成金额的硬币组合数。1 + 2 和 2 + 1 是同一种组合,所以硬币放外层,保证每组硬币只按固定顺序生成。
1 | def change(amount: int, coins: list[int]) -> int: |
7.2 组合总和 IV:题名叫组合,实际求排列数
377. 组合总和 IV 中不同选择顺序要分别统计。例如 [1, 2] 和 [2, 1] 是两种答案,所以先遍历容量,再遍历数字:
1 | def combination_sum4(nums: list[int], target: int) -> int: |
两道题的递推式都是:
1 | dp[current] += dp[current - item] |
但循环顺序决定了是否区分排列顺序:
| 目标 | 外层循环 | 内层循环 |
|---|---|---|
| 组合数 | 物品 | 容量正序 |
| 排列数 | 容量正序 | 物品 |
这条“组合与排列”的结论主要用于计数题。最大值和最小值问题仍然要先分析状态依赖,不要机械套表。
7.3 零钱兑换:最少硬币要用无穷大初始化
322. 零钱兑换 求凑成金额的最少硬币数:
1 | def coin_change(coins: list[int], amount: int) -> int: |
如果把所有位置初始化为 0,min 会永远保留这个并不存在的 0 个硬币方案。最小值问题常用 inf 表示尚不可达。
279. 完全平方数 可以把 1, 4, 9, ... 看成可无限使用的硬币,转移和零钱兑换相同。
8. 多重背包与分组背包:限制使用次数和选择范围
8.1 多重背包:每件物品最多使用若干次
多重背包给每件物品一个数量上限 count。直接做法是枚举当前物品使用几件:
1 | def multiple_knapsack( |
容量倒序保证读取的是处理当前物品之前的较小容量状态。但直接枚举 used 时,一件物品最多有 count 种取法;数量上限很大时,这一层循环会成为主要开销。
二进制分组:把多件相同物品打包成虚拟物品
二进制分组(也叫二进制拆分)的想法是:不再逐个枚举“使用 0 件、1 件、2 件……”,而是把若干件相同物品捆成一组,并把每组看成一件只能选择一次的 0-1 物品。
原物品的重量是 weight、价值是 value。把 amount 件捆成一组后,这件虚拟物品就是:
1 | 虚拟重量 = amount * weight |
每个虚拟物品最多选择一次,因此可以直接套用 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 | def multiple_knapsack_binary( |
以 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)。
二进制分组的优势不只有复杂度:
- 数量上限越大,减少的枚举次数越明显。
- 拆完以后只需要复用熟悉的 0-1 背包模板,不必在每个状态中再枚举使用件数。
- 每组最多选择一次,而且所有组的数量之和等于上限,数量约束会自然得到保证。
- 相比单调队列优化,它更容易实现、调试和在面试中解释。
它也不是任何情况下都最优:如果 count >= capacity // weight,数量限制实际上不会生效,这种物品可以直接按完全背包正序更新;当容量和数量都非常大、题目又严格卡时间时,才需要进一步考虑 O(n * C) 的单调队列优化。
单调队列优化:把枚举件数变成滑动窗口最大值
如果还不熟悉单调队列,可以先复习栈与队列笔记中的滑动窗口最大值。那里解决的是“窗口每移动一步,怎样快速得到窗口最大值”;多重背包优化做的事情,就是先把状态转移改写成同一种问题。
先固定一种重量为 weight、价值为 value、最多使用 count 次的物品。处理它之前的数组记为 previous,处理之后的数组仍记为 dp。直接转移是:
1 | dp[current] = max( |
慢的原因是:每个 current 都要重新枚举一遍 used。想去掉这一层枚举,需要先观察哪些容量之间会发生转移。
第一步:按照容量除以重量的余数分组
每次选择当前物品,容量只会增加 weight,因此能够互相转移的容量,对 weight 的余数一定相同。
例如 weight = 3,容量会被拆成三条互不影响的序列:
1 | 余数 0:0, 3, 6, 9, 12, ... |
对于某个固定余数 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 | dp[remainder + step * weight] |
把只与当前 step 有关的部分提到最大值外面:
1 | dp[remainder + step * weight] |
其中来源位置必须满足:
1 | step - count <= source_step <= step |
因此,当 step 依次增加时,需要维护的就是一个长度最多为 count + 1 的滑动窗口。窗口里的候选分数是:
1 | score(source_step) |
最大的 score 永远放在队首,就能在 O(1) 时间得到当前状态的最优来源。
第三步:队列怎样维护候选来源
队列中保存 (source_step, score),并让 score 从队首到队尾单调递减。每来到一个新的 step,依次做三件事:
- 如果队首的
source_step < step - count,说明使用数量已经超过上限,把队首弹出。 - 当前候选的
score如果大于等于队尾,就把队尾弹出。旧候选分数不更大、位置还更靠左,以后不可能优于当前候选。 - 当前候选入队;此时队首就是当前窗口的最大分数。
下面只跟踪 weight = 3、value = 4、count = 2 这件物品,并专门观察余数为 1 的容量序列 1、4、7、10、13。previous 表示处理当前物品之前已经冻结的上一层结果;其他两个余数序列的处理方式完全相同。
按 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 | from collections import deque |
这里有两个关键点:
- 必须从
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 | 同一重量只在相同余数的容量之间转移 |
8.2 分组背包:每组最多选一个选项
分组背包把物品分成若干组,每组最多选一个。稳妥写法是每处理一组就保存上一层:
1 | def group_knapsack( |
关键是所有组内选项都从 previous 转移。如果把组内物品逐件当普通 0-1 背包处理,就可能从同一组选出多个选项。
背包类型可以用一张表区分:
| 类型 | 每件物品限制 | 一维容量方向 | 关键点 |
|---|---|---|---|
| 0-1 背包 | 最多一次 | 倒序 | 读取上一层,防止重复使用 |
| 完全背包 | 无限次 | 正序 | 允许读取本轮更新结果 |
| 多重背包 | 最多 count 次 |
倒序枚举、二进制分组,或按余数分组维护单调队列 | 防止超过数量上限 |
| 分组背包 | 每组最多选一个 | 每组读取同一份上一层 | 组内选项不能互相转移 |
9. 打家劫舍:当前选择会限制相邻状态
9.1 线性房屋:偷当前房就不能偷前一间
198. 打家劫舍 定义:
1 | dp[i] 表示考虑下标 0..i 的房屋时,能偷到的最大金额。 |
最后一间有两种选择:
1 | 不偷 i:dp[i - 1] |
可以压缩成两个变量:
1 | def rob(nums: list[int]) -> int: |
prev1 是已经处理到前一间的最优答案,不代表一定偷了前一间。因此“不偷当前房”直接继承 prev1。
9.2 环形房屋:首尾不能同时出现
213. 打家劫舍 II 首尾相邻。一个合法方案一定属于下面至少一种情况:
- 不考虑最后一间,只处理
nums[:-1]。 - 不考虑第一间,只处理
nums[1:]。
1 | def rob_circle(nums: list[int]) -> int: |
9.3 树形房屋:每个节点返回偷与不偷
337. 打家劫舍 III 把房屋放在二叉树上,父子节点不能同时偷。后序遍历每个节点,返回两个状态:
1 | skip:不偷当前节点时的最大金额 |
1 | def rob_tree(root: TreeNode | None) -> int: |
不偷当前节点时,孩子可以偷也可以不偷,所以左右孩子都取各自两个状态的最大值;不要误写成“不偷父节点就必须偷孩子”。
10. 股票问题:统一成持有与不持有状态
股票题不要为每道题单独背一份代码。先统一两个基础状态:
1 | hold:今天结束时,持有一只股票的最大利润 |
状态表示一天结束后的最优结果,不代表今天一定发生了买入或卖出。
10.1 一次交易和无限次交易,只差买入来源
121. 买卖股票的最佳时机 最多交易一次:
先保留完整的二维 DP 表:
1 | dp[day][0]:第 day 天结束时,持有股票的最大利润 |
1 | def max_profit_once(prices: list[int]) -> int: |
这两个转移可以直接按“今天做什么”理解:
- 今天结束后持股:要么延续昨天的持股状态,要么今天第一次买入。
- 今天结束后不持股:要么昨天就没有股票,要么把昨天持有的股票在今天卖出。
因为整道题最多只能完成一次交易,所以买入时不能使用之前卖出赚到的利润,买入来源只能是 0 - price,也就是 -price。理解二维表以后,再把上一天的两个状态压缩成 hold 和 cash 即可。
122. 买卖股票的最佳时机 II 允许反复交易,卖出后的利润可以用于下一次买入:
1 | def max_profit_unlimited(prices: list[int]) -> int: |
两个模板的核心区别:
1 | 一次交易买入:-price |
10.2 冷冻期:卖出后的次日不能立刻买入
309. 买卖股票的最佳时机含冷冻期 可以维护三个状态:
1 | dp[day][0]:第 day 天结束时持有股票 |
1 | def max_profit_with_cooldown(prices: list[int]) -> int: |
冷冻期体现在买入转移里:dp[day][0] 只能从昨天的持股状态或休息状态得到,不能从昨天刚卖出的 dp[day - 1][1] 买入。昨天卖出后,今天必须先进入休息状态;最早只能在明天再次买入。
10.3 最多两次交易:把五个阶段写成状态
123. 买卖股票的最佳时机 III 最多完成两次交易。一笔交易由一次买入和一次卖出组成,可以把每天结束后的进度分成五个状态:
1 | dp[day][0]:还没有进行任何操作 |
1 | def max_profit_two_transactions(prices: list[int]) -> int: |
每个状态都有两种来源:昨天已经处于这个状态,今天什么也不做;或者今天完成进入该状态所需的买入或卖出。使用 -inf 表示第 0 天不可能完成的操作,可以防止非法状态参与后面的最大值比较。
10.4 最多 K 次交易:展开成 2K + 1 个动作状态
188. 买卖股票的最佳时机 IV 是上一题的推广。把“第几次交易”和“是否持股”合并成一个状态编号,就可以继续使用二维数组:
1 | dp[day][0]:没有进行任何操作 |
状态 0 加上每笔交易的买入和卖出两个状态,一共需要 2 * k + 1 个状态。奇数下标表示买入后持股,偶数下标表示卖出后不持股。
1 | def max_profit_k_transactions(k: int, prices: list[int]) -> int: |
当 k = 2 时,一行正好是 [无操作, 第一次买入, 第一次卖出, 第二次买入, 第二次卖出],也就是上一题的五状态 DP。代码只是把固定的五个状态推广成 2 * k + 1 个状态。
这段代码的时间复杂度是 O(n * k),空间复杂度也是 O(n * k)。理解完整状态后,可以只保存前一天,把空间压缩到 O(k)。
10.5 含手续费:在完成交易时扣一次费用
714. 买卖股票的最佳时机含手续费 允许完成任意多次交易,只是在每笔交易中需要支付一次手续费。仍然使用持股和不持股两个状态:
1 | dp[day][0]:第 day 天结束时持股的最大利润 |
1 | def max_profit_with_fee(prices: list[int], fee: int) -> int: |
手续费放在买入或卖出时扣都可以,但一笔交易只能扣一次。这里统一在卖出时减去 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 | def length_of_lis(nums: list[int]) -> int: |
因为最长序列不一定以最后一个元素结尾,所以答案是 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 | def longest_common_subsequence(text1: str, text2: str) -> int: |
下面用 text1 = "abcde"、text2 = "ace" 逐格填写 DP 表。先观察第 0 行和第 0 列为什么都是 0,再重点比较字符相等与不相等时的来源。
1035. 不相交的线 与 LCS 完全同构:相同数字连线且不能相交,等价于保持两个数组中的相对顺序。
连续版本 718. 最长重复子数组 在元素不等时必须归零,因为公共连续片段不能跳过中间元素;LCS 不要求连续,所以不等时可以丢掉其中一个末尾字符继续比较。
11.3 编辑距离:增、删、改对应三个来源
72. 编辑距离 定义:
1 | dp[i][j] 表示 word1 前 i 个字符变成 word2 前 j 个字符的最少操作数。 |
1 | def min_distance(word1: str, word2: str) -> int: |
下面用 word1 = "horse"、word2 = "ros" 逐格计算。表格中的上方、左方和左上方,分别对应删除、插入和替换;字符相等时则直接继承左上方,不增加操作次数。
两个前缀 DP 可以用来源快速区分:
| 问题 | 元素不相等时怎么做 |
|---|---|
| LCS | max(上方, 左方) |
| 最长公共连续子数组 | 归零 |
| 编辑距离 | 1 + min(上方, 左方, 左上) |
| 不同子序列计数 | 只能丢弃源串末尾,读取上方 |
11.4 回文区间:i 倒序,j 正序
647. 回文子串 定义 dp[i][j] 表示闭区间 s[i:j+1] 是否为回文串:
1 | def count_substrings(s: str) -> int: |
当前区间依赖更靠里的 dp[i + 1][j - 1],所以 i 必须倒序,j 从 i 向右遍历。
516. 最长回文子序列 同样使用区间状态,但聚合方式不同。单字符区间先初始化为 1,再从短区间推向长区间:
1 | def longest_palindrome_subseq(s: str) -> int: |
这里 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 | dp[i] = 处理前 i 个元素的最优答案 → 通常返回最后一格 |
不要看到一维数组就默认返回 dp[-1]。
12.3 滚动数组会隐藏依赖方向
二维压缩成一维后,代码更短,但“上一行”和“当前行”不再显式出现。第一次整理一道题时,先写清二维状态来源,再判断:
- 当前格只依赖上一行吗?
- 需要保留哪些方向的旧值?
- 正序会不会读到本轮刚更新的状态?
这些问题决定能否压缩以及应该怎样遍历。
12.4 一份实用的 DP 检查清单
- 能否用一句话完整解释
dp每个下标的含义? - 当前状态的所有合法来源是否都列出来了?
- 初始化能否由状态定义直接解释?
- 不可达状态应该是
False、inf还是-inf? - 当前循环顺序下,读取的状态已经计算了吗?
- 答案是最后一格还是整张表的最大值?
- 空数组、单元素、容量 0、目标 0、全负数是否正确?
- Python 二维数组是否误用了
[[...]] * rows? - 多状态转移是否错误读取了当天刚更新的值?
- 用最小样例打印 DP 表时,每一格是否符合手算结果?
13. 复习总览
- 动态规划把重复子问题的答案保存下来,按照依赖顺序从小状态推出大状态。
- 五步法是:定义状态、写递推、做初始化、定遍历顺序、确定答案位置。
- 状态定义必须是一句完整的话;公式、初始化和遍历方向都要服从这个定义。
- 一维基础题常依赖前一两个位置;网格题常来自上方和左方。
- 0-1 背包每件物品最多一次,一维容量倒序;完全背包可以重复使用,容量正序。
- 计数组合时物品在外层;计数排列时容量在外层。
dp[0] = 1在计数题中表示空方案,dp[0] = True在可行性题中表示空集合可组成 0。- 多重背包限制每件数量,分组背包限制每组最多选一个,不能让组内选项互相转移。
- 打家劫舍是在“偷与不偷”之间转移;树形版本让每个节点同时返回两个状态。
- 股票题统一维护持有和不持有状态,限制次数、冷冻期、手续费只是修改状态或来源。
- LIS 使用“以
i结尾”的一维状态;LCS 和编辑距离使用两个前缀;回文题常使用区间状态。 - 递推式决定遍历顺序。滚动数组只是空间优化,不应该掩盖原本的依赖关系。
动态规划最难的不是把模板背下来,而是把状态说清楚。复习时先问“这一格代表什么、它从哪里来”,再写循环;只要状态语义稳定,初始化、遍历顺序和答案位置就会自然连起来。





