02.7.2 区间树形与状态压缩 DP
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.7 动态规划
这个知识域解决什么问题
结构型与特殊状态的 DP 专题。本知识域分四块:区间 DP → 树形 DP → 状态压缩 DP → 数位 DP 与其他;覆盖连续区间合并、树上自底向上、集合掩码、逐位计数与概率/期望/博弈变体。
知识地图
区间 DP(1)
→ 树形 DP(2)
→ 状态压缩 DP(3)
→ 数位 DP 与其他(4)
子主题
| 编号 | 子主题 | 核心内容 | 题数 |
|---|---|---|---|
| 02.7.2.1 | 区间 DP | 区间状态与长度外层、分割点枚举、石子合并、戳气球、矩阵链乘、回文区间、博弈区间、破环为链、O(n³) 口径 | 20 |
| 02.7.2.2 | 树形 DP | 后序状态挂载、选/不选两状态、最大路径和、打家劫舍 III、直径、独立集/点覆盖、多叉聚合、树上背包 | 20 |
| 02.7.2.3 | 状态压缩 DP | 掩码集合表示、位运算、TSP、Hamilton 路径、行型放置、合法状态预处理、2ⁿ 规模估算与选型 | 20 |
| 02.7.2.4 | 数位 DP 与其他 | 逐位计数、tight/leading、前缀差分、数位和与相邻约束、概率/期望 DP、博弈胜负态、INF 选取与综合选型 | 20 |
合计 80 题。 每题按「一句话结论 → 概念解释 → 原理流程(含状态定义与转移链) → 代码/图示 → 常见误区 → 追问(带答案)」组织;代码以 Java 为主,标注复杂度口径。
学习路径
先 1 掌握区间长度外层与分割点转移,再 2 练熟树形后序两状态合并,3 理解掩码状态压缩与规模上限,最后 4 拓展数位、概率、期望、博弈等变体 DP。
自检
- [ ] 能按区间长度外层填表,枚举分割点并算区间合并代价
- [ ] 能写树形 DP 后序返回选/不选状态,处理多叉聚合
- [ ] 能用位掩码表示集合并实现 TSP 类转移
- [ ] 能判断 2ⁿ 状态规模是否可行
- [ ] 能写数位 DP 的 tight/leading 状态与前缀差分
- [ ] 能区分概率、期望、博弈 DP 的转移口径
- [ ] 每题能报出状态数、转移代价与空间口径