illegalCreed

中文

English

中文

English

Appearance

入门：四大进阶 DP 模型与何时用哪个 ​

基于通用算法概念 · 核于 2026-07

速查 ​

  • 进阶 DP 的本质：把 DP 从「一维序列」推广到树、数位、可换根的树、位掩码集合四类复杂结构——核心难点不在写代码，而在为每类结构找到正确的计算顺序。
  • 树形 DP：状态挂在树的节点上 f[u]，用后序遍历（DFS）从叶到根递推——先算所有子节点，再合并到父节点。典型：树的最大独立集、树的直径、树的最长链。
  • 数位 DP：把一个数按位拆开，逐位 DP + 记忆化，关键标志 limit（当前位是否受上界约束）。用于统计区间 [L,R] 内满足某条件（不含 62、数位之和等）的数个数，复杂度 O(位数 × 状态)。
  • 换根 DP：解决「以每个节点为根时的答案」。朴素是每个根各跑一次 O(n²)，换根 DP 用两次 DFS——第一次以任一点为根求「向下」子树解 down，第二次从根换到子节点用父的 up 贡献，总共 O(n)。
  • 状态压缩 DP：用**位掩码（整数）**把「集合」压成一个状态维度，f[mask][i] 表示「已访问集合 mask、当前在 i」的最优值。典型：旅行商问题（TSP），复杂度 O(2ⁿ · n²)，n ≤ 20 可用。
  • 树形 DP 的计算顺序：后序 DFS（先递归子节点，回溯时合并）——这是「树上拓扑序」的自然体现，父永远在子之后算。
  • 数位 DP 的 limit 标志：某位 limit=true 表示前面各位都顶到了上界，本位取值不能超过上界对应位；limit=false 表示前面已比上界小，本位 0~9 随便取。limit=true 的状态少，记忆化时通常把 limit 也作为维度或单独不记。
  • 换根 DP 的两步：①第一遍 DFS 求 down[u]（u 向下子树内的最优解）；②第二遍 DFS 用父节点 v 的总答案扣掉 u 的贡献得到 up[u]（u 从父那边来的部分），up[u]+down[u] 即以 u 为根的答案。
  • 状压 DP 的位运算：mask | (1<<i) 加入元素 i；mask & (1<<i) 测试 i 是否在集合；mask ^ (1<<i) 删除。枚举子集 for(sub=mask; sub; sub=(sub-1)&mask)。
  • 何时用哪种：树上的最优化/计数 → 树形 DP；区间内满足数位条件的计数 → 数位 DP；「对每个根求答案」→ 换根 DP；集合/连通性/哈密顿路 → 状压 DP。
  • DP 优化引入（思想层面）：单调队列优化（转移是一段区间的最值）、斜率优化（转移可写成线性式的斜率比较）、矩阵快速幂（线性递推加速到 O(log n)）。
  • 复杂度直觉：树形 DP O(n)/O(n²)；数位 DP O(log R × 状态数)；换根 DP O(n)；状压 DP O(2ⁿ · n)。
  • 进阶顺序：树形 DP 与数位 DP → 换根 DP 与 DP 优化 → 参考。

一、树形 DP：状态挂树上，后序从叶到根 ​

线性 DP 的状态是一维下标 f[i]，状态之间靠「下标顺序」天然有拓扑序。但树不是线性的——树形 DP 把状态挂在节点上 f[u]，状态的依赖关系是「父依赖子」，所以计算顺序必须是后序 DFS：先递归进每个子节点算完，回溯时再把所有子节点的 f[child] 合并成 f[u]。

text
dfs(u):
  for v in u.children:
    dfs(v)            # 先把子节点全算完
  f[u] = 合并(f[v] for v in u.children)  # 回溯时合并

典型应用：

  • 树的最大独立集：选若干节点使任意两节点不相邻，求权值和最大。f[u][0/1] 表示「u 不选/选」时子树的最优——f[u][1] = w[u] + Σ f[v][0]，f[u][0] = Σ max(f[v][0], f[v][1])。
  • 树的直径：树上最长的简单路径。维护 d[u]（u 出发的最长下行链），直径 = max(d[u] + 次长下行链)。

二、数位 DP：按位拆解，逐位 DP + limit 标志 ​

统计「[1, R] 内满足某数位条件（不含 62、数位和等于 S、单调不降等）的数有多少个」——这类问题用传统枚举 O(R) 必爆，但一个数的位数只有 log R 级别。数位 DP 把数按位拆开，从高位到低位逐位确定，用记忆化避免重复。

核心难点是 limit 标志：

  • limit=true：前面各位都顶到了上界 R 的对应位，本位取值不能超过 R 的当前位。
  • limit=false：前面已有某位比 R 小，本位 0~9 随便取。
text
dfs(pos, limit, ...其它状态):
  if pos == 位数: return 1   # 成功填完一个数
  up = limit ? R[pos] : 9    # 本位上界
  ans = 0
  for d in 0..up:
    if 满足本位的约束:
      ans += dfs(pos+1, limit && d==up, ...)
  return ans

记忆化时通常把 pos 和其它状态记下来；limit=true 的分支因为「沿上界走」路径唯一、数量少，常不记忆化或把 limit 作为维度。

三、换根 DP：两次 DFS 求每个根的答案 ​

问题：「以树中每个节点为根时，某指标（如最大深度、子树大小和、最大距离）的值是多少」。朴素做法是枚举每个根各跑一次树形 DP，共 O(n²)。换根 DP 把它优化到 O(n)：

  1. 第一次 DFS（求 down）：任选一个根（如 0），跑一遍树形 DP，求出 down[u]（u 向子树内的最优解）。
  2. 第二次 DFS（换根求 up）：从根往下 DFS，对每个子节点 u，利用父节点 v 的完整答案减去「u 这棵子树对 v 的贡献」，得到 u 从父方向上得到的 up[u]。up[u] + down[u] 就是以 u 为根的答案。
text
dfs1(u, fa):           # 第一遍：求 down
  for v in u.children if v != fa:
    dfs1(v, u)
    down[u] = 合并(down[u], down[v])

dfs2(u, fa):           # 第二遍：换根，用父的答案推子的 up
  for v in u.children if v != fa:
    up[v] = (up[u] + down[u]) 扣掉 v 这棵子树对 u 的贡献
    dfs2(v, u)

典型：求每个节点为根时的最大深度、子树大小之和、树中最远距离。

四、状态压缩 DP 入门：位掩码当集合 ​

当状态里要记录「一个集合的子集」时，直接用数组维度无法表达。状压 DP 用整数的二进制位表示集合——第 i 位为 1 表示元素 i 在集合里。这样 mask（一个整数）就是一个状态维度。

最经典的是旅行商问题（TSP）：f[mask][i] = 已访问集合为 mask、当前在城市 i 时的最短路径。转移：f[mask | (1<<j)][j] = min(f[mask][i] + dist[i][j])。答案 f[(1<<n)-1][起点]。复杂度 O(2ⁿ · n²)，n ≤ 20 可行。

text
f[1<<start][start] = 0
for mask in 1..(1<<n)-1:
  for i in 0..n-1 if mask & (1<<i):
    for j in 0..n-1 if not (mask & (1<<j)):
      f[mask|(1<<j)][j] = min(f[mask|(1<<j)][j], f[mask][i] + dist[i][j])

五、何时用哪种进阶 DP 模型 ​

题目特征选用的模型
在树上求最优化 / 计数（树的直径、最大独立集）树形 DP
统计区间 [L,R] 内满足数位条件的数个数数位 DP
「以每个节点为根时的答案」换根 DP
涉及集合 / 连通性 / 哈密顿路，n ≤ 20状压 DP

记忆口诀：树上的问题用树形，数位的计数用数位，每个根都要答案用换根，集合小用状压。

下一步 ​

理解了四大模型的定位后，下一步先吃透两类最常考的模型——树形 DP（后序从叶到根）与数位 DP（逐位 + limit），见树形 DP 与数位 DP。