第 103 章 区间 DP、树形 DP、状压 DP¶
配套例题：BISHI145 石子合并、BISHI143 没有上司的舞会、BISHI144 食物链计数 来源：S3
day6/DP资料/进阶资料/树型动态规划七道题.md、day6/DP资料/进阶资料/DP例题选讲 by 罗翔宇.md、S4模板.docx（区间 DP、树型 DP「选课」、状压 DP）
前两章的 DP 都沿「一维序列」推进。这一章的三种形态换了推进的载体： 区间 DP 沿区间长度推进，树形 DP 沿子树推进，状压 DP 沿集合推进。 共同点是——枚举「最后一步」的技巧依然有效，只是「最后一步」的含义变了。
103.1 区间 DP¶
状态是一个区间 \([l, r]\)，转移枚举最后一次合并的断点。
枚举顺序必须按区间长度¶
\(f[l][r]\) 依赖的 \(f[l][k]\) 和 \(f[k+1][r]\) 都是更短的区间。所以外层必须枚举长度：
# [片段]
for length in range(2, n + 1): # 区间长度从小到大：短区间先算好，长区间才敢用
for l in range(1, n - length + 2): # 左端点上界由「右端点不越过 n」倒推而来
r = l + length - 1 # 长度为 length 的区间是 [l, r]，闭区间
for k in range(l, r): # 断点 k 取到 r-1：切成 [l,k] 与 [k+1,r] 两段非空
...
写成
for l: for r:的双层循环也可以，但必须 \(l\) 倒序、\(r\) 正序， 否则依赖没算好。按长度枚举更不容易错，推荐固定用这个写法。
环形区间：破环成链¶
若区间首尾相连（如「石子摆成一圈」），标准做法是把数组复制一倍变成长度 \(2n\) 的链， 再在所有长度为 \(n\) 的区间里取最优。
BISHI145 是链不是环，不需要复制。读题时要确认这一点。
BISHI145 石子合并（较难）¶
\(N\) 堆石子排成一排，每次合并相邻两堆、代价为两堆之和，求最小总代价。\(N \le 300\)。
最后那一项与断点 \(k\) 无关——无论怎么合，最后一次合并的代价一定是整段之和。 用前缀和 \(O(1)\) 取出。
复杂度：状态 \(O(N^2) = 9\times10^4\)，每个状态枚举 \(O(N)\) 个断点 ⇒ \(O(N^3) \approx 4.5\times10^6\)。
Python 关键：维护转置表把内层下沉 C 层¶
最内层的「枚举断点取 min」是 \(4.5\times10^6\) 次 Python 迭代，勉强能过但很险。 可以整段下沉，但需要同时维护一张转置表：
| 要取的数据 | 在 f 里 |
是否连续 |
|---|---|---|
| \(f[l][k]\)，\(k = l..r-1\) | f[l][l:r] —— 第 \(l\) 行的一段 |
✅ 连续 |
| \(f[k+1][r]\)，\(k = l..r-1\) | 第 \(r\) 列的一段 | ❌ 不连续 |
所以额外维护 fT[r][k+1] = f[k+1][r]，于是：
# [片段]
from operator import add
# f[l][l:r] 依次是 f[l][k]，k = l..r-1；fT[r][l+1:r+1] 依次是 f[k+1][r]，同一批 k
# map(add, ...) 逐位相加得到全部断点的候选值，min 一次取最小，两步都在 C 层
best = min(map(add, f[l][l:r], fT[r][l + 1:r + 1]))
map(add, ...) 把两个切片逐元素相加、min 取最小，全在 C 层。
每次更新 f[l][r] 时同步写一份 fT[r][l]。
代价是双倍内存和一次额外写入，换来内层循环从 Python 层挪到 C 层。 \(N = 300\) 时这个改写把耗时从约 3 秒降到 0.2 秒量级。
题解：solutions/BISHI145.py（已通过官方样例验证）
区间 DP 的其它经典模型¶
| 问题 | 状态与转移 |
|---|---|
| 括号匹配的最长合法子串 | \(f[l][r]\)，匹配则 \(f[l+1][r-1]+2\)，否则枚举断点 |
| 回文划分（最少切几刀） | \(f[i] = \min\{f[j] + 1\}\)，\(s[j+1..i]\) 是回文 |
| 矩阵链乘 | \(f[l][r] = \min f[l][k] + f[k+1][r] + p_{l-1}p_k p_r\) |
| 能量项链（环形） | 破环成链 |
103.2 树形 DP¶
状态是「某个子树」，转移由孩子的状态合并而来。
⚠️ Python 必须用迭代，不能递归¶
这是本章最重要的一条工程约束。
\(n \le 2\times10^5\) 的链状树，递归深度就是 \(2\times10^5\)：
| 做法 | 结果 |
|---|---|
| 直接递归 | RecursionError（默认上限 1000） |
sys.setrecursionlimit(300000) + 递归 |
爆 C 栈，段错误（判题机显示 RE，且没有 traceback） |
threading.stack_size(1<<26) + 线程内递归 |
✅ 可行 |
| 显式栈的迭代式后序遍历 | ✅ 推荐，通用姿势 |
setrecursionlimit 只解除了解释器的软限制，真正的物理限制是线程栈大小。
这是 Python 竞赛里最隐蔽的 RE 来源之一——本地小数据全过，判题机上大数据直接段错误。
迭代式后序遍历模板¶
# [片段]
# 通用写法：显式栈，用一个标记位区分「进入」与「回溯」
stack = [(root, -1, False)] # 三元组：结点、父结点、是否处于回溯阶段
while stack:
u, fa, back = stack.pop()
if back:
# 此时 u 的所有孩子都已处理完 —— 在这里做合并
for c in g[u]:
if c != fa: # 无向图里要靠父结点编号挡住「往回走」
merge(u, c)
else:
stack.append((u, fa, True)) # 先压回自己的回溯帧，它会在所有孩子之后被弹出
for c in g[u]:
if c != fa:
stack.append((c, u, False)) # 再压孩子，于是孩子先被处理
更快的写法（当输入直接给出有向父子边时）：只要按 BFS 序遍历一遍， 再倒着累加即可——子节点一定排在父节点后面，倒序就是合法的后序：
# [片段]
order = bfs_order(root) # 一次 BFS 得到层序：父结点一定排在孩子之前
for u in reversed(order): # 倒序 = 后序，连栈都不用
merge_into_parent(u) # 轮到 u 时它的子树已全部合并完毕
这个技巧避免了显式栈的元组打包开销，是树形 DP 在 Python 里的最优形态。 BISHI143 的输入天然给出「\(k\) 是 \(\ell\) 的上司」的有向父子边，正好适用。
BISHI143 没有上司的舞会（较难）¶
树上最大权独立集：选了某点就不能选它的父亲。\(n \le 2\times10^5\)，\(w_i \in [-128, 127]\)。
两个状态：
答案 \(= \max(g[\text{root}],\ f[\text{root}])\)。
坑：\(w_i\) 可以是负数，所以 \(g[u]\) 不一定优于 \(f[u]\)， 不能写成「叶子一定选」的贪心。\(f[u]\) 里对每个孩子取 \(\max(g[c], f[c])\) 而不是 \(g[c]\)， 就是因为孩子的权值可能为负、不选反而更好。
题解：solutions/BISHI143.py（已通过官方样例验证）
树形 DP 的常见状态设计¶
| 问题 | 状态 |
|---|---|
| 最大权独立集 | \(f[u][0/1]\)：\(u\) 选 / 不选 |
| 树的直径 | \(f[u]\) = 从 \(u\) 往下的最长链；答案在每个点合并两条最长链 |
| 树上背包（选课） | \(f[u][j]\) = 子树里选 \(j\) 个点。见 101-背包问题 §101.9 |
| 树的重心 | \(f[u]\) = 子树大小，重心是 \(\max(\text{最大子树},\ n - size_u)\) 最小的点 |
| 换根 DP | 两次遍历：先自下而上求子树内答案，再自上而下把「父亲方向」的贡献传下来 |
103.3 DAG 上的 DP¶
DAG 上 DP 与树形 DP 同源，但拓扑序取代了后序。
必须按拓扑序处理（或反拓扑序，取决于转移方向）。
BISHI144 食物链计数（较难）¶
求 DAG 上从「入度为 0 的点」到「出度为 0 的点」的路径条数。\(n, m \le 10^5\)。
答案 \(= \sum_{\text{入度为 0 的 } x} f[x]\)。
实现上按「出度」做 Kahn：先把出度为 0 的点入队；出队 \(v\) 时把 \(f[v]\) 累加给所有前驱 \(u\)， 并把 \(u\) 的出度减 1，减到 0 就入队。这样天然是逆拓扑序，不需要显式排序。
坑 1（最容易错）：方向别搞反。输入
u v表示「\(v\) 捕食 \(u\)」，即有向边 \(u \to v\)； 而 \(f\) 是沿边正向走到出度 0 的点的方案数，所以递推要用反向邻接表。坑 2：题面文字与样例说明略有出入（说明里把 8 也列成了生产者）。 以形式化定义为准：出度为 0 = 链的一端，入度为 0 = 链的另一端。 按样例验算 \(f(1) = 2+3+4 = 9\)，与期望输出一致，确认定义无误。
坑 3：孤立点（入度出度都是 0）自成一条链，计入答案 1——公式天然覆盖，不用特判。
题解：solutions/BISHI144.py（已通过官方样例验证）
DAG 上 DP 是本章唯一在 Python 里完全没有劣势的形态——纯线性、无嵌套循环。 拓扑排序模板见 93-拓扑排序与二分图。
103.4 状压 DP¶
用一个整数的二进制位表示「集合」，状态是这个整数。
适用条件：集合元素个数 \(n \le 20\) 左右（\(2^{20} \approx 10^6\) 个状态）。
常用位操作¶
见 46-位运算，这里列出状压 DP 专用的：
# [片段]
(mask >> i) & 1 # 第 i 个元素是否在集合里：把第 i 位挪到最低位再取出
mask | (1 << i) # 加入元素 i：或运算只会把该位置 1，其余位不动
mask & ~(1 << i) # 移除元素 i：取反后该位为 0，与运算把它清掉
mask & (mask - 1) # 移除最低位的 1：减一会翻转最低位 1 及其右边的全部 0
bin(mask).count("1") # 集合大小（3.9 写法；3.10+ 用 mask.bit_count()）
# 枚举 mask 的所有子集（含空集），O(2^popcount)
sub = mask # 从全集出发，逐个变小地枚举
while True:
... # 处理 sub
if sub == 0: # 空集也要处理，所以判空放在处理之后
break
sub = (sub - 1) & mask # 减一借位后再与 mask，跳到下一个更小的子集
枚举所有 mask 的所有子集，总复杂度是 \(O(3^n)\) 而不是 \(O(4^n)\)—— 每个元素有「在 mask 且在 sub」「在 mask 不在 sub」「不在 mask」三种状态。 \(n = 16\) 时 \(3^{16} \approx 4.3\times10^7\)，Python 下已经不行了。
两类经典状压¶
类型一：集合是「已选过哪些元素」
旅行商问题（TSP）：\(f[\text{mask}][i]\) = 走过集合 mask、当前在 \(i\) 的最短路。 \(O(2^n n^2)\)，\(n \le 15\) 时 Python 可行（\(7.4\times10^6\)）。
类型二：集合是「一行的状态」（棋盘类）
逐行推进，\(f[i][\text{mask}]\) = 前 \(i\) 行、第 \(i\) 行状态为 mask 的最优值。 行内合法性与行间兼容性都用位运算一次判完：
# [片段]
mask & (mask << 1) == 0 # 行内不相邻：左移一位后无公共 1
(m1 | (m1 << 1) | (m1 >> 1)) & m2 == 0 # 行间不相邻（含斜向）
# 上一行的每个 1 向左右各扩一位，覆盖正下方与两个斜下方，再与本行取交
solutions/BISHI79.py（取数游戏）用的正是这个套路。
Python 下的状压优化¶
| 手段 | 说明 |
|---|---|
| 预处理合法 mask 列表 | 先筛出行内合法的 mask，循环只跑这些（通常远少于 \(2^n\)） |
| 预处理兼容表 | ok[m1] = 与 \(m_1\) 兼容的 mask 列表，避免内层重复位运算 |
用 list 而不是 dict 存 \(f\) |
mask 是连续整数下标，list 快 2–3 倍 |
| 大整数当位集合 | 当「集合」超过 64 位时，Python 大整数天然是无限位 bitset，位运算走 C 层 |
最后一条是 Python 的独有优势：
solutions/BISHI4.py的两级值域位图就是这个思路的极致运用， 见 116-平衡树与有序集合。
103.5 计数 DP 与取模¶
三种形态都可能出计数版本（把 \(\min\)/\(\max\) 换成 \(+\)）。要点：
| 要点 | 说明 |
|---|---|
| 每步取模 | 否则大整数膨胀，见 100-DP入门 §100.7 |
| 「互不重叠 + 覆盖全部」 | 计数 DP 的正确性依据，必须显式检查 |
| 答案可能不需要取模 | BISHI144 保证答案 \(\le 10^9\)，Python 不溢出所以不用取模 |
| 最优值的方案数 | 同时维护 \(f\)（最优值）与 \(g\)（方案数）：更优则覆盖 \(g\)，相等则累加 \(g\) |
103.6 本章速查¶
| 形态 | 状态载体 | 枚举顺序 | 「最后一步」是什么 |
|---|---|---|---|
| 区间 DP | 区间 \([l,r]\) | 按长度从小到大 | 最后一次合并的断点 \(k\) |
| 树形 DP | 子树 | 后序（孩子先于父亲） | 每个孩子选哪个状态 |
| DAG DP | 点 | 拓扑序 / 逆拓扑序 | 走哪条出边 |
| 状压 DP | 集合 mask | mask 从小到大（子集先于超集） | 加入哪个元素 / 上一行是什么 |
| Python 关键 | 做法 |
|---|---|
| 树形 DP 绝不能递归 | 迭代后序，或「BFS 序倒序」 |
setrecursionlimit 不够 |
只解除软限制，物理栈仍会段错误 |
| 区间 DP 内层下沉 | 维护转置表 fT，用 min(map(add, f[l][l:r], fT[r][l+1:r+1])) |
| 状压枚举子集 | sub = (sub - 1) & mask，总量 \(O(3^n)\)，\(n \le 15\) 为限 |
| 状压存储 | 用 list 不用 dict |
| 超 64 位集合 | Python 大整数天然是 bitset，位运算走 C 层 |
| DAG DP | 本章唯一 Python 无劣势的形态 |
| 规模判据 | Python |
|---|---|
| 区间 DP \(O(n^3)\) | \(n \le 300\) ✅（内层下沉后）、\(n \le 500\) ⚠️ |
| 树形 DP \(O(n)\) | \(2\times10^5\) ✅（必须迭代） |
| 树上背包 \(O(n^2)\) | \(n \le 500\) ✅ |
| 状压 \(O(2^n n)\) | \(n \le 20\) ✅ |
| 状压 \(O(3^n)\) | \(n \le 15\) ✅、\(n = 16\) ❌ |