动态规划
01 / 共享的机制
一张表格逐格填充自己 —— 每一格都由 常数个更早的格子组合而来。递推关系因子模式而异, 但底层机制 —— 状态、转移、填表顺序 —— 是共通的。
02 / 一句话本质
状态是一个子集,用位掩码表示。每次转移把一个元素加入集合。 关键是认清:元素被选的顺序不重要,只有哪些被选才重要 —— 这把N!的搜索缩减为2^N个不同状态。
题目N 个任务分配给 N 个工人的最小代价输入cost = [7, 4, 3, 3, 1, 2, 5, 8, 6]
代价
7T0·W0
4T0·W1
3T0·W2
3T1·W0
1T1·W1
2T1·W2
5T2·W0
8T2·W1
6T2·W2
dp[mask]
0000
∞001
∞010
∞011
∞100
∞101
∞110
∞111
dp[mask] = 把任务 0..popcount(mask)−1 分配给 mask 表示的工人时的最小代价。从 dp[0] = 0 开始,其余为 ∞。按位数升序遍历 2^3 个 mask。
步
0 / 32
mask
—
已填 mask
1 / 8
dp[全]
∞
0 / 32
03 / 模式骨架
# 分配问题 —— 按 popcount 升序填表dp[0] ← 0dp[mask] ← ∞ for mask ≠ 0for mask in 0..(2^N − 1):k ← popcount(mask) # 下一个待分配下标for j in 0..N−1 if j 不在 mask:dp[mask | (1 << j)] ← min(dp[mask | (1 << j)], dp[mask] + cost[k][j])return dp[(1 << N) − 1] # 所有元素都已放置
04 / 什么时候用这个模式
"N ≤ 20"
约束说 N 很小(通常 15–20),而答案需要枚举每个子集 —— 强烈暗示
2^N 个状态可行。"为每个分配 / 选齐所有"
"为每个任务指派工人"、"访问每个节点"、"覆盖每项技能" 这类题面 —— 答案只取决于哪些被选,不依赖顺序。
"对排列求 min / max / 计数"
朴素解是
N! 种排列,且代价是逐元素累加的 —— 位掩码 DP 共享前缀,把它缩到 O(2^N · N)。"Hamiltonian / TSP"
Held-Karp 模板:
dp[mask][i] = 访问 mask 中节点、 以 i 结尾的最短路径。当转移代价依赖当前末位时, 额外的 i 维度是必需的。05 / 常见坑
遍历 mask 的顺序错。
必须在写入
dp[mask | bit] 之前先访问 dp[mask](前向 DP)—— 因为 mask < mask | bit,顺序升序就对。 但若转移会去掉位或双向走,需按 popcount 排序。忘了 popcount → 元素下标的对应。
常见框架是"第 k 个被分配的元素在位置
popcount(mask)"。 这里 off-by-one 不会报错,只是悄悄分配重了或漏了 —— 答案不对而已。把 mask 当有序序列。
mask 记的是哪些元素在集合里,不是它们被加入的顺序。 若答案依赖顺序(比如"最后访问的节点"),就要加一个
i 维度, 单 mask 不够。j 枚举范围搞反:遍历
mask 还是 ~mask。常见笔误:本该枚举未设置位却枚举了设置位(或反之)。 用
if (mask & (1 << j)) 判定归属,反向就翻转条件。06 / 去 LeetCode 上练习
中等8
01Can I Win— LC 464→02Matchsticks to Square— LC 473→03Beautiful Arrangement— LC 526→04Partition to K Equal Sum Subsets— LC 698→05Campus Bikes II— LC 1066→06Maximum Compatibility Score Sum— LC 1947→07Minimum Number of Work Sessions to Finish the Tasks— LC 1986→08Fair Distribution of Cookies— LC 2305→
困难12
01Stickers to Spell Word— LC 691→02Shortest Path Visiting All Nodes— LC 847→03Find the Shortest Superstring— LC 943→04Number of Squareful Arrays— LC 996→05Smallest Sufficient Team— LC 1125→06Maximum Students Taking Exam— LC 1349→07Parallel Courses II— LC 1494→08Distribute Repeating Integers— LC 1655→09Minimum Incompatibility— LC 1681→10Find Minimum Time to Finish All Jobs— LC 1723→11Maximize Score After N Operations— LC 1799→12Minimum XOR Sum of Two Arrays— LC 1879→
— / 什么时候用哪个
一维线性
当下标 i 处的答案只依赖常数个更早的下标时使用。
打家劫舍 · 爬楼梯 · 最大子段和
二维网格
当状态由两个下标组成 —— 网格,或两条相互作用的序列。
最短路径 · LCS · 编辑距离
背包
当每个物品都触发一次选 / 不选决策、且有容量约束时使用。
子集和 · 找零 · 划分
区间
当状态是一个区间
(i, j)、答案由内部区间组合得出时使用。回文 · 矩阵链 · 戳气球
状态机
当每个下标可以处于若干有限状态之一、且状态之间有明确的转移规则时使用。
股票 · 冷冻期 · 双状态
树形 DP
当问题定义在树上、且每个节点的答案依赖其子节点答案时使用。
打家劫舍 III · 二叉树直径 · 最大路径和
位掩码
当状态是子集(通常
N ≤ 20),且只关心选了哪些、不关心顺序时使用。分配 · TSP · 最小覆盖团队