动态规划进阶：区间、状压与树形
一句话定义
进阶 DP 把状态定义从「一维前缀」扩展到三个常用维度：区间 DP 以 [i,j] 为状态处理合并/分割类问题；状态压缩（Bitmask）DP 用整数二进制位表示「已访问集合」处理子集类问题（如 TSP，O(n²·2ⁿ)）；树形 DP 在树上自叶向根做无后效性聚合（如树的最大独立集）。
为什么重要
「会一维 DP」到「会建模」之间隔着这三座桥：它们回答「子问题天然不是前缀时怎么办」——区间、集合、子树就是三种最常见的答案。TSP 的 2ⁿ 也是「指数级子问题数 × 多项式转移」仍优于暴力全排列 n! 的量化案例，让你对「DP 是搜空间的智能剪裁」有体感。
前置知识
kp-026（四步法与滚动优化）；kp-031（位运算——状压的实现语言）；kp-011（树的遍历顺序，供树形 DP）。
核心概念
- 区间 DP：状态 dp[i][j] = 区间 [i,j] 的最优值；转移枚举分割点 k：dp[i][j] = min/max(dp[i][k] + dp[k+1][j] + cost(i,j))；遍历顺序按区间长度从小到大。
- 矩阵链乘法：n 个矩阵的最少乘法次数，是区间 DP 的原型，Θ(n³)。
- 状压 DP：状态含一个集合位 mask ∈ [0, 2ⁿ)；n ≤ 20~24 是工程上限（2²⁴≈1.6×10⁷）。
- TSP（旅行商）：dp[S][j] = 已访问集合 S、当前在 j 的最小代价；转移自 S∖{j} 的任意 i。
- 子集枚举技巧：
sub = (sub − 1) & S从 S 开始倒序枚举全部非空子集，均摊每个集合 3ⁿ 次访问而非 4ⁿ。 - 树形 DP：以节点为状态、孩子聚合；常配「选/不选」两维（如没有上司的舞会）；依赖父无环保证无后效性。
- 常见优化：前缀和去一重（区间）、单调队列（滑动窗口最值，O(n)）、位运算并行（状压内层）。
原理与机制
三类进阶 DP 共享「换一种子问题划分」的机制：区间 DP 以「区间最后一步如何合并」为转移（枚举分割点 k），并按区间长度从小到大填表，保证转移依赖的更短区间已算好；状压 DP 把「已访问集合」编码成整数二进制位，集合运算降为位运算，转移即「点亮某一位」时取最优来源；树形 DP 用自叶向根的后序聚合规避父依赖，无后效性由树的天然层次保证。
直观类比
区间 DP 像合并石子：任何大堆的最后一步都是「两小堆合成一堆」，所以先算所有小堆的代价表，再按堆大小升格。状压 DP 像「背包挂一排指示灯表示城市去没去过」，转移就是哪盏灯点亮时走来最省。树形 DP 像「从班组往上报数据」，每个节点只汇总孩子的报表。
公式或模型
- 区间 DP 通用骨架：
对于 len 从 2 到 n: // 长度从小到大
对于 i 从 0 到 n−len: j ← i + len − 1
dp[i][j] ← min over k ∈ [i, j−1] of dp[i][k] + dp[k+1][j] + cost(i,j)- TSP：dp[S][j] = min over i ∈ S∖{j} of dp[S∖{j}][i] + w(i,j)；答案 min_j dp[全集][j] + w(j,起点)。复杂度 Θ(2ⁿ·n²)；n=20 约 4×10⁸ 可过，n=25 已不可过——这就是状压的边界感。
- 树最大独立集：dp[u][0] = Σ max(dp[c][0], dp[c][1])；dp[u][1] = w(u) + Σ dp[c][0]。
图示
区间 DP 填表方向（按长度）:
len=1: dp[0][0] dp[1][1] … （对角线，初始化）
len=2: dp[0][1] dp[1][2] … ← 只看 len=1
len=3: dp[0][2] … ← 依赖 len=1 与 len=2
↑ 整张表沿「对角线层」推进，k 是最后一步的分界点。
TSP 状态（n=4）: dp[1011₂][2] = 已访问 {0,1,3}、现在城市 2 的最短路径长
转移: dp[1011][2] ← min( dp[0011][0]+w(0,2), dp[0011][1]+w(1,2), dp[1010][3]+w(3,2) )实例或案例
- 石子合并/戳气球（LeetCode 312）：区间 DP + 边界处理（戳气球「逆向最后一个戳破」的经典转化）。
- 矩阵链乘法（CLRS 14 章）：区间 DP 原型，Θ(n³)。
- TSP 与「n ≤ 20 的覆盖类计数」（壮志难酬集合覆盖）：状压；配套「枚举子集的子集」3ⁿ 技巧。
- 没有上司的舞会/树的最大独立集：树形 DP 双状态模板；树上背包（依赖背包）是其进阶。
常见误区
- 区间 DP 按左端点外层循环：导致转移依赖的更短区间尚未算出；必须按长度分层。
- 状压不控制 n：n=30 时 2ⁿ 已 10⁹ 级且乘 n² 直接爆炸，需识别可换 meet-in-middle/启发式的场景。
- 枚举子集写成四重循环：O(4ⁿ) 超时；用
(sub−1)&S技巧压到 O(3ⁿ)。 - 树形 DP 把「无后效性」想当然：若状态缺「父方向信息」（换根 DP），答案会依赖遍历顺序，需二次换根。
- 把能贪心的题硬写区间 DP：先看数据范围再定设计。
自测题
- 写出石子合并（只能合并相邻堆）的状态与转移。
答案要点：dp[i][j] = min over k of dp[i][k]+dp[k+1][j]+sum(i,j)；sum 用前缀和 O(1) 取；Θ(n³)。
- n=20 的 TSP 状压 DP 状态数与转移总数各是多少？
答案要点：状态 2²⁰×20 ≈ 2×10⁷；每状态转移 20 次 ⇒ 约 4×10⁸ 次基本操作，量级可过。
- 为什么枚举「S 的子集」用
(sub−1)&S是 O(3ⁿ) 而不是 O(4ⁿ)？
答案要点：每个 (S, sub) 对恰被枚举一次，按每位「在 S / 在 sub / 都在」计数归结为 3ⁿ。
与其他知识点的关系
kp-026 的四步法是全部进阶的地基；kp-031 提供状压的位运算语言；kp-027 回溯常与状压 DP 在「小 n 搜索」题中互为替代（剪枝版回溯 vs 记表 DP）；kp-016 的树上遍历序支撑树形 DP 的实现。
延伸阅读
《算法导论》矩阵链乘一节；《算法竞赛入门经典》状态压缩 DP 与树形 DP 章节；LeetCode 312/847/337 对照三类模板。