进阶动态规划
进阶动态规划（Advanced Dynamic Programming）是把 DP 从「线性表 / 背包」推广到更复杂的结构维度的一类模型——当状态不再躺在一维数组上，而是挂在树的节点上、散在数位的每一位上、随根的更换而平移、或被位掩码压缩成一个整数时，基础的「两层 for 填表」就不够用了，必须为每一类结构定制状态的拓扑顺序与转移方式。它是 DP 三部曲（基础 → 序列区间 → 进阶）的收官篇：基础篇练的是「状态定义 + 转移方程」的基本功，序列区间篇练的是「二维状态与区间合并」，本叶则把 DP 的疆域扩展到树形结构、数位计数、换根统计、状态压缩四大模型。
进阶 DP 的全部考点都源于一个核心动作：为复杂结构找到正确的「计算顺序」。由此衍生出四大主题：①树形 DP（状态挂在树上，后序遍历从叶到根递推，求树的最大独立集 / 树的直径 / 树的最长链）；②数位 DP（把一个数按位拆开，逐位 DP + 记忆化 + limit 标志，统计 [L,R] 内满足某条件的数的个数）；③换根 DP（两次 DFS——第一次以任一点为根求「向下」的子树解，第二次从根换到子节点求「向上」的贡献，解决「以每个节点为根时的答案」）；④状态压缩 DP 入门（用位掩码把「集合」压缩成整数当状态维度，如旅行商问题 TSP）。其中树形 DP 是树的考点的绝对核心，数位 DP 的 limit 标志是最容易写错的细节，换根 DP 把「对每个根各跑一次 O(n)」优化成「两次 DFS 一共 O(n)」，状压 DP 则是连通性 / 哈密顿路问题的通用武器。掌握这四类模型后，再了解单调队列优化 / 斜率优化 / 矩阵快速幂加速等 DP 优化的思想，进阶 DP 的版图就基本完整了。
评价
优点
- 解决线性 DP 解决不了的题：树形 / 数位 / 换根 / 状压四类问题，线性 DP 根本无法建模——进阶模型把 DP 的适用面从「一维序列」扩到「任意结构」
- 模型高度可复用：树形 DP 的「后序 dfs + 子节点合并」、数位 DP 的「逐位 + 记忆化 + limit」、换根 DP 的「两遍 DFS」都是固定套路，认出模型就能套模板，套路识别后编码量并不大
- 状态压缩的降维打击：状压 DP 把指数级的「子集枚举」压成
O(2ⁿ · n)的可承受复杂度，是 NP-hard 问题（如 TSP）的精确解法 - 换根 DP 的巧妙优化：把朴素的「枚举每个根 O(n²)」优化到「两遍 DFS O(n)」，是 DP 思想在树统计问题上的优雅应用
缺点
- 模型识别门槛高：四大模型长得完全不一样，新手最难的不是写代码，而是「这道题该用树形 / 数位 / 换根 / 状压里的哪一个」——强依赖刷题积累的题感
- 数位 DP 细节极多：
limit（上界限制）、lead（前导零）、记忆化的维度与时机，任何一处写错都得不到正确答案，调试成本高 - 状压 DP 状态空间爆炸：
2ⁿ随n指数增长，n > 20基本不可用，且位运算代码可读性差、易写错 - DP 优化（单调队列 / 斜率）数学味重：斜率优化要维护凸包、判断斜率单调性，门槛高，初学者不易掌握
本叶地图
- 入门 —— 进阶 DP 的四大模型定位、树形 / 数位 / 换根 / 状压各自解决什么、何时用哪种模型
- 树形 DP 与数位 DP —— 树形 DP（后序 dfs 从叶到根、最大独立集 / 树的直径）、数位 DP（逐位 DP + 记忆化 + limit 标志、统计区间内不含 62 的数）
- 换根 DP 与 DP 优化 —— 换根 DP（两次 DFS 求 down / up、每个根的子树大小 / 最大距离）、DP 优化引入（单调队列 / 斜率 / 矩阵快速幂）
- 参考 —— 四类进阶 DP 模型对照表、树形 / 数位 / 换根代码模板、DP 模型识别决策树、易错点清单
交互演示
- 树形 DP 可视化演示 —— 后序遍历从叶到根的状态合并
- 数位 DP 可视化演示 —— 逐位 DP 与 limit 标志的传递
- 换根 DP 可视化演示 —— 两次 DFS 的 down 与 up 贡献