罗罗编程学习记录
本页内容 展开查看

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 的转移口径
  • [ ] 每题能报出状态数、转移代价与空间口径