一、起源:暴力搜索的重复计算
1.1 递推式的直接翻译与指数级代价
有一类问题天然以递推的形式给出定义:第 n 项由更小的若干项决定。
斐波那契: F(n) = F(n-1) + F(n-2), F(0) = 0,F(1) = 1
爬楼梯: 走到第 n 级的方法数 = 走到第 n-1 级 + 走到第 n-2 级
卡特兰数: C(n) = Σ C(i)·C(n-1-i), C(0) = 1
把这类定义直接翻译成递归函数,代码与定义一一对应,正确性几乎不需要额外论证:
long fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
这段代码的问题不在于正确性,而在于代价。以 n = 5 展开调用树:
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
fib(3) 出现了 2 次,fib(2) 出现了 3 次。调用次数随 n 指数增长,递推式 T(n) = T(n−1) + T(n−2) + O(1) 的解为 O(φⁿ) ≈ O(1.618ⁿ),与"递归结构复杂度结论"一节给出的结论一致(见 复杂度与算法分析)。以每秒约 10⁸ 次基本操作为参照,n 超过 50 后这段代码就无法在可接受时间内返回。
代价的来源可以精确定位:同一个子问题被反复求解。fib(3) 的计算结果只取决于参数 3,与"它是由 fib(5) 还是 fib(4) 调用而来"无关。递归写法把这一信息丢弃了,因此每次进入 fib(3) 都要把整棵子树重新展开一遍。
1.2 把重复子问题的解缓存下来
既然子问题的结果只由其参数决定,那么首次算出 fib(3) 之后,后续再遇到参数为 3 的调用可以直接返回缓存值,无需重新展开子树。缓存带来的差别是量级层面的:
朴素递归: 调用次数 O(1.618^n)
加缓存后: 每个参数至多被真正计算一次,调用次数 O(n)
原因是每个子问题的解只被计算一次,之后的访问都是 O(1) 的查表。时间从指数级降到线性,代价是 O(n) 的存储空间。这是"空间换时间"最直接的一种形式,复杂度分析中的时空换算一节已把记忆化列为四类换算手段中的第一项。
long[] memo = new long[n + 1];
Arrays.fill(memo, -1);
long fib(int k) {
if (k <= 1) {
return k;
}
if (memo[k] >= 0) { // 已计算,直接返回
return memo[k];
}
memo[k] = fib(k - 1) + fib(k - 2);
return memo[k];
}
这一改动引入了动态规划的三个核心概念,后文分别展开:
| 概念 | 在斐波那契中的体现 |
|---|---|
| 状态 | 参数 k,即"第 k 项的值" |
| 状态转移 | dp[k] = dp[k-1] + dp[k-2] |
| 重叠子问题 | 同一个 k 被多条调用路径到达,因此缓存有效 |
1.3 与分治、贪心的区别
动态规划位于"分而治之"与"逐步贪心"之间,三者的差别可以用两个问题界定:子问题是否互相独立,每一步是否需要保留多个候选。
| 方法 | 子问题关系 | 每步保留的候选 | 决策依据 | 典型问题 |
|---|---|---|---|---|
| 分治 | 子问题互不重叠,可独立求解后合并 | 不涉及 | 结构分解 | 归并排序、二分查找、Strassen 矩阵乘法 |
| 贪心 | 每步只留一个局部最优解 | 1 个 | 局部最优即全局最优(需证明) | 活动选择、Huffman 编码、分数背包 |
| 动态规划 | 子问题重叠,需缓存复用 | 全部候选状态 | 枚举决策后取最优或求和 | 0-1 背包、编辑距离、最长递增子序列 |
与分治的差别在于子问题是否重叠。 归并排序把数组一分为二,左右两半没有任何共享的子数组,记忆化在这里只会增加查表开销而无收益。动态规划处理的问题恰恰相反:同一批子问题被反复使用,因此缓存是收益的来源。这一区分也决定了实现方式的选择:子问题不重叠时用分治,重叠时用记忆化或递推。
与贪心的差别在于是否愿意保留多个候选。 贪心在每一步只保留一个选择,并断言该选择一定会出现在某个全局最优解中;动态规划在每一步保留全部候选状态,通过枚举与比较得出最优值。这一差别在 0-1 背包与分数背包上表现得很清晰:
- 分数背包允许把物品切开,按单位价值从高到低取用时,取满一个再取下一个的策略可以证明最优,贪心成立。
- 0-1 背包不允许切开。用同样的策略会失败:容量为 10,物品为(体积 6、价值 6)、(体积 5、价值 5)、(体积 5、价值 5),按单位价值贪心先取第一件,剩余容量 4 装不下任何物品,总价值 6;而最优解是取后两件,总价值 10。
硬币兑换更能说明贪心的失效边界。币值集合为 {1, 3, 4},目标金额为 6:贪心先取 4,剩下 2 只能取两个 1,共 3 枚;最优解是 3 + 3,共 2 枚。贪心选择"面值最大的硬币"这一局部最优并未导向全局最优。同样的币值集合,换成 {1, 5, 10} 时贪心又成立——这说明贪心的正确性依赖币值集合的结构,必须逐一证明,而动态规划不需要这类额外假设。
二、原理
2.1 适用条件
动态规划不是通用方法。一个问题能否用动态规划求解,取决于它是否同时具备三个条件。
2.1.1 最优子结构
问题的整体最优解,由相关子问题的最优解构成。
以带权图的最短路径为例:从 s 到 t 的最短路径若经过顶点 u,则该路径在 s 到 u 与 u 到 t 两段上分别也是最短的。若其中一段可以改短,把它替换进去就得到一条更短的 s-t 路径,与"已经最短"矛盾。因此"用子问题的最优解拼装全局最优解"是合法的,这正是 Dijkstra 与 Bellman-Ford 能够工作的前提(见 最短路径与最小生成树 中松弛操作与最优子结构的关系)。
反例:最长简单路径。 在带正权图中求两点之间"不重复经过顶点"的最长路径。把问题按中间点 k 拆成两段后,两段的"最长简单路径"可能共用顶点;拼接后就不再是简单路径,需要舍弃其中一个子问题的最优解才能得到可行解。此时子问题的最优解无法拼成全局最优解,最优子结构不成立。该问题属于 NP-hard,不存在一般的多项式时间动态规划解法(除非把"已访问集合"并入状态,得到规模为 2ⁿ 的状态空间,见 2.5.7 节)。
判断最优子结构的实用做法:假设已经得到子问题的最优解,检查能否构造出原问题的一个可行解并证明其最优;构造过程中若出现"子问题之间互相干扰"或"需要推翻某个子问题的最优性",则最优子结构不成立。
2.1.2 无后效性
状态一旦确定,后续决策只依赖状态本身,与到达该状态的历史路径无关。
这是对状态定义的要求,而非问题的固有属性——同一个问题可能因为状态定义不同而"有后效性"或"无后效性"。
- 无后效性的例子: 最大子段和问题中,定义状态为"以第 i 个元素结尾的最大子段和"。后续元素只能接在这个子段之后,因此不需要知道这个子段从哪开始、前面是否还有更优的开头,"以 i 结尾且和最大"这一信息已经足够。
- 有后效性的例子: 若把"当前所在城市"直接作为状态来求"经过全部城市一次的最短回路",则下一步的可选集合取决于此前已经访问过哪些城市,历史没有被状态吸收,无法转移。
处理有后效性的两条路径:
- 把历史并入状态,使新状态满足无后效性。上例中把"已访问集合"与"当前城市"一起作为状态,就得到状态压缩的动态规划(2.5.7 节)。
- 重新定义状态的语义,使转移不依赖路径历史。斐波那契的状态是"第 k 项的值",与"k 是怎么来的"无关。
2.1.3 重叠子问题
不同的求解路径会反复到达同一批子问题。
这项条件决定的是"缓存是否有收益",而非"动态规划是否成立"。若子问题互不重叠,每个子问题只会被访问一次,缓存只是增加了查表与存储开销,此时应改用分治。
| 问题 | 子问题是否重叠 | 记忆化收益 | 合适方法 |
|---|---|---|---|
| 斐波那契 | 高度重叠,fib(k) 被多次需要 | 指数级降到线性 | 动态规划 |
| 0-1 背包 | 重叠,同一 (前缀物品, 容量) 被多条路径到达 | 显著 | 动态规划 |
| 归并排序 | 不重叠,左右子数组互不相交 | 无 | 分治 |
| 二分查找 | 不重叠,每次只剩一个子区间 | 无 | 分治 |
| 快速排序 | 不重叠(划分后互不相交) | 无 | 分治 |
| 朴素全排列枚举 | 不重叠(每条路径产出不同排列) | 无 | 回溯搜索 |
2.1.4 三个条件的判定顺序
输入问题
│
├─ 能否用"更小规模的最优解"拼接出"当前最优解"? ── 否 ──> 最优子结构不成立
│ 考虑贪心/搜索/近似
└─ 是
│
├─ 状态确定后,后续决策是否与历史路径无关? ── 否 ──> 把历史并入状态或重新定义状态
│ 仍不成立则改用搜索
└─ 是
│
├─ 子问题是否被反复到达? ── 否 ──> 用分治,无需缓存
└─ 是 ──> 动态规划适用于该状态定义
需要强调的是:判定结论与状态定义强绑定。最优子结构与无后效性中的"子问题",指的都是当前状态定义下的子问题。状态定义改变,结论可能随之改变。因此"这个问题不能用动态规划"这一说法,严格表述应当是"在这个状态定义下不能用动态规划"。
2.2 状态设计
状态设计是动态规划的主体工作,也是出错最集中的环节。实现层面的错误大多可以定位,状态设计层面的错误则表现为"结果系统性偏小或偏大""小数据正确、大数据错误"这类难以排查的现象。
2.2.1 状态的含义与维度确定
状态是一组足以决定后续决策的最小信息。 "最小"意味着不携带多余信息(否则状态数膨胀),"足以"意味着不遗漏必要信息(否则出现后效性)。
维度确定的方法是回答一个问题:做出下一步决策时,需要知道哪些量? 每个必需的"区分性信息"对应状态的一个维度。
| 问题 | 决策需要的信息 | 状态维度 |
|---|---|---|
| 斐波那契 | 要求第几项 | 1:位置 k |
| 0-1 背包 | 已考虑哪些物品、剩余多少容量 | 2:物品前缀 i、容量 v |
| 最长公共子序列 | 两个串各自匹配到哪一位 | 2:位置 i、位置 j |
| 编辑距离 | 同 LCS,另加操作形式的区分 | 2:位置 i、位置 j(转移中含 3 种操作) |
| 区间合并(石子合并) | 区间的两个端点 | 2:左端 i、右端 j |
| 买卖股票(最多 k 次交易) | 第几天、还可交易几次、当前是否持仓 | 3:天数 i、次数 j、持仓状态 |
| 旅行商 | 已访问集合、当前所在城市 | 2:集合掩码 S、城市 i |
| 填满网格的方案 | 逐行推进时上一行的占用形态 | 2:行号 i、上一行轮廓掩码 S |
维度数量直接决定了状态规模。状态数的表达式应与输入规模的记号对应,例如"i 从 1 到 n,v 从 0 到 C,因此状态数为 O(n·C)"。这一步必须在写代码前完成,因为它同时是复杂度结论的依据(3.4 节)。
状态定义的两条硬性要求:
- 可区分。两个在当前状态定义下无法区分的局面,其后续最优值必须相同。若不同,说明状态遗漏了信息。
- 不含冗余。若某个维度的值可以由其他维度推出,该维度应删除。冗余维度会让状态数与循环层数无谓增加。
2.2.2 转移方程与决策枚举
转移方程描述"当前状态由哪些更小状态、经过什么决策得到"。写转移方程的过程是枚举当前状态下的全部决策,每个决策给出一个候选值,再按问题类型取最优或求和。
最优性问题: dp[s] = min/max { cost(s, d, s') + dp[s'] | d 是状态 s 下的合法决策 }
计数性问题: dp[s] = Σ { dp[s'] | s' 可由 s 经一步合法决策到达 }
可行性问题: dp[s] = OR { dp[s'] | ... }
写转移方程时最常出现的两类遗漏:
- 遗漏决策。只考虑了"选当前元素",忘记"不选当前元素";只考虑到达某状态的某一种方式,忘记另一种。子序列类问题中"不选"往往对应从前一个位置直接继承,遗漏后会出现"答案比正确答案小"的现象。
- 重复计数。计数型问题中,同一个方案被多条转移路径重复统计。处理方式是固定枚举顺序,为每条转移路径规定唯一的"最后一步",例如规定"最后一步必须选中第 i 个元素"。
转移方程的每一项都应当能回答"它对应哪一种决策",无法回答的项通常是笔误或冗余。
2.2.3 边界与初始化
边界条件决定最小规模子问题的值,是整个递推的起点。初始化错误是最容易发生也最难通过随机测试发现的一类缺陷(3.6 节)。
| 问题类型 | 边界语义 | 初始化方式 | 常见错误 |
|---|---|---|---|
| 最优值(求最大) | 不可达状态 | 初始化为负无穷(用 -INF 而非 Integer.MIN_VALUE) | 全部初始化为 0,导致"不可达"被当作"代价为 0"参与比较 |
| 最优值(求最小) | 不可达状态 | 初始化为正无穷 | 初始化为 0,导致所有结果都变成 0 |
| 计数 | 空序列的方案数 | dp[0] = 1 | 遗忘空方案,结果恒为 0 |
| 可行性 | 起点可达 | dp[起点] = true | 起点未标记 |
| 序列匹配 | 空前缀的匹配代价 | dp[i][0] = i(编辑距离)、dp[0][j] = 0(LCS) | 维度方向写反 |
关于"求最大值时初始化为 0"的说明。 当问题隐含"可以从空集开始、答案非负"时(如背包求最大价值、最大子段和允许只取一个元素),初始化为 0 是正确的。但当状态空间中存在不可达状态时,把不可达状态的初值设为 0 会让它以一个虚假的"高价值解"参与比较,从而污染最优值。判断依据是:0 是否可能是该状态的真实最优值。若不可能且该状态可能不可达,就必须使用哨兵值。
2.2.4 答案的取法
递推结束后,答案并不总是 dp[n]。常见四种取法:
| 取法 | 形式 | 适用 |
|---|---|---|
| 末状态 | dp[n] | 状态本身恰好刻画"完成全部任务"(如编辑距离的 dp[n][m]) |
| 全状态最优 | max(dp[i]) | 状态刻画"以 i 结尾",最优解可能终止在任意位置(最长递增子序列、最大子段和) |
| 特定维组合 | dp[起点][终点] | 区间类问题(石子合并的 dp[1][n]) |
| 汇总 | Σ dp[终态] | 计数类问题需要对所有合法终态求和 |
最长递增子序列是取法容易出错的典型:dp[i] 定义为"以第 i 个元素结尾的最长递增子序列长度",因此答案不是 dp[n],而是所有 dp[i] 的最大值。同理,最大子段和若定义为"以 i 结尾的最大子段和",答案取所有 dp[i] 的最大值,而不是 dp[n]。
2.3 实现方式:记忆化与递推
同一个状态与转移方程有两种实现方式,二者的状态定义与结论一致,差别在计算的时机与顺序。记忆化与递归的对应关系、递归深度与栈溢出的处置、分治与动态规划的分界见 递归与分治。
| 维度 | 自顶向下(记忆化递归) | 自底向上(递推填表) |
|---|---|---|
| 推进方式 | 从原问题出发递归,遇到未计算的子问题才求解 | 从边界出发按依赖顺序填满状态表 |
| 计算范围 | 只计算被真正需要的状态 | 计算全部状态(含未被使用的) |
| 代码形态 | 与递推式一一对应,直观 | 需要显式确定遍历顺序 |
| 递归栈 | 有,深度等于依赖链长度,可能栈溢出 | 无 |
| 函数调用开销 | 有,常数较大 | 无,通常更快 |
| 空间压缩 | 不便(依赖关系隐含在递归中) | 便于滚动数组与一维化 |
| 缓存局部性 | 一般(访问顺序由递归决定) | 好(顺序访问数组) |
| 适用场景 | 状态空间大但只用到一部分、转移方向天然是"由大求小"、树形或图上不好确定顺序 | 状态空间稠密、依赖顺序明确、需要空间优化 |
选择依据。 状态表中"有用状态"占比很低、或依赖顺序不易显式表达(如树形结构、状态图有环)时,记忆化更合适:它只求解可达状态,且不需要确定拓扑序。反之,状态稠密、需要极限空间或极限常数时,递推更合适。
自顶向下在 Java 与 Python 中的写法差异。 Java 中缓存通常用数组或 HashMap 手工实现;Python 提供了 functools.lru_cache 装饰器,把缓存与递归解耦:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n: int) -> int:
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
lru_cache 的缓存键是函数的实参元组,因此被缓存函数的所有参数必须可散列,且不能包含"仅用于输出"的可变对象。递归深度受解释器递归上限约束,深度较大时需要改为递推或调整上限。
2.3.1 遍历顺序由依赖关系决定
自底向上的核心约束是:计算某个状态时,它依赖的所有状态必须已经计算完毕。 违反该约束会读到未初始化或过时的值,且不一定立刻报错,可能只在小规模或特定数据上表现出偏差。
| 依赖形态 | 遍历顺序 | 典型问题 |
|---|---|---|
dp[i] 依赖 dp[i-1]、dp[i-2] | i 递增 | 斐波那契、爬楼梯、打家劫舍 |
dp[i][j] 依赖 dp[i-1][*] | i 递增(内层任意) | 背包、LCS |
dp[i][j] 依赖同层的 dp[i][j-1] | 外层 i 递增,内层 j 递增 | 完全背包一维化后、某些网格路径计数 |
dp[i][j] 依赖 dp[i+1][j] | 外层 i 递减 | 编辑距离的正向压缩写法 |
dp[i][j] 依赖更短区间 dp[i][k]、dp[k+1][j] | 按区间长度递增 | 石子合并、括号匹配、矩阵链乘 |
dp[S] 依赖 S 的真子集 | 按掩码数值递增(子集必然小于全集) | 状态压缩 DP |
| 树上节点依赖其子节点 | 后序遍历(或按深度递减) | 树形 DP |
| 有向无环图上按拓扑序 | 拓扑序 | DAG 上的最长路、依赖调度 |
关于"按掩码数值递增"的说明。 状态压缩中,从集合 S 转移到 S ∪ {v} 时恒有 S ∪ {v} > S(因为加入了新的二进制位),因此直接按整数递增遍历掩码即可保证依赖已计算,无需额外排序。
2.4 空间优化
2.4.1 滚动数组与一维化
当 dp[i][*] 只依赖 dp[i-1][*] 时,可以把第一维压缩掉:
二维: dp[i][v] = max(dp[i-1][v], dp[i-1][v - w[i]] + val[i])
一维: dp[v] = max(dp[v], dp[v - w[i]] + val[i])
压缩的前提有两条:
- 转移只依赖有限的前若干层,通常是"前一层"。若依赖前 k 层,则可保留 k 行,用取模索引循环复用。
- 覆盖顺序不破坏依赖。这是压缩后最容易出错的地方。
2.4.2 遍历方向的变化:0-1 背包必须倒序
以 0-1 背包为例。一维数组中,dp[v] 既表示"处理完当前物品后的值",也是"处理上一个物品时的值"。对于 dp[v] = max(dp[v], dp[v - w] + val):
- 若容量
v正序遍历,计算dp[v]时dp[v - w]已经在本轮被更新过,它对应的是"已经选过当前物品"的状态。此时转移等价于"当前物品可以被重复选取",得到的是完全背包,而非 0-1 背包。 - 若容量
v倒序遍历,计算dp[v]时dp[v - w](更小的容量)尚未在本轮被更新,仍是上一轮的值,因此每个物品至多被选一次。
// 0-1 背包:容量倒序,保证每件物品只用一次
int[] dp = new int[C + 1];
for (int i = 1; i <= n; i++) {
for (int v = C; v >= w[i]; v--) {
dp[v] = Math.max(dp[v], dp[v - w[i]] + val[i]);
}
}
// 完全背包:容量正序,允许同一件物品重复选取
int[] dp = new int[C + 1];
for (int i = 1; i <= n; i++) {
for (int v = w[i]; v <= C; v++) {
dp[v] = Math.max(dp[v], dp[v - w[i]] + val[i]);
}
}
两段代码只差循环方向,解出的却是两个不同的问题。这是"空间压缩后遍历方向"最典型的例子,也是 3.6 节排查清单中的必查项。
方向的一般判据: 一维化后,dp[v] 的新值是否会作为同层转移的来源被再次使用。若会(允许重复使用当前物品或允许同层多次转移),正序;若不会(每件物品只处理一次),倒序。
2.4.3 依赖范围决定优化方式
| 依赖范围 | 优化方式 | 空间 | 例子 |
|---|---|---|---|
| 仅前一层 | 一维化,注意覆盖方向 | O(宽度) | 背包、LCS、编辑距离 |
| 前两层 | 三个变量或两行轮换 | O(宽度) 或 O(1) | 斐波那契、打家劫舍 |
| 前一层的连续区间 | 一维化 + 单调队列维护区间最值 | O(宽度) | 滑动窗口限制的转移、多重背包 |
| 前一层加当前层的某个前缀 | 一维化 + 前缀和 | O(宽度) | 区间求和型计数转移 |
| 同层的一个滑动窗口 | 单调队列 | O(宽度) | 带窗口上限的最大子段和类问题 |
| 全部更短区间 | 通常不能一维化(依赖 O(n) 个区间) | O(n²) | 区间 DP,只能做滚动或原地更新 |
路径还原与空间压缩的冲突。 一维化后,中间状态被覆盖,无法回溯出具体的决策序列。若需要输出方案而非仅输出最优值,有三种处理方式:保留完整的状态表;额外记录每一步的决策(前驱数组);或者在得到最优值后重新正推一遍以确定决策。第三种做法在背包类问题上常用,代价是需要保留物品列表与最终容量。
2.5 经典模型
状态设计的能力主要来自对已有一批模型的内化。以下模型覆盖了绝大多数变形的组合方式:新的问题通常可以识别为某个模型加上额外的状态维度或约束。
2.5.1 线性 DP
状态沿一个方向线性推进,转移只依赖前面的若干状态。
最长递增子序列(LIS)。 状态定义为"以第 i 个元素结尾的最长递增子序列长度":
dp[i] = 1 + max{ dp[j] | j < i 且 a[j] < a[i] },若不存在这样的 j 则 dp[i] = 1
答案 = max{ dp[i] | 1 ≤ i ≤ n }
定义中"以 i 结尾"这一限定是必须的:若去掉它,设 dp[i] 为"前 i 个元素中的最长递增子序列长度",则转移需要知道该子序列的结尾值才能判断能否接上 a[i],状态遗漏了信息。朴素实现的时间复杂度为 O(n²)。
最大子段和。 状态定义为"以第 i 个元素结尾的最大子段和":
dp[i] = max(a[i], dp[i-1] + a[i])
答案 = max{ dp[i] }
转移的两项分别对应"从 a[i] 重新开始一段"与"把 a[i] 接在前一段之后"。这里不需要"不选 a[i]"这一决策——因为状态强制要求以 a[i] 结尾,"不选"由后续位置或答案取法覆盖。这一细节说明"转移是否完整"要结合状态的语义判断。
2.5.2 背包问题
背包是状态维度与遍历顺序关系最丰富的一族模型。
0-1 背包。 每件物品至多选一次。状态 dp[i][v] 表示前 i 件物品、容量不超过 v 时的最大价值。一维化后容量倒序。
完全背包。 每件物品可选无限次。一维化后容量正序。其二维转移为 dp[i][v] = max(dp[i-1][v], dp[i][v-w[i]] + val[i]),注意第二项用的是同层的 dp[i],这正是"允许再选一件当前物品"的体现,也是一维化后需要正序的根本原因。
多重背包。 每件物品有数量上限 c[i]。两种做法:
- 二进制拆分:把数量 c 拆成 1、2、4、…、剩余,转化为若干件"只能选一次"的物品,再用 0-1 背包求解。复杂度 O(C · Σ log c[i])。
- 单调队列优化:按容量模 w[i] 的余数分组,在每组内用单调队列维护窗口最值,复杂度 O(n·C)。
分组背包。 物品分为若干组,每组至多选一件。循环顺序为:外层枚举组,内层倒序枚举容量,最内层枚举组内物品。顺序不可调换:容量必须在内层而非外层,否则同一组会被允许选多件。
| 模型 | 时间(朴素) | 空间 | 遍历要点 |
|---|---|---|---|
| 0-1 背包 | O(n·C) | O(C) | 容量倒序 |
| 完全背包 | O(n·C) | O(C) | 容量正序 |
| 多重背包(二进制拆分) | O(C·Σ log c[i]) | O(C) | 拆分为 0-1 |
| 多重背包(单调队列) | O(n·C) | O(C) | 按余数分组维护窗口 |
| 分组背包 | O(n·C) | O(C) | 组外、容量中层、组内最内 |
| 二维费用背包 | O(n·C₁·C₂) | O(C₁·C₂) | 两个容量维均需相应方向 |
背包的变体还包括"恰好装满"(初始化 dp[0]=0,其余为负无穷)与"至多容量"(全部初始化为 0)。这一差别正是 2.2.3 节初始化规则的直接应用。
2.5.3 区间 DP
状态为区间 dp[i][j],转移通过枚举分割点把区间拆成两个更短的子区间。遍历顺序必须按区间长度递增,因为长度较短的区间总是先被使用。
石子合并。 把 n 堆石子合并成一堆,每次只能合并相邻两堆,代价为两堆石子数之和,求最小总代价:
dp[i][j] = min{ dp[i][k] + dp[k+1][j] | i ≤ k < j } + sum(i..j)
边界: dp[i][i] = 0
答案: dp[1][n]
区间和由前缀和 O(1) 取得。朴素复杂度 O(n³)。当区间代价函数满足区间包含单调性与四边形不等式时,最优分割点满足 opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j],枚举范围收缩后复杂度降为 O(n²)。
括号匹配与最长回文子序列。 状态同样为区间,转移考虑两端字符的关系:匹配时两端配对并向内收缩,不匹配时舍弃某一端。这类转移的形态是"由两端决策决定是否收缩",与石子合并的"按分割点拆分"不同,但同样是区间 DP。
2.5.4 序列匹配
两个序列的匹配问题状态通常为二维 dp[i][j],表示两个序列各自处理到第 i、第 j 位时的最优值。编辑距离与最长公共子序列在字符串场景下的常用形式与工程落点见 字符串算法。
最长公共子序列(LCS)。
若 s[i] == t[j]: dp[i][j] = dp[i-1][j-1] + 1
否则: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
边界: dp[i][0] = dp[0][j] = 0
编辑距离。 允许插入、删除、替换三种操作,求把 s 变为 t 的最少操作数:
若 s[i] == t[j]: dp[i][j] = dp[i-1][j-1]
否则: dp[i][j] = 1 + min(dp[i-1][j-1], ← 替换
dp[i-1][j], ← 删除 s[i]
dp[i][j-1]) ← 在 s 中插入 t[j]
边界: dp[i][0] = i,dp[0][j] = j
边界的含义需要理解正确:dp[i][0] = i 表示把长度为 i 的 s 前缀变成空串需要 i 次删除,而不是 0。
序列匹配类的空间可以压缩到 O(min(n, m)),但需要保证内层循环遍历的是较短的那一维,或在滚动时正确处理 dp[i-1][j-1] 的暂存。若需要还原编辑方案(如输出 diff),则必须保留完整表格或前驱信息。
2.5.5 状态机 DP
把同一位置上"所处的状态"作为额外维度,转移在状态之间按固定规则跳转。
打家劫舍。 相邻房屋不能同时被选,求最大收益。状态为"第 i 间房选或不选":
dp[i][0] = max(dp[i-1][0], dp[i-1][1]) ← 不选第 i 间
dp[i][1] = dp[i-1][0] + nums[i] ← 选第 i 间
答案 = max(dp[n][0], dp[n][1])
由于每层只依赖上一层,空间可压缩为两个变量。
买卖股票。 状态为"第 i 天、当前是否持股"(若限制交易次数则再加一维)。转移包括买入、卖出、持有、空仓等待:
持有: dp[i][1] = max(dp[i-1][1], dp[i-1][0] - price[i])
空仓: dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price[i])
加上"含冷冻期""含手续费""最多 k 次交易"等约束时,只需增加状态维度或调整转移的常数项,模型结构不变。这是状态机 DP 的典型特征:约束以状态维度的形式进入模型,而非改写转移结构。
2.5.6 树形 DP
状态定义在树节点上,转移沿父子关系进行,通常采用后序遍历(先算完所有子节点,再合并到父节点)。树结构不存在环,因此不需要显式确定拓扑序,递归后序天然满足依赖关系。
树上最优选择(没有上司的舞会 / 打家劫舍 III)。 每个节点选或不选,父子不能同时选:
设 f(u, 0) 为不选 u 时 u 子树的最优值,f(u, 1) 为选 u 时 u 子树的最优值
f(u, 0) = Σ max(f(v, 0), f(v, 1))
f(u, 1) = val[u] + Σ f(v, 0)
答案 = max(f(root, 0), f(root, 1))
树的直径(最长路径)。 两种求法:两次遍历(从任一点出发找最远点 u,再从 u 出发找最远点 v,u-v 即直径端点,适用于无负权的树);或树形 DP(对每个节点求"向下延伸的最长链"与"次长链",两者之和即为经过该节点的最长路径,取全局最大)。树形 DP 版本的优势是只遍历一次,且可处理带权边。
树形 DP 的实现要点:
- 递归返回值需要携带足够的信息。上例中返回两个值(选/不选),只返回一个值会导致状态遗漏。
- 若树很深,递归会触及栈深度限制,需要改为显式栈的迭代后序,或按"节点深度递减"的逆序遍历。递归深度与树高的关系见 二叉树与二叉搜索树。
- 多叉树先合并子节点结果,再计算本节点,不能反序。
2.5.7 状态压缩 DP
当状态中必须包含一个"集合"信息时,把集合编码为二进制掩码,用整数下标索引该维度。适用前提是集合规模足够小,通常 n ≤ 20(2²⁰ ≈ 10⁶ 个状态可接受),因为状态数随集合规模指数增长。
旅行商问题(TSP)。 状态为 dp[S][i]:已访问城市集合为 S、当前位于城市 i 时的最小代价。
dp[S ∪ {v}][v] = min(dp[S][v]...) 即:
dp[S | (1<<v)][v] = min{ dp[S][u] + dist[u][v] | u ∈ S,v ∉ S }
初始: dp[{0}][0] = 0
答案: min{ dp[全集][u] + dist[u][0] }
复杂度: 状态数 O(2^n · n),每个状态枚举下一个城市 O(n),总时间 O(2^n · n²),空间 O(2^n · n)
其他典型形态:
| 问题 | 掩码含义 | 状态 |
|---|---|---|
| 集合划分(把元素分成若干组,最小化组内代价之和) | 已分配的元素集合 | dp[S] |
| 覆盖问题(用若干集合覆盖全集,最少用几个) | 已覆盖的元素集合 | dp[S] |
| 网格轮廓线(铺砖块) | 已决策与未决策的分界线两侧的占用形态 | dp[i][轮廓掩码] |
| 哈密顿路径 | 已访问顶点集合、当前终点 | dp[S][i] |
状态压缩的常见优化:
- 压缩无效状态。若转移只在若干特定形态之间发生(如相邻位不能同时为 1),可以预先枚举全部合法掩码并把它们重新编号,掩码维度大幅缩小。
- 交换维度顺序。把状态数小的一维放在外层,可改善缓存局部性;把需要整体更新的维度放内层,便于用数组整块处理。
- 按位运算替代集合操作。判断
v是否在S中用(S >> v & 1) == 1,加入用S | (1 << v),差集用S ^ (1 << v),子集枚举用for (int T = S; T > 0; T = (T - 1) & S)。
2.5.8 计数型 DP 与概率型 DP
计数型 DP。 转移从"取最优"改为"求和",通常需要取模。要点:
- 初始化
dp[0] = 1(空序列是一种方案),遗漏它会导致全部结果为 0。 - 注意去重:同一种方案若有多条转移路径,会被重复统计。解决办法是为每条转移规定唯一的"最后一步",或规定元素必须按某种顺序被选取。
- 取模运算在加法与乘法下保持结合律,可以在每次转移后取模;减法需先加模数再取模,避免负数。涉及除法取模时需要逆元。
概率型 DP。 求达成某结果的概率或期望值。要点:
- 期望的线性性允许把"总期望"拆成多个随机变量的期望之和,许多期望问题因此不需要状态转移,直接按线性性计算即可。
- 若问题依赖状态转移,通常采用逆推:设
dp[s]为"从状态 s 出发到终止状态的期望代价",转移为dp[s] = 1 + Σ p(s→s')·dp[s']。逆推的前提是状态图无环或可以按终止距离递减的顺序计算。 - 概率值使用浮点数时需注意累积误差与比较精度;期望值可能很大,需评估类型范围。
2.6 优化技巧
朴素动态规划的复杂度是"状态数 × 每个状态的转移代价"。优化从这两项入手:减少状态数(重新设计状态)或降低单次转移代价(优化转移)。
2.6.1 前缀和优化
适用场景: 转移中需要枚举一个连续区间的状态求和或取最值,且区间端点随当前下标单调移动。
朴素: dp[i] = Σ { dp[j] | L(i) ≤ j ≤ R(i) } 每状态 O(n)
优化: 预处理前缀和 S[k] = dp[1] + ... + dp[k]
dp[i] = S[R(i)] - S[L(i)-1] 每状态 O(1)
判定条件是"区间边界只由 i 决定,且可增量维护"。若区间内需要取最大值而非求和,前缀和无效,应改用单调队列。
2.6.2 单调队列优化
适用场景: 转移形如 dp[i] = min/max{ dp[j] + C(j, i) },其中 C(j, i) 可以分离为只与 j 相关和只与 i 相关的两部分,且合法的 j 构成一个随 i 单调移动的窗口。
dp[i] = min{ dp[j] + A(j) } + B(i), j ∈ [i-R, i-L]
由于 B(i) 与 j 无关,只需在窗口内维护 dp[j] + A(j) 的最小值,单调队列可在均摊 O(1) 时间内完成插入、删除与取最值。整体复杂度从 O(n²) 降为 O(n)。
判定条件: 窗口上下界随 i 单调不减(保证队列只从两端增删);被比较的表达式不含同时依赖 i 与 j 的交叉项。若存在交叉项,需考虑斜率优化。
2.6.3 斜率优化
适用场景: 转移中包含 i 与 j 的乘积项,形如
dp[i] = min{ dp[j] + a[i]·b[j] + c[j] } + d[i]
把含 j 的项整理为"以 b[j] 为自变量、dp[j] + c[j] 为因变量"的点,转移等价于"用斜率 -a[i] 的直线去截这些点,求截距最小"。当 a[i] 单调时,用单调队列维护下凸壳,均摊 O(1) 取最优;当 a[i] 不单调时,在凸壳上二分查找,单次 O(log n)。
判定条件与代价: 需要转移能写成上述线性形式,且决策点集合可增量维护。实现上需要处理斜率比较的精度问题(用交叉相乘代替除法以避免浮点误差)与凸壳的弹出条件(不满足凸性的点直接淘汰)。实现复杂度明显高于前两种优化,只有在复杂度确实无法接受时才引入。
2.6.4 四边形不等式与决策单调性
适用场景: 区间 DP 或形如 dp[i] = min{ dp[j] + w(j, i) } 的一维转移。
判定条件: 代价函数 w 满足
- 区间包含单调性:若区间 A ⊆ B,则
w(A) ≤ w(B); - 四边形不等式:
w(a, c) + w(b, d) ≤ w(a, d) + w(b, c),其中 a ≤ b ≤ c ≤ d。
满足时,最优决策点 opt 具有单调性:区间 DP 中 opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j],枚举范围从 O(n) 收缩到均摊 O(1),总复杂度从 O(n³) 降到 O(n²);一维转移中 opt[i] 单调不减,可用"分治优化"把复杂度从 O(n²) 降到 O(n log n)。
使用边界: 该优化只给出枚举范围的收缩,不改变转移方程的语义;若代价函数依赖具体数据而不满足上述两个条件,优化后的结果可能错误。实践中应先写朴素版本并用对拍验证优化版本的等价性(3.1 节)。
2.6.5 记忆化与递推的相互转化
两种实现共享同一套状态与转移方程,因此可以互相改写:
- 记忆化转递推:把递归调用关系看作依赖边,对状态依赖图做拓扑排序,按该顺序填表。若依赖图无环(状态定义满足无后效性时必然无环),该顺序一定存在。
- 递推转记忆化:把填表循环改写为递归函数,在函数入口检查缓存、出口写入缓存。
转化的实用价值:
- 调试。递推版本便于打印状态表并观察局部数值;记忆化版本便于验证"该状态是否需要被计算"。
- 确定遍历顺序。把记忆化版本的调用关系打印出来,可以看出真实的依赖顺序,用于确定递推版本的循环嵌套层次与方向。
- 空间优化。递推版本便于识别"只依赖前一层",从而实施滚动数组;记忆化版本不容易看出这一点。
2.6.6 状态的重新设计以降维
当状态数过大导致超时时,除了优化转移,还可以考虑改变状态定义本身。
| 手法 | 做法 | 效果 |
|---|---|---|
| 删除冗余维度 | 若某维度的值可由其他维度推出,删除该维度 | 状态数直接下降一个量级 |
| 交换"存什么"与"求什么" | 把答案作为状态、把原状态的一个维度作为值 | 以答案范围换状态维度 |
| 分阶段处理 | 把"同时决策多个维度"改为"逐维度依次决策",用多次 DP 组合 | 状态数由乘积变求和 |
| 合并对称状态 | 若两个状态在后续决策中完全等价,合并为同一状态 | 状态数按对称群大小下降 |
| 交换维度顺序 | 把循环嵌套顺序调整为内层维度连续 | 改善缓存命中,常数级收益 |
"交换存什么与求什么"的典型用法。 若状态 dp[i][v] 中 v 的取值范围达到 10⁹ 而答案范围很小,可以改为 g[i][k] 表示"前 i 个物品取得价值 k 所需的最小容量",状态数由 O(n·C) 降为 O(n·maxValue)。这一手法适用于容量极大、价值较小的场景。
2.7 与其他方法的边界
2.7.1 与贪心
| 维度 | 贪心 | 动态规划 |
|---|---|---|
| 每步保留的候选 | 一个 | 全部候选状态 |
| 正确性依据 | 需证明"局部最优必属于某个全局最优解" | 最优子结构 + 无后效性 |
| 复杂度 | 通常更低 | 状态数 × 转移代价 |
| 失效信号 | 存在反例 | 无(前提满足时一定正确) |
| 实现难度 | 低(但证明难度未必低) | 中到高 |
判定方法:举反例。 设计贪心策略后,先在小规模、结构特殊的数据上尝试构造反例。1.3 节的硬币兑换({1,3,4} 凑 6)与 0-1 背包都是廉价的反例模板:贪心失效往往发生在"局部最优选择占用了后续更需要的资源"。若一时无法构造反例,也不应立即断定贪心正确——反例可能存在于更大规模;此时可以用动态规划在小数据上求最优值,与贪心结果对照(即 3.1 节的对拍)。贪心选择性质的证明方法(交换论证、拟阵)与失效反例的构造思路见 贪心与回溯。
两者的关系不是对立。 动态规划的部分环节可能内嵌贪心思想:Dijkstra 按最短距离由小到大处理顶点是一种贪心(其正确性依赖边权非负),而处理顺序本身由"松弛后的距离"决定,与动态规划的分层推进在形式上一致。见 最短路径与最小生成树 中关于松弛顺序的讨论。
2.7.2 与分治
判据是子问题是否重叠:
- 重叠 → 记忆化或递推,避免重复计算。
- 不重叠 → 分治,缓存无收益。
一个中间形态是分治 + 动态规划:若状态转移的决策点在分治结构上具有单调性,可用分治优化(2.6.4 节)计算转移,复杂度为 O(n log n)。
2.7.3 与搜索加剪枝
| 场景 | 倾向选择 | 理由 |
|---|---|---|
| 状态空间可枚举且规模可控 | 动态规划 | 有确定的时间上界 |
| 状态数随输入规模指数增长且无法压缩 | 搜索 + 剪枝 | 动态规划的状态表无法容纳 |
| 只需判断可行性、不需求最优值 | 搜索(BFS/DFS)或并查集 | 动态规划的最优性枚举是多余的 |
| 需要输出全部方案而非一个最优值 | 搜索 + 回溯 | 动态规划通常只保留最优值 |
| 剪枝条件强、实际搜索分支很少 | 搜索 + 剪枝 | 常数与实现成本更低 |
| 状态可形式化、依赖关系明确 | 动态规划 | 可预测、可优化 |
两者的结合也存在:记忆化搜索本身是"带缓存的搜索",当状态空间稀疏时,它比填满整张表的递推更高效;搜索过程中若发现某状态的最优值已确定,可直接返回缓存值,相当于在搜索树中实施动态规划。
2.7.4 与最短路的等价性
动态规划可以视为有向无环图上的最短路径问题。 把每个状态看作图中的一个顶点,把每条合法转移看作一条有向边(边权为转移代价),则"求最优值"等价于"求从初始状态到终止状态的最短(或最长)路径"。
| 问题特征 | 对应图结构 | 求解方式 |
|---|---|---|
| 状态转移无环(无后效性成立) | 有向无环图(DAG) | 按拓扑序递推,O(状态数 + 转移数) |
| 状态转移有环(状态定义未吸收历史) | 一般有向图,可能含环 | 需按最短路径算法求解:非负权用 Dijkstra,含负权用 Bellman-Ford |
| 转移代价含负值且存在负环 | 无解或最短路无下界 | 先检测负环 |
Floyd 算法是这一等价关系最清晰的实例:它的状态是"只允许前 k 个顶点作为中间点时的最短距离",三重循环按 k 分层推进,本质上就是按状态分层做动态规划。该状态定义、转移方程的推导与"k 必须位于最外层"的原因见 最短路径与最小生成树 中 Floyd 的动态规划视角一节。
这一视角的实用价值:
- 判断能否递推。 若状态转移图无环,一定存在拓扑序,可以递推;若出现环,说明状态定义不满足无后效性(或问题本身的最优解结构确实含环),不能直接递推。
- 识别可用的算法。 一旦把问题转化为最短路,可以直接使用已有的最短路算法与其负权、负环处理经验,不必重新设计 DP 结构。
- 解释 Bellman-Ford 的轮次。 Bellman-Ford 的"最多进行 V−1 轮松弛"对应"最短路径最多含 V−1 条边",其逐轮扫描全部边的推进方式与动态规划的按层填表同构。
三、实现
3.1 建模步骤
从问题描述到可运行的代码,中间需要一个稳定的推导流程。跳过其中任何一步,都容易在调试验证阶段付出更大代价。
3.1.1 推导流程
第 1 步 明确决策与阶段
—— 每一步要做什么选择?按什么顺序推进(时间、位置、物品编号、区间长度)?
第 2 步 列出状态变量
—— 做出下一步决策时,必须知道哪些信息?
—— 每个必需信息对应一个维度;检查是否存在冗余维度与遗漏信息。
第 3 步 写出状态的含义(用一句自然语言表述)
—— 例:"dp[i][v] 表示从前 i 件物品中选择、总容量不超过 v 时的最大价值。"
—— 若这句话写不出来,说明状态尚未想清楚。
第 4 步 枚举决策、写出转移方程
—— 对每个状态,列出全部合法决策,逐一写出对应的候选值。
—— 检查是否遗漏"不选/跳过"这一决策;检查计数问题是否重复统计。
第 5 步 确定边界与初始化
—— 最小规模子问题的值是多少?不可达状态用什么哨兵?
—— 检查 0 是否可能是真实最优值(决定是否可用 0 作为初值)。
第 6 步 确定答案的取法
—— 答案位于 dp[n]?还是所有 dp[i] 的最值?还是某个维度组合?
第 7 步 确定遍历顺序
—— 依据状态之间的依赖方向(2.3.1 节的对照表)。
—— 决定内层循环的方向与上下界。
第 8 步 估算复杂度、判断是否需要空间或转移优化
—— 状态数 × 每状态转移代价;对照目标规模判断是否可行。
第 9 步 实现朴素版本,用小规模暴力对照验证正确性
—— 通过后再实施优化,并对优化版本做同样验证。
第 3 步的重要性往往被低估。 把状态含义写成一句话,可以在编码前暴露绝大多数定义问题:如果这句话里必须加入"并且已经……"之类的历史限定,说明无后效性可能不成立;如果这句话无法覆盖问题的全部约束,说明状态漏了维度。
3.1.2 正确性验证:暴力对照与对拍
动态规划的错误以小数据正确、大数据错误的形式出现时最难定位。可靠的验证方式是与暴力求解对照。
区间 DP 与线性 DP 的暴力对照。 对同一组小规模随机数据(n 取 8 至 12),分别运行动态规划与暴力枚举(全排列、全子集或指数级递归),比较结果是否一致。小规模保证了枚举的可行性,随机数据保证了覆盖的多样性。
对拍流程。
循环若干轮:
1. 用随机数生成器产生一组小规模输入
2. 分别运行暴力程序与优化后的程序
3. 比较两份输出
4. 不一致则保存该组输入,停止循环
一致通过全部轮次后,再在较大规模上比较朴素 DP 与优化 DP
// 对拍骨架:暴力与动态规划在同一组随机输入上比较
Random rnd = new Random(2026);
for (int round = 0; round < 10000; round++) {
int n = 1 + rnd.nextInt(10); // 小规模,保证暴力可行
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = rnd.nextInt(20);
}
long expected = bruteForce(a);
long actual = solveByDp(a);
if (expected != actual) {
System.out.println("mismatch: " + Arrays.toString(a));
System.out.println("expected=" + expected + " actual=" + actual);
break;
}
}
固定随机种子是可复现的前提:出现不一致时,同一个种子可以重放该组输入。验证通过后再更换种子扩大覆盖范围。
优化的等价性验证。 每引入一项优化(滚动数组、单调队列、四边形不等式),都应与未优化的版本在小规模上对拍。优化引入的错误通常表现为"边界数据出错"或"极值数据出错",随机测试需要覆盖这些形态:全部元素相同、严格递增、严格递减、含大量重复值、含 0 与极值。
3.2 代码实现要点
3.2.1 数组维度与下标偏移
统一使用 1 起始的语义下标。 递推式中的"第 i 个物品""前 i 个字符"通常从 1 开始计数,而数组的下标从 0 开始。两种处理方式:
// 方式一:数组大小为 n + 1,下标 i 直接对应"前 i 个"
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 使用 s.charAt(i - 1) 访问原始串的第 i 个字符
}
}
// 方式二:在序列前插入一个哨兵元素,使下标与位置一一对应
char[] s = (" " + source).toCharArray(); // s[1..n] 对应原串
char[] t = (" " + target).toCharArray();
方式一不需要额外空间,但访问原序列时必须做 i - 1 的换算;方式二消除了换算,但引入一个额外的哨兵位。两种方式都可行,混淆使用是错误的主要来源:在同一个函数里混用两种约定,会导致某处多减 1 或少减 1,表现为结果整体偏移一位。
避免负索引。 当转移中出现 dp[i][j-1]、dp[v-w] 这类引用时,必须确保下标不会越界。做法是让循环边界与转移中的最远引用一致:
// dp[i][j] 依赖 dp[i-1][j-1],因此 i、j 从 1 开始,保证了 i-1、j-1 不为负
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// ...
}
}
对于"下标可能为负"的语义(如坐标差),通过对下标加偏移量把区间平移到非负范围,例如坐标范围 [−1000, 1000] 映射为 [0, 2000]。
3.2.2 初始化与不可达标记
哨兵值的选取。 用 Integer.MIN_VALUE 表示不可达时,任何加法都会溢出(MIN_VALUE + 1 仍为负数,MIN_VALUE + MIN_VALUE 会回绕)。稳妥的做法是取一个"足够小但不至于溢出"的值:
static final int INF = Integer.MAX_VALUE / 2; // 避免加法溢出
static final int NEG_INF = Integer.MIN_VALUE / 2;
// 求最小值的场景
int[] dp = new int[n + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
// 求最大值的场景
long[] best = new long[n + 1];
Arrays.fill(best, NEG_INF);
best[0] = 0;
MAX_VALUE / 2 与 MIN_VALUE / 2 的选取依据是"两次相加仍在类型范围内",足以容纳一行中出现的所有加法。若转移中可能出现三次相加,则需要进一步收缩哨兵值,或改用 long。
不可达状态的传播。 使用哨兵值时,转移前应判断来源状态是否可达,否则会得到"看似合理"的数值:
if (dp[j] == INF) {
continue; // 跳过不可达状态,避免 INF + w 参与比较
}
dp[j + w] = Math.min(dp[j + w], dp[j] + cost);
若判断不可达状态的代价可观,可以依赖哨兵值的相对大小关系:只要哨兵值与真实值之间的间隔足够大,INF + w 仍然大于任何真实值,比较结果依然正确。这一做法在常数上更优,但要求对哨兵值的取值范围有明确把握。
3.2.3 边界循环范围
循环的上下界需要与转移式中实际引用的下标一致,过宽会访问未初始化状态,过窄会遗漏决策。
| 场景 | 常见错误边界 | 正确边界 |
|---|---|---|
| 0-1 背包内层容量 | v = C; v >= 0(当 v < w 时无意义) | v = C; v >= w[i] |
| 完全背包内层容量 | v = 0(当 v < w 时无意义) | v = w[i]; v <= C |
| 区间 DP 起点 | i = 1; i <= n(j 会越界) | i + len - 1 <= n |
| 区间 DP 分割点 | k = i; k <= j(会使子区间为空) | k = i; k < j |
| LCS 二维 | i = 0(dp 下标为负) | i = 1; i <= n |
| 状态压缩 | S 从 0(空集通常无意义) | 从初始集合开始 |
3.2.4 类型与溢出
动态规划中数值的累积速度容易被低估。
| 问题类型 | 数值增长 | 建议类型 |
|---|---|---|
| 最优值(代价、价值) | 与输入规模线性或平方相关 | 按量级估算,超 2×10⁹ 用 long |
| 计数(方案数) | 指数级增长,必须取模 | long 并随时取模 |
| 期望值 | 可能远大于输入数值 | double,注意精度与特殊值 |
| 中间加法 | 两个接近上限的值相加 | 用 long 作为累加器后再判断 |
计数问题不存在"不取模"的选择。 方案数通常按指数增长,任何固定宽度的整数类型都会溢出。取模的位置在每次加法之后:
final int MOD = 1_000_000_007;
dp[i] = (dp[i] + dp[i - 1]) % MOD;
减法在取模下需要处理负数:(a - b + MOD) % MOD。
3.2.5 备忘录的实现方式
自顶向下实现需要一张"状态到值"的表。这张表在语义上是一个映射(键为状态,值为该状态的最优值或方案数),属于 抽象数据类型(ADT) 中的映射类型,其底层可由数组或哈希表实现,两种载体的取舍如下:
| 载体 | 适用 | 优点 | 限制 |
|---|---|---|---|
| 数组 | 状态可以由小范围的整数下标唯一索引 | 访问 O(1),常数最小,内存紧凑 | 状态空间稀疏时浪费空间;状态含多维度或非整数时不便 |
| 哈希表 | 状态空间稀疏、状态是多维元组或字符串、状态值范围过大 | 只存实际访问过的状态 | 有哈希与装箱开销,常数明显更大 |
选择依据是状态的实际使用率。 若状态表中被访问的状态占比超过约一半,数组更优;占比很低(例如状态定义中包含"已访问集合"而实际可达集合很少)时,哈希表可以避免为不可达状态分配空间。
Java 中多维状态用哈希表时,需要把多维键编码为单一键:
// 方式一:编码为单个 long(各维有明确上界时)
long key = (long) i * (m + 1) + j;
// 方式二:编码为字符串(可读性好,开销大,仅适合调试或极稀疏场景)
String key = i + "," + j;
// 方式三:自定义记录类型(Java 16+ 的 record 自动具备 equals 与 hashCode)
record State(int i, int j) {}
Map<State, Integer> memo = new HashMap<>();
编码方式必须保证不同状态映射到不同键(即编码是单射),否则不同状态会互相覆盖。各维的上界需要在编码时预留,例如 j 的上界为 m 时,乘数取 m + 1。
关于哈希表的冲突处理、扩容行为与键的 equals/hashCode 契约,见 散列表;使用可变对象作为键会导致缓存失效,因为对象被修改后哈希值改变,无法再定位到原有条目。
3.3 典型实现
以下给出六个基础模型的实现要点。代码只保留结构,边界与哨兵按前文规则处理。
3.3.1 0-1 背包与完全背包
/**
* 0-1 背包:容量 C,物品 i 的体积 w[i] 与价值 val[i],每件至多选一次。
* dp[v] = 容量为 v 时的最大价值,容量倒序遍历。
* 时间 O(n·C),空间 O(C)。
*/
static int zeroOneKnapsack(int[] w, int[] val, int C) {
int[] dp = new int[C + 1]; // 题意允许不选任何物品,故初值为 0
for (int i = 0; i < w.length; i++) {
for (int v = C; v >= w[i]; v--) { // 倒序:dp[v-w[i]] 仍是上一层状态
dp[v] = Math.max(dp[v], dp[v - w[i]] + val[i]);
}
}
return dp[C];
}
/**
* 完全背包:每件物品可选任意多次。
* 与 0-1 背包的唯一差别是容量正序遍历。
*/
static int unboundedKnapsack(int[] w, int[] val, int C) {
int[] dp = new int[C + 1];
for (int i = 0; i < w.length; i++) {
for (int v = w[i]; v <= C; v++) { // 正序:dp[v-w[i]] 已是本层状态
dp[v] = Math.max(dp[v], dp[v - w[i]] + val[i]);
}
}
return dp[C];
}
要点:
- 两段代码只差循环方向,对应两个不同的问题。改动方向时必须同步确认问题语义是否改变。
- "恰好装满容量 C"时,
dp[0] = 0、其余初始化为负无穷,最终dp[C]若仍为负无穷表示无解。这一改动对应 2.2.3 节的初始化规则。 - 容量维使用一维数组时,物品循环必须在最外层。若内外层互换(容量在外、物品在内),0-1 背包会退化为"每种容量组合可重复选取物品"的错误模型。
3.3.2 最长递增子序列
/**
* O(n^2) 版本:dp[i] 表示以 a[i] 结尾的最长递增子序列长度。
*/
static int lisQuadratic(int[] a) {
int n = a.length;
int[] dp = new int[n];
int best = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1; // 子序列至少包含 a[i] 自身
for (int j = 0; j < i; j++) {
if (a[j] < a[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
best = Math.max(best, dp[i]); // 答案取全局最大值
}
return best;
}
/**
* O(n log n) 版本:tails[k] 表示"长度为 k+1 的递增子序列"的最小结尾值。
* 维护 tails 为严格递增序列,对每个元素二分找到第一个不小于它的位置并替换。
*/
static int lisBinarySearch(int[] a) {
int[] tails = new int[a.length];
int len = 0;
for (int x : a) {
int lo = 0, hi = len;
while (lo < hi) { // 寻找第一个 >= x 的位置
int mid = (lo + hi) >>> 1;
if (tails[mid] < x) {
lo = mid + 1;
} else {
hi = mid;
}
}
tails[lo] = x;
if (lo == len) {
len++;
}
}
return len;
}
要点:
tails维护的是"长度为 k 的递增子序列的最小结尾值"这一辅助信息,它本身通常不是原数组中的任何一个具体子序列。若需要还原方案,必须额外记录每个元素的前驱(dp版本自然具备该能力)。- 二分时用
tails[mid] < x(严格小于)得到严格递增;改为<=则得到非递减子序列。这一处符号决定了问题语义。 - O(n log n) 版本的贪心性质(用更小的结尾值替换,不损失后续可选空间)需要证明:结尾值越小,后续可接的元素集合越大,因此替换不会使答案变差。这一性质是"贪心 + 二分",但结论与 O(n²) 的动态规划版本一致。
3.3.3 编辑距离
/**
* 把 s 转换成 t 的最少操作数(插入、删除、替换各计 1)。
* 时间 O(n·m),空间 O(n·m);滚动数组可降至 O(min(n, m))。
*/
static int editDistance(String s, String t) {
int n = s.length(), m = t.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = i; // 全部删除
}
for (int j = 0; j <= m; j++) {
dp[0][j] = j; // 全部插入
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], // 替换
Math.min(dp[i - 1][j], // 删除 s[i]
dp[i][j - 1])) + 1; // 插入 t[j]
}
}
}
return dp[n][m];
}
要点:
- 边界含义是"把空串变成长度 k 的串需要 k 次操作",因此
dp[i][0] = i、dp[0][j] = j,而不是 0。 - 相等时直接继承
dp[i-1][j-1](不需要操作),不能写成"取三者最小值"——后者会把无需操作的字符也计一次。 - 一维化时
dp[j-1]在同一轮中已被更新为当前行的值,而dp[j]仍是上一行的值,因此需要用一个临时变量暂存上一轮的dp[j](即二维时的dp[i-1][j-1])。这是滚动数组最常见的实现细节。 - 若比较的是字符数组而不是字符串,可省去
charAt的边界检查开销,在大规模比较中有可测量的收益。
3.3.4 最长公共子序列
/**
* LCS:dp[i][j] 表示 s 前 i 个字符与 t 前 j 个字符的最长公共子序列长度。
* 时间 O(n·m),空间 O(n·m),可滚动至 O(min(n, m))。
*/
static int lcs(String s, String t) {
int n = s.length(), m = t.length();
int[][] dp = new int[n + 1][m + 1]; // 第 0 行与第 0 列初值为 0
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
}
要点:
- 先检查两个串的公共前缀/后缀长度,可以把问题规模直接缩小:公共前缀与后缀一定属于某个 LCS,剪掉它们不影响结果,也不改变最优值。
- 与编辑距离的差别在于不等时的处理:LCS 取"两个方向的最大值"而不加 1,因为跳过字符不产生长度。
- 一维化后,
dp[j]的更新依赖上一轮的dp[j](二维时的dp[i-1][j])与本轮已更新的dp[j-1](二维时的dp[i][j-1]),同时还需要上一轮的dp[j-1](二维时的dp[i-1][j-1]),因此需要一个临时变量保存被覆盖的值。
3.3.5 区间 DP:石子合并
/**
* 石子合并:每次合并相邻两堆,代价为两堆之和,求合并为一堆的最小总代价。
* 时间 O(n^3)(四边形不等式优化后 O(n^2)),空间 O(n^2)。
*/
static int stoneMerge(int[] stone) {
int n = stone.length;
int[] prefix = new int[n + 1];
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + stone[i - 1];
}
int[][] dp = new int[n + 2][n + 2];
for (int len = 2; len <= n; len++) { // 长度由小到大
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) { // 枚举分割点
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
dp[i][j] += prefix[j] - prefix[i - 1]; // 本次合并的代价
}
}
return dp[1][n];
}
要点:
- 外层必须是区间长度而不是左端点。若外层为左端点,计算
dp[i][j]时dp[k+1][j]可能尚未计算。 - 合并代价
prefix[j] - prefix[i-1]与本段内部如何分割无关,可以提到内层循环之外,这是四边形不等式优化能够成立的结构性原因。 dp的大小取n + 2是为了让k + 1 ≤ n + 1时不越界;实际使用的下标范围仍是 1 至 n。
3.3.6 状态机 DP:打家劫舍
/**
* 打家劫舍:相邻房屋不能同时被选,求最大收益。
* 状态机视角:每个位置有"选/不选"两种状态。
* 由于每层只依赖上一层,空间压缩为常数。
*/
static int rob(int[] nums) {
int skip = 0; // 上一间不选时的最大收益
int take = 0; // 上一间选时的最大收益
for (int x : nums) {
int newSkip = Math.max(skip, take); // 本间不选:上一间选与不选均可
int newTake = skip + x; // 本间选:上一间必须不选
skip = newSkip;
take = newTake;
}
return Math.max(skip, take);
}
要点:
- 环形房屋(首尾相邻)的处理方式是拆成两个线性问题:不选第一家时的最优值,与不选最后一家时的最优值,取两者较大者。这是"环形约束化为线性"的通用手法。
- 状态机 DP 的空间压缩要求"每层的转移只依赖上一层",因此不能像数组那样直接原地更新——必须先用临时变量保存上一层的两个值。
3.4 复杂度与实测
3.4.1 状态的复杂度分析
时间复杂度 = 状态数 × 每个状态的平均转移代价
空间复杂度 = 状态数(未优化时)或 保留的层数 × 单层宽度(优化后)
| 模型 | 状态数 | 单状态转移代价 | 时间 | 空间(未优化) | 空间(优化后) |
|---|---|---|---|---|---|
| 斐波那契 / 爬楼梯 | O(n) | O(1) | O(n) | O(n) | O(1) |
| 0-1 背包 | O(n·C) | O(1) | O(n·C) | O(n·C) | O(C) |
| 完全背包 | O(n·C) | O(1) | O(n·C) | O(n·C) | O(C) |
| 多重背包(朴素) | O(n·C) | O(c[i]) | O(C·Σc[i]) | O(C) | O(C) |
| 多重背包(单调队列) | O(n·C) | O(1) 均摊 | O(n·C) | O(C) | O(C) |
| 最长递增子序列(朴素) | O(n) | O(n) | O(n²) | O(n) | O(n) |
| 最长递增子序列(贪心+二分) | O(n) | O(log n) | O(n log n) | O(n) | O(n) |
| 最长公共子序列 | O(n·m) | O(1) | O(n·m) | O(n·m) | O(min(n,m)) |
| 编辑距离 | O(n·m) | O(1) | O(n·m) | O(n·m) | O(min(n,m)) |
| 区间 DP(朴素) | O(n²) | O(n) | O(n³) | O(n²) | O(n²) |
| 区间 DP(四边形不等式) | O(n²) | O(1) 均摊 | O(n²) | O(n²) | O(n²) |
| 树形 DP | O(n) | O(度) | O(n) | O(n) | O(n) |
| 状态压缩 DP(TSP) | O(2ⁿ·n) | O(n) | O(2ⁿ·n²) | O(2ⁿ·n) | — |
| 状态压缩 DP(集合划分) | O(2ⁿ) | O(n) 或 O(2ⁿ) | O(2ⁿ·n) | O(2ⁿ) | — |
估算时最容易出错的三处:
- 把状态数当成一维。 写成 O(n) 而实际是 O(n·C) 或 O(n²),导致规模上界判断错误。
- 忽略转移代价中的内层枚举。 区间 DP 的三重循环、状态压缩的逐元素枚举都计入转移代价,遗漏后会把 O(n³) 写成 O(n²)。
- 忽略常数项的实际影响。 状态数相同时,数组访问与哈希访问的常数差异可达一个数量级(3.2.5 节),类型为
long的运算比int略慢,多维数组的维度顺序影响缓存命中。
3.4.2 空间与时间优化的实测
复杂度分析给出的空间与时间结论是量级层面的,具体的优化收益需要实测确认。三类需要实测的场景:
| 优化 | 预期效果 | 需要实测确认的问题 |
|---|---|---|
| 滚动数组(二维降一维) | 空间降一个量级 | 对时间的影响方向不确定:一维数组的复用改善了缓存命中,但增加了临时变量与额外的赋值,小规模下可能变慢 |
| 记忆化改为递推 | 去掉递归与函数调用开销 | 当状态空间稀疏时,递推要计算全部状态,反而可能更慢 |
| 单调队列 / 斜率优化 | 转移代价降一个量级 | 常数量级增大(队列操作、凸壳维护),交叉规模以下不如朴素版本 |
实测方法。 微基准需要控制预热、固定数据规模与分布、隔离分叉进程、消费计算结果以避免死代码消除,具体设计(预热与测量轮次分离、黑洞、分叉隔离、参数化展开、结果判读)见 JMH 微基准测试。动态规划还需要额外控制两点:
- 数据规模必须覆盖交叉点。 滚动数组与朴素二维实现在小规模下的排序可能反转,只在单一规模上测量无法得出可用结论。
- 数据分布需要覆盖最优/最坏/随机三类。 状态转移的分支预测行为与数据相关,随机数据会掩盖差异。
结论表述。 应同时给出规模、数据分布、优化前后的实现与测量数值,例如"在容量 10⁴、200 件物品的随机数据上,一维实现的时间与二维实现接近,峰值内存约为其 1/200"。缺少条件的结论(如"滚动数组更快")不可复用。
3.5 工程应用
动态规划在工程中很少以"算法题"的形式出现,而是嵌入在容量规划、字符串处理、调度与定价等场景中,作为其中一步的最优化。
3.5.1 资源分配与预算分配
| 场景 | 状态 | 转移 | 目标 |
|---|---|---|---|
| 预算分配到多个项目 | 项目编号、已用预算 | 每个项目选择投入档位 | 总收益最大 |
| 服务器资源分配到服务 | 服务编号、已分配 CPU/内存 | 每个服务选择实例规格 | 满足 SLA 的前提下成本最低 |
| 存储容量规划 | 业务编号、已用容量 | 每类数据选择副本数与介质 | 成本与可靠性的权衡 |
| 广告预算投放 | 时段、剩余预算 | 每个时段选择出价档位 | 转化数最大 |
这类问题的结构是"多重背包":每个对象有多个可选档位,总资源有限,求总收益最大。工程中的额外约束(整数规格、阶梯定价、上下限)通常表现为转移的可行域变化,而不改变模型结构。
工程落点与纯算法题的差别:
- 规模约束。 预算以分为单位时容量维度可达 10⁶ 以上,直接开二维数组不可行。应对方式包括:按最小分配粒度离散化、合并档位、采用"交换存什么与求什么"的状态重设计(2.6.6 节)。
- 约束的优先级。 工程中常有硬约束(合规、容量上限)与软约束(成本、时延)。硬约束通过状态定义(设为不可行)表达,软约束通过代价函数表达,两者不应混在同一个转移项里。
- 结果需要解释。 纯算法只需最优值,工程通常需要给出分配方案。此时必须保留方案信息(完整状态表、前驱数组或正推还原),不能在空间压缩后丢弃。
3.5.2 字符串相似度与模糊匹配
编辑距离是字符串相似度的基础度量,工程中的用法有三层:
- 直接比较:以编辑距离衡量两个字符串的相似程度,用于拼写纠错、名称匹配、脏数据归并。
- 带权编辑距离:不同操作的代价不同(插入常见词代价低、替换形近字符代价低),转移不变,只改代价常数项。
- 结合索引:在词表上做模糊匹配时,若对每个候选词都算一次编辑距离,代价与词表规模成正比。索引结构用于把候选集合先缩小,再在缩小后的集合上算编辑距离。
字符串集合的组织方式(共享前缀、前缀查询、最长前缀匹配)与编辑距离在模糊匹配中的分工见 字典树与字符串索引 中关于三类字符串查询的划分。工程上的常见分工是:用索引(前缀树、倒排索引、n-gram 索引)把候选从百万级降到千级,再用编辑距离或相似度函数在候选内排序。把编辑距离直接用在全量数据上是代价与效果都不划算的做法。
编辑距离的复杂度为 O(n·m),在长文本比较中不可接受。工程上的替代方案包括:长度差过滤(长度差大于阈值时直接排除)、公共前缀/后缀剪枝、只计算对角带(带式编辑距离)、使用近似的相似度度量(如 Jaccard、SimHash)。
3.5.3 路径与工序的最优安排
| 场景 | 模型 | 状态 |
|---|---|---|
| 车间工序安排 | 区间 DP / 状态压缩 | 已完成工序集合、当前机器状态 |
| 装配顺序优化 | 状态压缩(TSP 变体) | 已安装零件集合、当前工位 |
| 版本升级路径 | DAG 最长路 / 最短路 | 当前版本及其依赖满足情况 |
| 网络报文分段 | 线性 DP | 已发送字节数 |
这些场景的共同结构是"在一组先后有序或相互依赖的操作中,选择总代价最小的执行序列"。当工序数在 20 以内时,状态压缩是可行的精确解法;超过该规模后状态空间迅速膨胀,需要转向启发式(贪心、局部搜索)或借助问题特有的结构(如工序间无交叉依赖时退化为区间 DP)。
3.5.4 库存与定价类决策
| 场景 | 状态 | 决策 |
|---|---|---|
| 库存补货 | 期数、当前库存量 | 每期补货量 |
| 动态定价 | 期数、剩余库存、当前价格档 | 每期定价 |
| 生产计划 | 期数、库存、产能占用 | 每期生产量 |
| 期权与投资 | 期数、持仓、资金 | 每期买卖 |
这类问题在运筹学中称为多阶段决策问题,状态通常包含"时间"与"存量"两维。要点:
- 状态维度小但范围大。 库存量的取值范围可能很大,需要按最小包装量离散化,或把"存量"维度改为"已满足的累计需求"。
- 决策的可行域随状态变化。 产能上限、库存上下限、批次下限都属于此,需在枚举决策时判断可行性,而不是靠代价函数惩罚。
- 逆推与正推的选择。 若终态的边界条件明确(期末库存必须为零),逆推更自然;若初始状态明确,正推更自然。两者的转移方程相同,只是遍历方向相反。
3.5.5 任务调度中的最优化
操作系统的调度器与定时任务系统都需要在"一批待执行任务"与"有限的执行资源"之间做出选择。相关的场景与机制见 linux: 计划任务与定时器:cron 的固定时间点触发与 systemd timer 的单调时钟与随机延迟,都涉及"何时执行"与"如何避免集中触发"的取舍。
动态规划在这一领域的可用形态有三层:
| 层次 | 问题 | 动态规划的适用性 |
|---|---|---|
| 离线批量调度 | 已知全部任务的到达时间与时长,求最小化总延迟或最大吞吐的顺序 | 适用,状态为"已完成任务集合"(状态压缩)或"前 k 个任务 + 当前时刻"(线性 DP) |
| 单机顺序调度 | 已知任务时长与截止期,求可行或最优顺序 | 特定目标下可用 DP;多数变体是 NP-hard,需用贪心(如最早截止期优先)或近似算法 |
| 在线调度 | 任务到达时间未知 | 不适用,动态规划需要已知的全部状态空间;改用优先级规则或队列管理 |
这一对比说明了动态规划的适用边界: 它要求状态空间可以在决策前被枚举。在线场景中未来状态未知,动态规划无从建立状态表,只能改用贪心规则或队列管理。反之,离线场景中若已知全部输入,动态规划可以给出精确最优解(在状态空间可承受的前提下)。
3.6 常见误用与排查
| 误用 | 表现 | 成因 | 纠正 |
|---|---|---|---|
| 状态定义遗漏信息 | 小数据正确、大数据偏小;结果系统性优于或劣于正确答案 | 决策所需的历史信息未纳入状态 | 检查"做出下一步决策时需要知道哪些量",把缺失信息并入状态或重新定义状态含义(2.2.1 节) |
| 转移顺序错误 | 结果依赖数据顺序,或与暴力结果不一致;某些规模下出现明显偏差 | 计算某状态时其依赖的状态尚未计算(原地滚动或内层方向写反) | 先写出二维版本确认正确,再按依赖方向(2.3.1 节)改写为一维;用对拍验证(3.1.2 节) |
| 初始化不当 | 求最大值的结果偏大;不可达状态被当作有效解 | 把哨兵值初始化为 0,或边界值方向写反 | 确认"0 是否可能是真实最优值";不可达状态用 -INF/INF,且哨兵值避免加法溢出(3.2.2 节) |
| 遗漏"不选当前元素"的决策 | 答案偏小;子序列类问题结果恒为最短 | 转移方程只写了"选中"的分支 | 逐一检查每个状态的全部合法决策,确认"跳过/不选"分支存在(2.2.2 节) |
| 空间压缩后遍历方向写错 | 0-1 背包解出完全背包的结果;物品被重复选取 | 内层循环方向与"是否允许同层复用"不匹配 | 一维化后确认 dp[v - w] 是本层值还是上一层值(2.4.2 节) |
| 复杂度估算错误导致超时 | 小规模通过,目标规模超时或内存溢出 | 把状态数或转移代价少算一维 | 按"状态数 × 转移代价"逐项写出表达式,与目标规模对照(3.4.1 节) |
| 计数问题重复统计 | 方案数偏大 | 同一方案由多条转移路径到达 | 为转移规定唯一的"最后一步",或规定元素的选取顺序(2.5.8 节) |
| 计数问题溢出 | 结果出现负数或与预期不符 | 未取模或取模位置不当 | 每次加法后取模,减法先加模数(3.2.4 节) |
| 边界循环范围过窄 | 部分状态未被计算,答案偏小 | 内层循环下界未考虑 v < w[i] 等无意义区间 | 核对循环上下界与转移式中的下标引用(3.2.3 节) |
| 下标偏移混用 | 结果整体偏移一位 | 在同一个函数中混用"1 起始语义下标"与"0 起始数组下标" | 统一约定,或使用哨兵前导字符(3.2.1 节) |
| 备忘录键碰撞 | 结果随机错误 | 多维状态编码为整数时未保证单射 | 编码时预留各维上界(如乘数取 m + 1)(3.2.5 节) |
| 用可变对象作缓存键 | 缓存不命中或键失联 | 对象被修改后哈希值改变 | 使用不可变类型作为键(3.2.5 节) |
| 忽略递归深度 | 数据规模未到先出现栈溢出 | 记忆化递归的深度等于依赖链长度 | 评估最坏深度;改为递推或显式栈 |
| 把最优值当方案输出 | 只能给出数值,无法给出选择 | 空间压缩后中间状态被覆盖 | 保留完整状态表、前驱数组,或正推还原 |
| 环形结构未拆解 | 首尾相邻约束不生效 | 直接在线性状态上加约束 | 拆成"不含首元素"与"不含末元素"两个线性问题取最优(3.3.6 节) |
排查顺序。 出现"结果与预期不符"时的检查顺序:
- 确认规模。改用 n ≤ 10 的小规模输入,看结果是否仍然错误。若小规模正确,问题多半在状态范围、溢出或空间压缩;若小规模也错,问题在状态定义或转移方程。
- 与暴力对拍。用随机小规模数据跑 1000 轮以上,定位第一组不一致的输入(3.1.2 节)。
- 打印状态表。对不一致的那组输入,以二维表格形式打印中间状态,观察哪一行的数值开始偏离暴力结果——偏离的第一处即错误转移的位置。
- 检查边界。逐一核对第 0 行、第 0 列与不可达状态的初值。
- 检查方向。确认内层循环方向与"是否允许同层复用"一致。
- 检查完整性。确认每个状态枚举了全部决策分支。
- 检查规模与类型。确认状态数表达式与目标规模匹配,数值类型足以容纳中间结果。
3.7 检查清单与学习路径
3.7.1 建模自检清单
状态设计。
- 状态的含义能否用一句不含"并且已经……"的自然语言表述?若必须引入历史限定,无后效性可能不成立。
- 状态是否覆盖了做出决策所需的全部信息?是否存在两个在状态定义下无法区分、但后续最优值不同的局面?
- 是否存在可由其他维度推出的冗余维度?
- 状态数是否与目标规模匹配?是否可通过对换"存什么"与"求什么"降低维度?
转移方程。
- 每个状态是否枚举了全部合法决策?"不选/跳过"分支是否存在?
- 每一项转移能否对应到一个明确的决策?无法对应的项通常是笔误。
- 计数型问题中,同一方案是否只被一条转移路径统计?
- 转移中是否遗漏了对不可达状态的判断?
边界与初始化。
- 最小规模子问题的值是否正确?
dp[0]、第 0 行、第 0 列的语义是否明确? - 求最大值时初始化为 0 是否安全(0 是否可能是真实最优值)?
- 哨兵值是否会因加法而溢出?
- "恰好装满"与"至多容量"的初始化差别是否已确认?
遍历与实现。
- 遍历顺序是否保证依赖状态已计算?区间类问题是否按长度递增?
- 空间压缩后内层方向是否与"同层是否复用"一致?
- 循环上下界是否覆盖全部有效状态且不越界?
- 语义下标与数组下标的换算是否统一?
- 数值类型是否足以容纳中间结果?计数问题是否全员取模?
答案与验证。
- 答案的取法是否正确(
dp[n]、全状态最值、特定维度组合,还是终态求和)? - 是否用小规模暴力对照验证过?随机测试是否覆盖极端形态(全相同、严格增减、大量重复值)?
- 每一处优化是否与未优化版本对拍通过?
- 复杂度表达式是否与目标规模匹配?是否需要滚动数组或转移优化?
3.7.2 学习路径
模型之间的依赖关系决定了推进顺序:后面的模型通常在前面模型的基础上增加一个维度或改变一种状态语义。
第一层:一维线性
斐波那契、爬楼梯、打家劫舍
—— 建立"状态 + 转移 + 边界"的基本框架,理解空间压缩到常数
第二层:二维线性与序列匹配
0-1 背包、最长公共子序列、编辑距离
—— 建立二维状态与双维度推进,理解一维化的方向规则
第三层:背包族变体
完全背包、多重背包、分组背包、二维费用背包
—— 理解循环顺序与状态语义的对应关系,把"模型"与"实现技巧"分开
第四层:线性 DP 的取法与优化
最长递增子序列、最大子段和、前缀和优化、单调队列
—— 理解"答案取法"与"转移代价优化",掌握辅助结构维护窗口最值
第五层:区间 DP
石子合并、最长回文子序列、矩阵链乘
—— 理解按长度递增的遍历顺序与分割点枚举,接触决策单调性
第六层:状态机 DP 与树形 DP
买卖股票系列、树上最优选择、树的直径
—— 理解"把约束变成状态维度"与"沿树后序合并"
第七层:状态压缩 DP
旅行商、集合划分、覆盖问题
—— 理解用位掩码表示集合、指数级状态空间的边界与小规模精确求解
第八层:计数与概率
方案数计数、期望值递推
—— 理解取模、去重与逆推方向
第九层:高级优化与状态重设计
斜率优化、四边形不等式、分治优化、交换"存什么与求什么"
—— 理解优化的判定条件与代价,掌握"先朴素后优化并全程对拍"的工作方式
推进过程中的三条做法。
- 每个模型先写出朴素版本并跑通对拍,再考虑优化。优化后的正确性单独验证。
- 记录每个模型的"结构特征"而非代码:状态含义、转移中出现的决策、遍历顺序的确定依据。代码可以重写,结构特征才是迁移能力。
- 遇到新问题时先做模型识别:问题中的"决策"是什么,"阶段"是什么,"约束"需要几个维度表达。多数新问题是已知模型增加一个维度或替换一种状态语义的结果。
四、总结
定位。 动态规划处理的是"子问题重叠、需要枚举决策"的最优化与计数问题。它把指数级的重复计算压缩为"每个状态只算一次",代价是存储状态的空间。它不改变问题的难度类别:对 NP-hard 问题,动态规划给出的是在状态空间可枚举前提下的精确解。
适用条件。 最优子结构(整体最优由子问题最优构成)、无后效性(状态确定后后续与历史无关)、重叠子问题(缓存有收益)三项条件必须同时满足。前两项依赖状态定义,因此"该问题能否用动态规划"这一判断必须与状态定义一起给出。最优子结构不成立的反例是最长简单路径;无后效性不成立时,出路是把历史并入状态或重新定义状态。
状态设计。 状态是"足以决定后续决策的最小信息"。维度由决策所需的信息确定,状态数与单状态转移代价的乘积决定复杂度。转移方程必须枚举全部决策,尤其不能遗漏"不选"的分支。初始化必须区分"0 是真实最优值"与"0 是哨兵"两种情形。答案的位置取决于状态的语义,通常不是 dp[n] 而需要按取法规则确定。
实现方式。 记忆化递归与递推填表共享同一套状态与转移,差别在计算范围、栈开销、常数与空间压缩的便利程度。递推的硬性约束是遍历顺序必须满足依赖关系:线性 DP 正序、区间 DP 按长度递增、树形 DP 后序、状态压缩按掩码递增。空间压缩的前提是"只依赖有限前层",压缩后的遍历方向必须与"同层是否复用"一致——0-1 背包倒序、完全背包正序,这是同一模型的两个不同问题。
模型族。 线性 DP、背包(0-1 与完全与多重与分组)、区间 DP、序列匹配(LCS 与编辑距离)、状态机 DP、树形 DP、状态压缩 DP、计数与概率型 DP 覆盖了绝大多数变形。新问题通常是这些模型增加一个状态维度或替换一种状态语义的结果,模型识别的效率取决于对既有模型的熟悉程度。
优化。 优化从"减少状态数"与"降低转移代价"两条路径入手。转移侧的手段按适用条件排序:前缀和(区间求和)、单调队列(窗口最值、转移项可分离)、斜率优化(转移含 i·j 交叉项)、四边形不等式(代价函数满足区间包含单调性与四边形不等式)。判定条件不满足时这些优化会给出错误结果,因此每一步优化都必须与朴素版本对拍。
边界。 与贪心的差别在于是否保留多个候选,贪心的正确性需要证明,失效可用"局部最优占用后续资源"的反例检验;与分治的差别在于子问题是否重叠;与搜索的分工由状态空间能否枚举决定,在线场景无法建立状态表时只能用规则或启发式;与最短路等价——状态即顶点、转移即边,状态转移无环时按拓扑序递推,有环时退化为一般最短路问题,需按边权特征选择算法。
工程落点。 动态规划在工程中作为容量规划、字符串相似度、工序与路径安排、库存与定价、离线调度等场景中的最优化环节出现。与算法题的差别集中在四点:规模约束需要状态离散化或状态重设计;硬约束与软约束应分别用状态定义与代价函数表达;需要输出方案时必须保留回溯信息;在线与离线场景的可用性截然不同。
常见误用。 状态遗漏信息、转移顺序错误、初始化不当、遗漏"不选"分支、空间压缩后方向写错、复杂度估算漏掉一个维度、计数重复与溢出、下标换算混用,是最集中的八类缺陷。排查从"缩小规模并与暴力对拍"开始,定位到第一处状态偏离后,按边界、方向、完整性、类型与规模的顺序检查。
动态规划的核心工作不在编码,而在状态设计。编码层面的错误大多可以定位,状态层面的错误则表现为结果的系统性偏差。把状态含义写成一句话、把转移决策逐条列出、把每一处优化都与朴素版本对拍,是避免这类偏差的三项基本做法。