illegalCreed

中文

English

中文

English

Appearance

换根 DP 与 DP 优化 ​

基于通用算法套路 · 核于 2026-07

速查 ​

  • 换根 DP 解决什么：「以树中每个节点为根时，某指标（最大深度、子树大小之和、最远距离）的值」。朴素是每个根各跑一次树形 DP = O(n²)，换根 DP 优化到 O(n)。
  • 换根 DP 两步走：①第一遍 DFS 求 down[u]——任选根（如 0），后序求每个 u 向下子树内的解；②第二遍 DFS 求 up[u]——从根往下，用父的完整答案扣掉 u 这棵子树对父的贡献，得到 u 从父方向来的部分。
  • 换根 DP 的关键操作：「扣除子贡献」——父 v 的总答案里有一部分来自 u 的子树，换根时要把这部分减掉再传给 u，否则会重复计算。
  • 最终答案：以 u 为根的答案 = down[u] + up[u]（向下子树 + 向上父方向的贡献合并）。
  • 换根 DP 复杂度：两遍 DFS 各 O(n)，总共 O(n)。
  • DP 优化引入（思想层面，不深入）：
    • 单调队列优化：当转移是「一段长度固定的滑动区间的最值 / 和」时，用单调队列把区间查询从 O(n) 降到 O(1)，整体降一维。
    • 斜率优化：当转移方程能写成 f[i] = min(g(j) + h(i)·k(j)) 的线性形式时，维护凸包用斜率单调性把 O(n²) 降到 O(n log n) 或 O(n)。
    • 矩阵快速幂加速：当转移是线性递推（如斐波那契、爬楼梯）时，把递推写成矩阵乘法，用快速幂把 O(n) 降到 O(k³ log n)。
  • 何时用哪种优化：转移含定长区间最值 → 单调队列；转移是线性式且可整理成斜率比较 → 斜率优化；线性递推求第 n 项（n 极大）→ 矩阵快速幂。
  • 状态压缩 DP 衔接：集合小（n ≤ 20）时用位掩码当状态，见入门第四节。
  • 进阶顺序：换根 DP 两遍 DFS → DP 优化思想 → 状态压缩 DP 完整模型 → 综合识别。

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

「以每个节点为根时的答案」这类问题，朴素做法是枚举 n 个根各跑一次 O(n) 的树形 DP，共 O(n²)。换根 DP 的洞察：相邻两个根（父子）的答案只差一个「换根」的贡献调整，所以可以一遍求 down、一遍从上往下「推」出每个根的答案，共 O(n)。

核心思路 ​

以「求每个节点为根时，到所有节点的距离之和」为例（经典换根题）：

  1. 第一遍 DFS（求 down / size）：以 0 为根，后序求 size[u]（u 子树大小）和 down[u]（以 0 为根时 u 子树内所有节点到 u 的距离之和）。
  2. 第二遍 DFS（换根求 ans）：从 0 往下推。已知 ans[0] = down[0]，对 0 的子节点 v：当根从 0 换到 v 时，v 子树内所有节点（size[v] 个）距离各减 1，其余节点（n - size[v] 个）距离各加 1。于是：
ans[v] = ans[u] - size[v] + (n - size[v])
js
// 第一遍：求 size 和 down
function dfs1(u, fa) {
  size[u] = 1;
  for (const [v, w] of adj[u]) {
    if (v === fa) continue;
    dfs1(v, u);
    size[u] += size[v];
    down[u] += down[v] + size[v] * w;   // v 子树每个点都多走 w
  }
}
// 第二遍：换根，ans[0]=down[0]，往下推
function dfs2(u, fa) {
  for (const [v, w] of adj[u]) {
    if (v === fa) continue;
    // 根从 u 换到 v：v 子树内 size[v] 个点距离 -w，其余 n-size[v] 个点 +w
    ans[v] = ans[u] - size[v] * w + (n - size[v]) * w;
    dfs2(v, u);
  }
}
dfs1(0, -1);
ans[0] = down[0];
dfs2(0, -1);
// ans[i] 即以 i 为根时所有节点到 i 的距离之和

何时用换根 DP ​

题面特征是「对树中每个节点（作为根）求某指标」。识别后套两遍 DFS 模板。其他典型题：以每个点为根时的树的最大深度、树中最远距离（配合树形 DP 的直径思路）、子树大小之和。

二、DP 优化思想引入 ​

基础/进阶 DP 模型的复杂度有时仍偏高，这里介绍三种优化思想（本叶只讲思想与适用场景，不深入实现）：

1. 单调队列优化 ​

当转移形如 f[i] = min/max(f[j]) + cost，其中 j 是 i 之前一段定长滑动区间 [i-k, i-1] 时，朴素每次扫区间 O(k)，整体 O(nk)。用单调队列维护这段区间的最值，每次 O(1) 取，整体降到 O(n)。

典型：滑动窗口最大值、多重背包的单调队列优化、跳跃游戏 IV。

2. 斜率优化 ​

当转移能整理成 f[i] = min(g(j) + h(i) · k(j))，把 g(j) 看成截距、k(j) 看成斜率、h(i) 看成变量，问题变成「在点集里找斜率最优的点」——用凸包 + 斜率单调性维护，把 O(n²) 降到 O(n log n) 或 O(n)。

典型：任务安排、仓库建设。数学味较重，是竞赛向的进阶技巧。

3. 矩阵快速幂加速 ​

当转移是线性递推（如斐波那契 f[n]=f[n-1]+f[n-2]、爬楼梯），且 n 极大（如 10¹⁸）时，把递推写成矩阵乘法形式，用快速幂在 O(k³ log n) 内求出第 n 项（k 是状态维数）。

典型：斐波那契第 n 项、线性递推数列加速、图上走恰好 k 步的路径计数。

三、何时用哪种进阶 DP 模型（完整决策） ​

题目特征选用模型关键标志
树上最优化 / 计数树形 DP后序 DFS、f[u]、fa 防回父
区间内满足数位条件的计数数位 DPpos、limit、记忆化
「以每个节点为根时的答案」换根 DP两遍 DFS、扣除子贡献
集合 / 连通性，n ≤ 20状压 DP位掩码 mask、2ⁿ 枚举
转移含定长区间最值单调队列优化滑动区间、单调队列
线性递推求第 n 项（n 极大）矩阵快速幂矩阵乘法、快速幂

交互演示 ​

下一步 ​

四类进阶 DP 模型与优化思想都已就绪，最后用一份速查参考把代码模板、模型识别决策树、易错点汇总，见参考。