分享丨【算法题单】动态规划（入门/背包/划分/状态机/区间/状压/数位/树形/优化）

本文转载自力扣讨论区，作者：灵茶山艾府（endlesscheng）。原文链接：https://leetcode.cn/circle/discuss/tXLS3i/

前言

掌握动态规划（DP）是没有捷径的，咱们唯一能做的，就是投入时间猛猛刷题。好比学数学，只看书看视频而不做习题，是不能说学会的。

我能做的，是帮你节省找题的时间，并把这些题分类整理好。有着相同套路的题，一起做效率会更高，也更能领悟到 DP 的精髓。每个小节的题目已按照难度分排序（右侧数字为难度分）。

动态规划算法题 DP题单动态规划题单入门动态规划题目动态规划新手教程力扣DP 力扣动态规划 leetcode动态规划 leetcode dp 灵茶山艾府灵神灵神题单

记忆化搜索是新手村神器（甚至可以用到游戏后期），推荐先看动态规划入门：从记忆化搜索到递推。

但记忆化搜索并不是万能的，某些题目只有写成递推，才能结合数据结构等来优化时间复杂度，多数题目还可以优化空间复杂度。所以在写完记忆化搜索后，推荐把递推的代码也写一下。熟练之后直接写递推也可以。

有时候，思考「最后一步发生了什么」能启发我们找到子问题，进而得到状态定义和状态转移方程。

一、入门 DP

§1.1 爬楼梯

讲解

70. 爬楼梯
746. 使用最小花费爬楼梯约 1500
3693. 爬楼梯 II 1560 注意：虽然题目说下标从 $1$ 开始，但实际输入的数组还是从 $0$ 开始的
377. 组合总和 Ⅳ 约 1600
2466. 统计构造好字符串的方案数 1694
2266. 统计打字方案数 1857
2533. 好二进制字符串的数量（会员题）同 2466 题

§1.2 打家劫舍

答疑

问：在 1:1 翻译的过程中，如何根据记忆化搜索，确定递推数组（DP 数组）的大小？为什么有时候要开 $n + 1$ 大小的数组，有时候要开 $n + 2$ 大小的数组？

答：看记忆化搜索的参数的范围（最小值和最大值）。例如 $i$ 最小是 $- 1$ （递归边界也算），最大是 $n - 1$ （递归入口），那么一共有 $n + 1$ 个不同的 $i$ ，就需要开 $n + 1$ 大小的 DP 数组。如果 $i$ 最小是 $- 2$ ，最大是 $n - 1$ ，一共有 $n + 2$ 个不同的 $i$ ，就需要开 $n + 2$ 大小的 DP 数组。

思维扩展：

2140. 解决智力问题 1709

§1.3 最大子数组和（最大子段和）

有两种做法：

定义状态 $f [i]$ 表示以 $a [i]$ 结尾的最大子数组和，不和 $i$ 左边拼起来就是 $f [i] = a [i]$ ，和 $i$ 左边拼起来就是 $f [i] = f [i - 1] + a [i]$ ，取最大值就得到了状态转移方程 $f [i] = max (f [i - 1], 0) + a [i]$ ，答案为 $max (f)$ 。这个做法也叫做 Kadane 算法。
用前缀和，转化成 121. 买卖股票的最佳时机。

思维扩展：

思考题

完成本章后，请思考：什么时候要返回 $f [n]$ ，什么时候要返回 $max (f)$ ？

二、网格图 DP

对于一些二维 DP（例如背包、最长公共子序列），如果把 DP 矩阵画出来，其实状态转移可以视作在网格图上的移动。所以在学习相对更抽象的二维 DP 之前，做一些形象的网格图 DP 会让后续的学习更轻松（比如 0-1 背包的空间优化写法为什么要倒序遍历）。

讲解

§2.1 基础

思维扩展：

2684. 矩阵中移动的最大次数 1626
1824. 最少侧跳次数 1778

§2.2 进阶

三、背包

讲解：0-1 背包完全背包【基础算法精讲 18】

§3.1 0-1 背包

每个物品只能选一次，即要么选，要么不选。所以 0-1 背包是「选或不选」的代表。

关于「枚举选哪个」的代表，见本题单的「§4.2 最长递增子序列」。

进阶：

§3.2 完全背包

物品可以重复选，无个数限制。

思维扩展：

§3.3 多重背包（选做）

物品可以重复选，有个数限制。

求方案数

注意求方案数的题目不能用二进制优化。比如从 $6$ 个相同物品中选 $3$ 个，只有一种选法。但按照二进制优化，会把 $6$ 分解为 $1 + 2 + 3$ ，有 $1 + 2$ 和 $3$ 两种选法。

如果要优化，可以考虑用同余前缀和优化。

二进制优化

3489. 零数组变换 IV

§3.4 分组背包

同一组内的物品至多/恰好选一个。

§3.5 树上背包（选做）

注：目前力扣只有无依赖的背包，时间复杂度为 $O (n W^{2})$ ，其中 $n$ 是树的节点个数， $W$ 是背包容量。如果有依赖，可以优化到 $O (n W)$ 。

四、经典线性 DP

§4.1 最长公共子序列（LCS）

讲解：最长公共子序列编辑距离【基础算法精讲 19】

一般定义 $f [i] [j]$ 表示对 $(s [: i], t [: j])$ 的求解结果。

§4.1.1 基础

思维扩展：

718. 最长重复子数组

§4.1.2 进阶

思考题：

115 题的扩展。给定字符串 $s$ 和 $t$ ，你可以在 $s$ 的任意位置插入一个字母，插入后， $s$ 最多有多少个子序列等于 $t$ ？

思路和代码见评论。

§4.2 最长递增子序列（LIS）

讲解：最长递增子序列【基础算法精讲 20】

做法有很多：

枚举选哪个。（见讲解）
二分。（见讲解）
计算 $a$ 和把 $a$ 排序后的数组 $sortedA$ 的最长公共子序列。（用 LCS 求 LIS）
数据结构优化。（见 2407 题）

§4.2.1 基础

§4.2.2 进阶

思维扩展：

思考题：

给定整数 $k$ ，构造一个数组 $a$ ，使得 $a$ 恰好有 $k$ 个最长递增子序列。

解答（评论）

五、划分型 DP

§5.1 判定能否划分

一般定义 $f [i]$ 表示长为 $i$ 的前缀 $a [: i]$ 能否划分。

枚举最后一个子数组的左端点 $L$ ，从 $f [L]$ 转移到 $f [i]$ ，并考虑 $a [L : i]$ 是否满足要求。

§5.2 最优划分

计算最少（最多）可以划分出多少段、最优划分得分等。

一般定义 $f [i]$ 表示长为 $i$ 的前缀 $a [: i]$ 在题目约束下，分割出的最少（最多）子数组个数（或者定义成分割方案数）。

枚举最后一个子数组的左端点 $L$ ，从 $f [L]$ 转移到 $f [i]$ ，并考虑 $a [L : i]$ 对最优解的影响。

132. 分割回文串 II
2707. 字符串中的额外字符 1736
3196. 最大化子数组的总成本 1847 也有状态机 DP 做法
2767. 将字符串分割为最少的美丽子字符串 1865
91. 解码方法
639. 解码方法 II
LCR 165. 解密数字
1043. 分隔数组以得到最大和 1916
3144. 分割字符频率相等的最少子字符串 1917
1416. 恢复数组 1920
2472. 不重叠回文子字符串的最大数目 2013
1105. 填充书架 2014
2547. 拆分数组的最小代价 2020
3578. 统计极差最大为 K 的分割方式数 2033 优化
2430. 对字母串可执行的最大删除数 2102
2463. 最小移动总距离 2454
3579. 字符串转换需要的最小操作数 2493 可以做到 $O (n^{2})$
3500. 将数组分割为子数组的最小代价 2569 式子变形
2977. 转换字符串的最小成本 II 2696
3441. 变成好标题的最少代价 2765
2052. 将句子分隔成行的最低成本（会员题）
2464. 有效分割中的最少子数组数目（会员题）

§5.3 约束划分个数

将数组分成（恰好/至多） $k$ 个连续子数组，计算与这些子数组有关的最优值。

一般定义 $f [i] [j]$ 表示将长为 $j$ 的前缀 $a [: j]$ 分成 $i$ 个连续子数组所得到的最优解。

枚举最后一个子数组的左端点 $L$ ，从 $f [i - 1] [L]$ 转移到 $f [i] [j]$ ，并考虑 $a [L : j]$ 对最优解的影响。

注：对于恰好型划分 DP，可以通过控制内层循环的上下界，把时间复杂度从 $O (n k)$ 优化至 $O ((n - k) k)$ 。例如 3473 题。

六、状态机 DP

一般定义 $f [i] [j]$ 表示前缀 $a [: i]$ 在状态 $j$ 下的最优值。 $j$ 一般很小。

§6.1 买卖股票

讲解【基础算法精讲 21】

§6.2 基础

§6.3 进阶

七、其他线性 DP

§7.1 一维 DP

发生在前缀/后缀之间的转移，例如从 $f [i - 1]$ 转移到 $f [i]$ ，或者从 $f [j]$ 转移到 $f [i]$ 。

思维扩展：

4008. 击败所有怪物的最小初始强度 1776

§7.2 不相交区间

§7.3 子数组 DP

思维扩展：

§7.4 合法子序列 DP

计算合法子序列的最长长度、个数、元素和等。

一般定义 $f [x]$ 表示以元素 $x$ 结尾的合法子序列的最长长度/个数/元素和，从子序列的倒数第二个数转移过来。

注意这里的 $x$ 不是下标，是元素值。如果 $x$ 不是整数，或者值域范围很大，可以用哈希表代替数组。

思维扩展：

§7.5 子矩形 DP

§7.6 多维 DP

不会设计状态？那你可要好好刷这一节了。

思维扩展：

638. 大礼包

§7.7 计数 DP

八、区间 DP

讲解：区间 DP【基础算法精讲 22】

从数组的左右两端不断缩短，求解关于某段下标区间的最优值。

一般定义 $f [i] [j]$ 表示下标区间 $[i, j]$ 的最优值。

§8.1 最长回文子序列

§8.2 区间 DP

对于类似合法括号字符串（RBS）的消除问题，通常根据题意，会有如下性质：

可以消除相邻的匹配字符。
相邻匹配字符消除后，原本不相邻的字符会变成相邻，可以继续消除。换句话说，设子串 $A = x + B + y$ ，如果 $x$ 和 $y$ 是匹配的（可以消除），且子串 $B$ 可以完全消除，那么子串 $A$ 可以完全消除。
设子串 $A = B + C$ ，如果子串 $B$ 和 $C$ 可以完全消除，那么子串 $A$ 可以完全消除。

满足上述性质的题目（例如 3563 题），可以用区间 DP 解决。

定义 $f (i, j)$ 表示消除 $s [i]$ 到 $s [j]$ 的最优值。

根据性质 2，可以把 $f (i, j)$ 缩小成子问题 $f (i + 1, j - 1)$ 。
根据性质 3，可以枚举子串 $B$ 的右端点，即枚举 $k = i + 1, i + 3, i + 5, \dots, j - 2$ ，把 $f (i, j)$ 划分成子问题 $f (i, k)$ 和 $f (k + 1, j)$ 。注意这里枚举 $k$ 的步长是 $2$ ，因为每次消除 $2$ 个字符，被消除的子串长度一定是偶数。

边界： $f (i + 1, i)$ ，即空串。

答案： $f (0, n - 1)$ 。

还有一些区间 DP 问题，见本题单的「十四、博弈 DP」。

九、状态压缩 DP（状压 DP）

§9.1 排列型状压 DP ① 相邻无关

学习指南：

暴力做法是枚举所有排列，对每个排列计算和题目有关的值，时间复杂度（通常来说）是 $O (n!)$ 。可以解决 $n \leq 10$ 的问题。

状压 DP 可以把时间复杂度（通常来说）优化至 $O (n \cdot 2^{n})$ 。可以解决 $n \leq 20$ 的问题。

一般有两种定义方式：

定义 $f [S]$ 表示已经排列好的元素（下标）集合为 $S$ 时，和题目有关的最优值。通过枚举当前位置要填的元素（下标）来转移。
定义 $f [S]$ 表示可以选的元素（下标）集合为 $S$ 时，和题目有关的最优值。通过枚举当前位置要填的元素（下标）来转移。

注：部分题目由于暴搜+剪枝也能过，难度分仅供参考。

§9.2 排列型状压 DP ② 相邻相关

一般定义 $f [S] [i]$ 表示未选（或者已选）的集合为 $S$ ，且上一个填的元素（下标）为 $i$ 时，和题目有关的最优值。通过枚举当前位置要填的元素（下标）来转移。

时间复杂度（通常来说）是 $O (n^{2} \cdot 2^{n})$ 。

§9.3 旅行商问题（TSP）

本质上就是排列型 ②。

相似问题：

§9.4 子集状压 DP

一般定义 $f [S]$ 表示未选（或者已选）的集合为 $S$ 时，和题目有关的最优值。通过枚举 $S$ （或者 $S$ 的补集 $∁_{U} S$ ）的子集来转移。

时间复杂度（通常来说）是 $O (3^{n})$ ，证明：

对于大小为 $n$ 的集合，它的大小为 $m$ 的子集有 $(\binom{n}{m})$ 个，每个子集又有 $2^{m}$ 个子集。根据二项式定理， $\sum_{m = 0}^{n} (\binom{n}{m}) 2^{m} = (2 + 1)^{n} = 3^{n}$ ，所以「枚举子集的子集」的总体时间复杂度为 $O (3^{n})$ 。

注：某些网格图的题也可以用「选或不选」来做，从而减少状态个数，详见「§9.5 轮廓线 DP」。

2305. 公平分发饼干 1887
1986. 完成任务的最少工作时间段 1995
3670. 没有公共位的整数最大乘积 2234
1723. 完成所有工作的最短时间 2284
1655. 分配重复整数 2307
3444. 使数组包含目标值倍数的最少增量 2337
3575. 最大好子树分数 2360
1349. 参加考试的最大学生数 2386
1681. 最小不兼容性 2390 有 $O (n^{2} \cdot 2^{n})$ 做法
3801. 合并有序列表的最小成本 2399
2572. 无平方子集计数 2420
1994. 好子集的数目 2465
1494. 并行课程 II
LCP 04. 覆盖
LCP 53. 守护太空城
465. 最优账单平衡（会员题）
2152. 穿过所有点的所需最少直线数量（会员题）

相关问题：

3594. 所有人渡河所需的最短时间 2604

§9.5 轮廓线 DP

思维扩展：

756. 金字塔转换矩阵 1990

§9.6 SOS DP

子集和 DP（Sum Over Subsets DP，SOS DP），国内算法竞赛圈一般叫高维前缀和。

原理讲解（方法二）

模板（从子集转移过来）：

# 设 w 为 a[i] 的二进制最大长度
# 返回一个长为 2^w 的数组 f，其中 f[S] 表示 a 中是 S 的子集的元素个数（把二进制数视作集合）
# 时间复杂度 O(n + U log U)，其中 U = max(a)
def sos_dp(a: List[int]) -> List[int]:
    mx = max(a)
    w = mx.bit_length()  # 二进制长度上限
    u = 1 << w

    f = [0] * u
    for x in a:
        f[x] += 1  # 初始值

    for i in range(w):
        bit = 1 << i
        s = 0
        while s < u:
            s |= bit  # 优化：快速跳到 i 位是 1 的 s
            f[s] += f[s ^ bit]
            s += 1
    return f

java

class Solution {
    // 设 w 为 a[i] 的二进制最大长度
    // 返回一个长为 2^w 的数组 f，其中 f[S] 表示 a 中是 S 的子集的元素个数（把二进制数视作集合）
    // 时间复杂度 O(n + U log U)，其中 U = max(a)
    public int[] sosDP(int[] a) {
        int mx = 0;
        for (int x : a) {
            mx = Math.max(mx, x);
        }

        int w = 32 - Integer.numberOfLeadingZeros(mx); // 二进制长度上限
        int[] f = new int[1 << w];
        for (int x : a) {
            f[x]++; // 初始值
        }

        for (int i = 0; i < w; i++) {
            for (int s = 0; s < (1 << w); s++) {
                s |= 1 << i; // 优化：快速跳到 i 位是 1 的 s
                f[s] += f[s ^ (1 << i)];
            }
        }
        return f;
    }
}

cpp

// 设 w 为 a[i] 的二进制最大长度
// 返回一个长为 2^w 的数组 f，其中 f[S] 表示 a 中是 S 的子集的元素个数（把二进制数视作集合）
// 时间复杂度 O(n + U log U)，其中 U = max(a)
vector<int> sos_dp(vector<int>& a) {
    int mx = ranges::max(a);
    int w = bit_width((uint32_t) mx); // 二进制长度上限

    vector<int> f(1 << w);
    for (int x : a) {
        f[x]++; // 初始值
    }

    for (int i = 0; i < w; i++) {
        for (int s = 0; s < (1 << w); s++) {
            s |= 1 << i; // 优化：快速跳到 i 位是 1 的 s
            f[s] += f[s ^ (1 << i)];
        }
    }
    return f;
}

// 设 w 为 a[i] 的二进制最大长度
// 返回一个长为 2^w 的数组 f，其中 f[S] 表示 a 中是 S 的子集的元素个数（把二进制数视作集合）
// 时间复杂度 O(n + U log U)，其中 U = max(a)
func sosDP(a []int) []int {
    mx := slices.Max(a)
    w := bits.Len(uint(mx)) // 二进制长度上限

    f := make([]int, 1<<w)
    for _, x := range a {
        f[x]++ // 初始值
    }

    for i := range w {
        for s := 0; s < 1<<w; s++ {
            s |= 1 << i // 优化：快速跳到 i 位是 1 的 s
            f[s] += f[s^1<<i]
        }
    }
    return f
}

模板（从超集转移过来）：

# 设 w 为 a[i] 的二进制最大长度
# 返回一个长为 2^w 的数组 f，其中 f[S] 表示 a 中是 S 的超集的元素个数（把二进制数视作集合）
# 时间复杂度 O(n + U log U)，其中 U = max(a)
def sos_dp(a: List[int]) -> List[int]:
    mx = max(a)
    w = mx.bit_length()  # 二进制长度上限
    u = 1 << w

    f = [0] * u
    for x in a:
        f[x] += 1  # 初始值

    for i in range(w):
        bit = 1 << i
        s = 0
        while s < u:
            s |= bit  # 优化：快速跳到 i 位是 1 的 s
            f[s ^ bit] += f[s]
            s += 1
    return f

java

class Solution {
    // 设 w 为 a[i] 的二进制最大长度
    // 返回一个长为 2^w 的数组 f，其中 f[S] 表示 a 中是 S 的超集的元素个数（把二进制数视作集合）
    // 时间复杂度 O(n + U log U)，其中 U = max(a)
    public int[] sosDP(int[] a) {
        int mx = 0;
        for (int x : a) {
            mx = Math.max(mx, x);
        }

        int w = 32 - Integer.numberOfLeadingZeros(mx); // 二进制长度上限
        int[] f = new int[1 << w];
        for (int x : a) {
            f[x]++; // 初始值
        }

        for (int i = 0; i < w; i++) {
            for (int s = 0; s < (1 << w); s++) {
                s |= 1 << i; // 优化：快速跳到 i 位是 1 的 s
                f[s ^ (1 << i)] += f[s];
            }
        }
        return f;
    }
}

cpp

// 设 w 为 a[i] 的二进制最大长度
// 返回一个长为 2^w 的数组 f，其中 f[S] 表示 a 中是 S 的超集的元素个数（把二进制数视作集合）
// 时间复杂度 O(n + U log U)，其中 U = max(a)
vector<int> sos_dp(vector<int>& a) {
    int mx = ranges::max(a);
    int w = bit_width((uint32_t) mx); // 二进制长度上限

    vector<int> f(1 << w);
    for (int x : a) {
        f[x]++; // 初始值
    }

    for (int i = 0; i < w; i++) {
        for (int s = 0; s < (1 << w); s++) {
            s |= 1 << i; // 优化：快速跳到 i 位是 1 的 s
            f[s ^ (1 << i)] += f[s];
        }
    }
    return f;
}

// 设 w 为 a[i] 的二进制最大长度
// 返回一个长为 2^w 的数组 f，其中 f[S] 表示 a 中是 S 的超集的元素个数（把二进制数视作集合）
// 时间复杂度 O(n + U log U)，其中 U = max(a)
func sosDP(a []int) []int {
    mx := slices.Max(a)
    w := bits.Len(uint(mx)) // 二进制长度上限

    f := make([]int, 1<<w)
    for _, x := range a {
        f[x]++ // 初始值
    }

    for i := range w {
        for s := 0; s < 1<<w; s++ {
            s |= 1 << i // 优化：快速跳到 i 位是 1 的 s
            f[s^1<<i] += f[s]
        }
    }
    return f
}

§9.7 其他状压 DP

十、数位 DP

用于解决 $[ℓ, r]$ 范围内有多少个符合要求的元素，或者符合要求的元素之和等问题。

§10.1 统计合法元素的数目

数位 DP v1.0 模板讲解

数位 DP v2.0 模板讲解（上下界数位 DP）

问：下面的代码，为什么只在 !limitLow && !limitHigh 成立时才记忆化？（Python 选手可以跳过这个问题）

答：记忆化的原理是，当我们再次遇到相同状态时，可以直接返回 $memo$ 中保存的结果。数位 DP 本质是暴力枚举，枚举每个数位填什么。 $low$ 是我们枚举的第一个数， $high$ 是我们枚举的最后一个数。所以「填入的数字组成了 $low$ 」以及「填入的数字组成了 $high$ 」在整个递归过程中只会枚举一次。状态 $(\dots, limitLow, limitHigh)$ 中的 $limitLow$ 和 $limitHigh$ 如果其中一个是 $true$ ，说明我们正在填 $low$ 或者正在填 $high$ ，这样的状态只会出现一次，不会再次遇到，所以不需要记忆化这种状态。

下面是数位 DP v2.1 模板。相比 v2.0，不需要写 $isNum$ 参数（之前是否填过数字）。

注：只有上界约束的题目，相当于 $low = 0$ 或者 $low = 1$ 。

# 代码示例：返回 [low, high] 中的恰好包含 target 个 0 的整数个数
# 比如 digitDP(0, 10, 1) == 2
# 要点：我们统计的是 0 的个数，需要区分「前导零」与「整数中的零」，前导零不能计入，而整数中的零需要计入
def digitDP(low: int, high: int, target: int) -> int:
    low_s = list(map(int, str(low)))  # 避免在 dfs 中频繁调用 int()
    high_s = list(map(int, str(high)))
    n = len(high_s)
    diff_lh = n - len(low_s)

    @cache
    def dfs(i: int, cnt0: int, limit_low: bool, limit_high: bool) -> int:
        if cnt0 > target:
            return 0  # 不合法
        if i == n:
            return 1 if cnt0 == target else 0

        lo = low_s[i - diff_lh] if limit_low and i >= diff_lh else 0
        hi = high_s[i] if limit_high else 9

        res = 0
        start = lo

        # 通过 limit_low 和 i 可以判断能否不填数字，dfs 无需 is_num 参数
        # 如果前导零不影响答案，去掉这个 if block
        if limit_low and i < diff_lh:
            # 不填数字，上界不受约束
            res = dfs(i + 1, 0, True, False)
            start = 1  # 下面填数字，从 1 开始填

        # is_num = not limit_low or i > diff_lh
        for d in range(start, hi + 1):
            res += dfs(i + 1,
                       cnt0 + (1 if d == 0 else 0),  # 统计 0 的个数
                       limit_low and d == lo,
                       limit_high and d == hi)

        # res %= MOD
        return res

    return dfs(0, 0, True, True)

java

// 代码示例：返回 [low, high] 中的恰好包含 target 个 0 的整数个数
// 比如 digitDP(0, 10, 1) == 2
// 要点：我们统计的是 0 的个数，需要区分「前导零」与「整数中的零」，前导零不能计入，而整数中的零需要计入
class Solution {
    public long digitDP(long low, long high, int target) {
        char[] lowS = String.valueOf(low).toCharArray();
        char[] highS = String.valueOf(high).toCharArray();

        int n = highS.length;
        long[][] memo = new long[n][target + 1];
        for (long[] row : memo) {
            Arrays.fill(row, -1);
        }

        return dfs(0, 0, true, true, lowS, highS, target, memo);
    }

    private long dfs(int i, int cnt0, boolean limitLow, boolean limitHigh, char[] lowS, char[] highS, int target, long[][] memo) {
        if (cnt0 > target) {
            return 0; // 不合法
        }
        if (i == highS.length) {
            return cnt0 == target ? 1 : 0;
        }

        if (!limitLow && !limitHigh && memo[i][cnt0] >= 0) {
            return memo[i][cnt0];
        }

        int diff = highS.length - lowS.length;
        int lo = limitLow && i >= diff ? lowS[i - diff] - '0' : 0;
        int hi = limitHigh ? highS[i] - '0' : 9;

        long res = 0;
        int d = lo;

        // 通过 limitLow 和 i 可以判断能否不填数字，dfs 无需 isNum 参数
        // 如果前导零不影响答案，去掉这个 if block
        if (limitLow && i < diff) {
            // 不填数字，上界不受约束
            res = dfs(i + 1, 0, true, false, lowS, highS, target, memo);
            d = 1; // 下面填数字，从 1 开始填
        }

        // boolean isNum = !limitLow || i > diffLH;
        for (; d <= hi; d++) {
            res += dfs(i + 1,
                       cnt0 + (d == 0 ? 1 : 0), // 统计 0 的个数
                       limitLow && d == lo,
                       limitHigh && d == hi,
                       lowS, highS, target, memo);
            // res %= MOD;
        }

        if (!limitLow && !limitHigh) {
            memo[i][cnt0] = res;
        }
        return res;
    }
}

cpp

// 代码示例：返回 [low, high] 中的恰好包含 target 个 0 的整数个数
// 比如 digitDP(0, 10, 1) == 2
// 要点：我们统计的是 0 的个数，需要区分「前导零」与「整数中的零」，前导零不能计入，而整数中的零需要计入
long long digitDP(long long low, long long high, int target) {
    string low_s = to_string(low);
    string high_s = to_string(high);
    int n = high_s.size();
    int diff_lh = n - low_s.size();
    vector memo(n, vector<long long>(target + 1, -1));

    auto dfs = [&](this auto&& dfs, int i, int cnt0, bool limit_low, bool limit_high) -> long long {
        if (cnt0 > target) {
            return 0; // 不合法
        }
        if (i == n) {
            return cnt0 == target;
        }

        if (!limit_low && !limit_high && memo[i][cnt0] >= 0) {
            return memo[i][cnt0];
        }

        int lo = limit_low && i >= diff_lh ? low_s[i - diff_lh] - '0' : 0;
        int hi = limit_high ? high_s[i] - '0' : 9;

        long long res = 0;
        int d = lo;

        // 通过 limit_low 和 i 可以判断能否不填数字，dfs 无需 is_num 参数
        // 如果前导零不影响答案，去掉这个 if block
        if (limit_low && i < diff_lh) {
            // 不填数字，上界不受约束
            res = dfs(i + 1, 0, true, false);
            d = 1; // 下面填数字，从 1 开始填
        }

        // bool is_num = !limit_low || i > diff_lh;
        for (; d <= hi; d++) {
            // 统计 0 的个数
            res += dfs(i + 1, cnt0 + (d == 0), limit_low && d == lo, limit_high && d == hi);
            // res %= MOD;
        }

        if (!limit_low && !limit_high) {
            memo[i][cnt0] = res;
        }
        return res;
    };

    return dfs(0, 0, true, true);
}

// 代码示例：返回 [low, high] 中的恰好包含 target 个 0 的整数个数
// 比如 digitDP(0, 10, 1) == 2
// 要点：我们统计的是 0 的个数，需要区分「前导零」与「整数中的零」，前导零不能计入，而整数中的零需要计入
func digitDP(low, high int, target int) int {
    lowS := strconv.Itoa(low)
    highS := strconv.Itoa(high)
    n := len(highS)
    diffLH := n - len(lowS)
    memo := make([][]int, n)
    for i := range memo {
        memo[i] = make([]int, target+1)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }

    var dfs func(int, int, bool, bool) int
    dfs = func(i, cnt0 int, limitLow, limitHigh bool) (res int) {
        // 不合法
        if cnt0 > target {
            return 0
        }
        if i == n {
            // 不合法
            if cnt0 < target {
                return 0
            }
            // 合法
            return 1
        }
        if !limitLow && !limitHigh {
            p := &memo[i][cnt0]
            if *p >= 0 {
                return *p
            }
            defer func() { *p = res }()
        }

        lo := 0
        if limitLow && i >= diffLH {
            lo = int(lowS[i-diffLH] - '0')
        }
        hi := 9
        if limitHigh {
            hi = int(highS[i] - '0')
        }

        d := lo
        // 通过 limitLow 和 i 可以判断能否不填数字，dfs 无需 isNum 参数
        // 如果前导零不影响答案，去掉这个 if block
        if limitLow && i < diffLH {
            // 不填数字，上界不受约束
            res = dfs(i+1, 0, true, false)
            d = 1 // 下面填数字，从 1 开始填
        }

        // isNum := !limitLow || i > diffLH
        for ; d <= hi; d++ {
            c0 := cnt0
            if d == 0 {
                c0++ // 统计 0 的个数
            }
            res += dfs(i+1, c0, limitLow && d == lo, limitHigh && d == hi)
            // res %= mod
        }
        return
    }

    return dfs(0, 0, true, true)
}

从低到高：

3704. 统计和为 N 的无零数对 2419 数对

§10.2 统计合法元素的价值总和

每个元素 $x$ 都有一个相应的价值 $f (x)$ ，计算 $[low, high]$ 中的满足题目约束的元素的价值总和。

例如 $f (x) = x$ 是计算满足题目约束的元素和， $f (x) = digsum (x)$ 是计算满足题目约束的元素的数位和。

模板（数位和）：

# 计算在 [low, high] 中的整数 x 的数位和，满足 x 中的不同数字个数不超过 k
def digitDPContribution(low: int, high: int, k: int) -> int:
    low_s = list(map(int, str(low)))  # 避免在 dfs 中频繁调用 int()
    high_s = list(map(int, str(high)))
    n = len(high_s)
    diff_lh = n - len(low_s)

    # dfs 返回两个数：子树合法整数个数，子树数位总和
    @cache
    def dfs(i: int, mask: int, limit_low: bool, limit_high: bool) -> Tuple[int, int]:
        if i == n:
            # 如果没有特殊约束，那么能递归到终点的都是合法整数
            return 1, 0

        lo = low_s[i - diff_lh] if limit_low and i >= diff_lh else 0
        hi = high_s[i] if limit_high else 9

        cnt = res = 0
        start = lo

        # 如果前导零不影响答案，去掉这个 if block
        if limit_low and i < diff_lh:
            # 不填数字，上界不受约束
            cnt, res = dfs(i + 1, 0, True, False)
            start = 1

        for d in range(start, hi + 1):
            new_mask = mask | 1 << d
            if new_mask.bit_count() > k:  # 不满足要求
                continue
            sub_cnt, sub_sum = dfs(i + 1,
                                   new_mask,
                                   limit_low and d == lo,
                                   limit_high and d == hi)
            cnt += sub_cnt  # 累加子树的合法整数个数
            res += sub_sum  # 累加子树的数位总和
            res += d * sub_cnt  # d 会出现在 sub_cnt 个数中（贡献法）

        # cnt %= MOD; res %= MOD
        return cnt, res

    return dfs(0, 0, True, True)[1]

java

// 计算在 [low, high] 中的整数 x 的数位和，满足 x 中的不同数字个数不超过 k
class Solution {
    public long digitDPContribution(long low, long high, int k) {
        char[] lowS = String.valueOf(low).toCharArray();
        char[] highS = String.valueOf(high).toCharArray();

        int n = highS.length;
        long[][][] memo = new long[n][1 << 10][];

        return dfs(0, 0, true, true, lowS, highS, k, memo)[1];
    }

    // dfs 返回两个数：子树合法整数个数，子树数位总和
    private long[] dfs(int i, int mask, boolean limitLow, boolean limitHigh, char[] lowS, char[] highS, int k, long[][][] memo) {
        if (i == highS.length) {
            // 如果没有特殊约束，那么能递归到终点的都是合法整数
            return new long[]{1, 0};
        }

        if (!limitLow && !limitHigh && memo[i][mask] != null) {
            return memo[i][mask];
        }

        int diff = highS.length - lowS.length;
        int lo = limitLow && i >= diff ? lowS[i - diff] - '0' : 0;
        int hi = limitHigh ? highS[i] - '0' : 9;

        long cnt = 0;
        long sum = 0;
        int d = lo;

        // 如果前导零不影响答案，去掉这个 if block
        if (limitLow && i < diff) {
            // 不填数字，上界不受约束
            long[] sub = dfs(i + 1, 0, true, false, lowS, highS, k, memo);
            cnt = sub[0];
            sum = sub[1];
            d = 1;
        }

        for (; d <= hi; d++) {
            int newMask = mask | 1 << d;
            if (Integer.bitCount(newMask) > k) { // 不满足要求
                continue;
            }
            long[] sub = dfs(i + 1,
                             newMask,
                             limitLow && d == lo,
                             limitHigh && d == hi,
                             lowS, highS, k, memo);
            cnt += sub[0]; // 累加子树的合法整数个数
            sum += sub[1]; // 累加子树的数位总和
            sum += d * sub[0]; // d 会出现在 sub[0] 个数中（贡献法）
            // cnt %= MOD; sum %= MOD;
        }

        long[] res = new long[]{cnt, sum};
        if (!limitLow && !limitHigh) {
            memo[i][mask] = res;
        }
        return res;
    }
}

cpp

// 计算在 [low, high] 中的整数 x 的数位和，满足 x 中的不同数字个数不超过 k
long long digitDPContribution(long long low, long long high, int k) {
    string low_s = to_string(low);
    string high_s = to_string(high);
    int n = high_s.size();
    int diff_lh = n - low_s.size();
    vector memo(n, vector<pair<long long, long long>>(1 << 10, {-1, -1}));

    // dfs 返回两个数：子树合法整数个数，子树数位总和
    auto dfs = [&](this auto&& dfs, int i, int mask, bool limit_low, bool limit_high) -> pair<long long, long long> {
        if (i == n) {
            // 如果没有特殊约束，那么能递归到终点的都是合法整数
            return {1, 0};
        }

        if (!limit_low && !limit_high && memo[i][mask].first >= 0) {
            return memo[i][mask];
        }

        int lo = limit_low && i >= diff_lh ? low_s[i - diff_lh] - '0' : 0;
        int hi = limit_high ? high_s[i] - '0' : 9;

        long long cnt = 0, sum = 0;
        int d = lo;

        // 如果前导零不影响答案，去掉这个 if block
        if (limit_low && i < diff_lh) {
            // 不填数字，上界不受约束
            tie(cnt, sum) = dfs(i + 1, 0, true, false);
            d = 1;
        }

        for (; d <= hi; d++) {
            int new_mask = mask | 1 << d;
            if (popcount((uint32_t) new_mask) > k) { // 不满足要求
                continue;
            }
            auto [sub_cnt, sub_sum] = dfs(i + 1, new_mask, limit_low && d == lo, limit_high && d == hi);
            cnt += sub_cnt; // 累加子树的合法整数个数
            sum += sub_sum; // 累加子树的数位总和
            sum += d * sub_cnt; // d 会出现在 sub_cnt 个数中（贡献法）
            // cnt %= MOD; sum %= MOD;
        }

        pair<long long, long long> res = {cnt, sum};
        if (!limit_low && !limit_high) {
            memo[i][mask] = res;
        }
        return res;
    };

    return dfs(0, 0, true, true).second;
}

// 计算在 [low, high] 中的整数 x 的数位和，满足 x 中的不同数字个数不超过 k
func digitDPContribution(low, high int, k int) int {
    lowS := strconv.Itoa(low)
    highS := strconv.Itoa(high)
    n := len(highS)
    diffLH := n - len(lowS)
    type pair struct{ cnt, sum int }
    memo := make([][1 << 10]pair, n)
    for i := range memo {
        for j := range memo[i] {
            memo[i][j].cnt = -1
        }
    }

    // dfs 返回两个数：子树合法整数个数，子树数位总和
    var dfs func(int, int, bool, bool) pair
    dfs = func(i, mask int, limitLow, limitHigh bool) (res pair) {
        if i == n {
            // 如果没有特殊约束，那么能递归到终点的都是合法整数
            return pair{1, 0}
        }
        if !limitLow && !limitHigh {
            p := &memo[i][mask]
            if p.cnt >= 0 {
                return *p
            }
            defer func() { *p = res }()
        }

        lo := 0
        if limitLow && i >= diffLH {
            lo = int(lowS[i-diffLH] - '0')
        }
        hi := 9
        if limitHigh {
            hi = int(highS[i] - '0')
        }

        d := lo
        // 如果前导零不影响答案，可以去掉这个 if block
        if limitLow && i < diffLH {
            // 不填数字，上界不受约束
            res = dfs(i+1, 0, true, false)
            d = 1
        }

        for ; d <= hi; d++ {
            newMask := mask | 1<<d
            if bits.OnesCount(uint(newMask)) > k { // 不满足要求
                continue
            }
            sub := dfs(i+1, newMask, limitLow && d == lo, limitHigh && d == hi)
            res.cnt += sub.cnt     // 累加子树的合法整数个数
            res.sum += sub.sum     // 累加子树的数位总和
            res.sum += d * sub.cnt // d 会出现在 sub.cnt 个数中（贡献法）
            // res.cnt %= mod; res.sum %= mod
        }
        return
    }

    return dfs(0, 0, true, true).sum
}

§10.3 其他数位 DP

3677. 统计二进制回文数字的数目 2223
3348. 最小可整除数位乘积 II 3101 只有下界

十一、优化 DP

§11.1 前缀和优化 DP

§11.2 单调栈优化 DP

前置题单：单调栈（矩形系列/字典序最小/贡献法）

§11.3 单调队列优化 DP

一般用来维护一段转移来源的最值。

前提：区间右端点变大时，左端点也在变大（同滑动窗口）。
转移前，去掉队首无用数据。
计算转移（直接从队首转移）。
把数据（一般是 $f [i]$ ）插入队尾前，去掉队尾无用数据。

§11.4 树状数组/线段树优化 DP

§11.5 字典树优化 DP

§11.6 矩阵快速幂优化 DP

有两种类型的矩阵快速幂优化 DP：

线性 DP（常系数齐次线性递推），转移系数写在第一行，其余行 $m_{i + 1, i} = 1$ ，例如 70，1137。讲解（含模板代码）。
多维 DP 或者状态机 DP，转移系数可表示为一个 $k \times k$ 大小的矩阵，例如 935。讲解（含模板代码）。

时间复杂度一般为 $O (k^{3} \log n)$ 。

进阶做法：先用 Berlekamp-Massey 算法找规律，得到线性递推式，然后用 Kitamasa 算法（或者 Bostan-Mori 算法）优化。

请看我的知乎科普文章：

具体例子见 3700 题我的题解的方法二。

时间复杂度一般为 $O (k^{2} \log n)$ 。

§11.7 斜率优化 DP

也叫凸包优化/凸壳优化（CHT，Convex Hull Trick）。

讲解

§11.8 WQS 二分优化 DP

本质是凸优化中的拉格朗日松弛 (Lagrangian Relaxation)。

把最多选 $k$ 个物品的问题（时间复杂度高）转换成选任意个物品的问题（时间复杂度低）。

一般时间复杂度为 $O (n \log U)$ 或者 $O (n \log n)$ 。

讲解

此外「§5.3 约束划分个数」的部分题目也可以用 WQS 二分优化。

§11.9 其他优化 DP

3654. 删除可整除和后的最小数组和 2039
1937. 扣分后的最大得分 2106
2713. 矩阵中严格递增的单元格数 2387
3651. 带传送的最小路径成本 2411
2318. 不同骰子序列的数目容斥优化（类似 CF1943D2）
1563. 石子游戏 V 单调性优化，可以做到 $O (n^{2})$
3181. 执行操作可获得的最大总奖励 II 2688 bitset 优化
2267. 检查是否有合法括号字符串路径可以进一步地用 bitset 优化
3213. 最小代价构造字符串字符串哈希 / 后缀数组 / AC 自动机优化
3292. 形成目标字符串需要的最少字符串数 II 字符串哈希 / AC 自动机优化
3743. 循环划分的最大得分闵可夫斯基和
LCP 14. 切分数组
LCP 59. 搭桥过河 Slope Trick
2263. 数组变为有序的最小操作次数（会员题）Slope Trick
3916. 锯齿形数组的总数 III（会员题）拉格朗日插值

关于倍增算法，见题单的「§3.8 最近公共祖先（LCA）、倍增算法」。

十二、树形 DP

注：可能有同学觉得树形 DP 没有重复访问同一个状态（重叠子问题），并不能算作 DP，而是算作普通的递归。这么说也有一定道理，不过考虑到思维方式和 DP 是一样的自底向上，所以仍然叫做树形 DP。此外，如果是自顶向下的递归做法，是存在重叠子问题的，一般要结合记忆化搜索实现。

§12.1 树的直径

讲解：树形 DP：树的直径【基础算法精讲 23】

注：求直径也有两次 DFS 的做法。

§12.2 树上最大独立集

讲解：树形 DP：打家劫舍 III【基础算法精讲 24】

337. 打家劫舍 III（没有上司的舞会）
2646. 最小化旅行的价格总和 2238
3544. 子树反转和 2545 记忆化搜索 / 树上刷表法
2378. 选择边来最大化树的得分（会员题）
3949. 子树反转和 II（会员题）

§12.3 树上最小支配集

讲解：树形 DP：监控二叉树【基础算法精讲 25】，包含 968 的变形题。

968. 监控二叉树 2124

§12.4 换根 DP

也叫二次扫描法。

设 $y$ 是 $x$ 的子节点。从「以 $x$ 为整棵树的根」变成「以 $y$ 为整棵树的根」，发生了什么？

站在 $x$ 的视角，去掉子树 $y$ 。设剩余部分为 $F$ 。
以 $y$ 为根时， $x$ 挂在 $y$ 的下面， $F$ 变成 $y$ 的一棵子树。

【图解】一张图秒懂换根 DP！

模板一：简单场景（例如 3772 题）

class Solution:
    def maxSubgraphScore(self, n: int, edges: List[List[int]], good: List[int]) -> List[int]:
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        # sub_score[x] 表示（以 0 为根时）包含 x 的子树 x 的最大得分
        sub_score = [0] * n
        # 计算 sub_score[x]
        def dfs(x: int, fa: int) -> None:
            sub_score[x] = 1 if good[x] else -1  # sub_score[x] 一定包含 x
            for y in g[x]:
                if y != fa:
                    dfs(y, x)
                    # 如果子树 y 的最大得分 > 0，选子树 y，否则不选
                    sub_score[x] += max(sub_score[y], 0)
        dfs(0, -1)

        ans = [0] * n
        ans[0] = sub_score[0]
        # 对于 x 的儿子 y，计算包含 y 的子图最大得分
        def reroot(x: int, fa: int) -> None:
            for y in g[x]:
                if y != fa:
                    # 从 ans[x] 中去掉子树 y，剩余部分记作 F
                    score_f = ans[x] - max(sub_score[y], 0)
                    # 换根后，x 挂在 y 的下面，F 变成 y 的一棵子树
                    # 计算 F 对 y 的贡献：如果 F 的最大得分 > 0，选 F，否则不选
                    ans[y] = sub_score[y] + max(score_f, 0)
                    reroot(y, x)
        reroot(0, -1)
        return ans

java

class Solution {
    public int[] maxSubgraphScore(int n, int[][] edges, int[] good) {
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, _ -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            g[x].add(y);
            g[y].add(x);
        }

        // subScore[x] 表示（以 0 为根时）包含 x 的子树 x 的最大得分
        int[] subScore = new int[n];
        dfs(0, -1, g, good, subScore);

        int[] ans = new int[n];
        ans[0] = subScore[0];
        reroot(0, -1, g, subScore, ans);
        return ans;
    }

    // 计算 subScore[x]
    private void dfs(int x, int fa, List<Integer>[] g, int[] good, int[] subScore) {
        subScore[x] = good[x] == 0 ? -1 : 1; // subScore[x] 一定包含 x
        for (int y : g[x]) {
            if (y != fa) {
                dfs(y, x, g, good, subScore);
                // 如果子树 y 的最大得分 > 0，选子树 y，否则不选
                subScore[x] += Math.max(subScore[y], 0);
            }
        }
    }

    // 对于 x 的儿子 y，计算包含 y 的子图最大得分
    private void reroot(int x, int fa, List<Integer>[] g, int[] subScore, int[] ans) {
        for (int y : g[x]) {
            if (y != fa) {
                // 从 ans[x] 中去掉子树 y，剩余部分记作 F
                int scoreF = ans[x] - Math.max(subScore[y], 0);
                // 换根后，x 挂在 y 的下面，F 变成 y 的一棵子树
                // 计算 F 对 y 的贡献：如果 F 的最大得分 > 0，选 F，否则不选
                ans[y] = subScore[y] + Math.max(scoreF, 0);
                reroot(y, x, g, subScore, ans);
            }
        }
    }
}

cpp

class Solution {
public:
    vector<int> maxSubgraphScore(int n, vector<vector<int>>& edges, vector<int>& good) {
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        // sub_score[x] 表示（以 0 为根时）包含 x 的子树 x 的最大得分
        vector<int> sub_score(n);
        // 计算 sub_score[x]
        auto dfs = [&](this auto&& dfs, int x, int fa) -> void {
            sub_score[x] = good[x] ? 1 : -1; // subScore[x] 一定包含 x
            for (int y : g[x]) {
                if (y != fa) {
                    dfs(y, x);
                    // 如果子树 y 的最大得分 > 0，选子树 y，否则不选
                    sub_score[x] += max(sub_score[y], 0);
                }
            }
        };
        dfs(0, -1);

        vector<int> ans(n);
        ans[0] = sub_score[0];
        // 对于 x 的儿子 y，计算包含 y 的子图最大得分
        auto reroot = [&](this auto&& reroot, int x, int fa) -> void {
            for (int y : g[x]) {
                if (y != fa) {
                    // 从 ans[x] 中去掉子树 y，剩余部分记作 F
                    int score_f = ans[x] - max(sub_score[y], 0);
                    // 换根后，x 挂在 y 的下面，F 变成 y 的一棵子树
                    // 计算 F 对 y 的贡献：如果 F 的最大得分 > 0，选 F，否则不选
                    ans[y] = sub_score[y] + max(score_f, 0);
                    reroot(y, x);
                }
            }
        };
        reroot(0, -1);
        return ans;
    }
};

func maxSubgraphScore(n int, edges [][]int, good []int) []int {
    g := make([][]int, n)
    for _, e := range edges {
        x, y := e[0], e[1]
        g[x] = append(g[x], y)
        g[y] = append(g[y], x)
    }

    // subScore[x] 表示（以 0 为根时）包含 x 的子树 x 的最大得分
    subScore := make([]int, n)
    // 计算 subScore[x]
    var dfs func(int, int)
    dfs = func(x, fa int) {
        subScore[x] = good[x]*2 - 1 // subScore[x] 一定包含 x
        for _, y := range g[x] {
            if y != fa {
                dfs(y, x)
                // 如果子树 y 的最大得分 > 0，选子树 y，否则不选
                subScore[x] += max(subScore[y], 0)
            }
        }
    }
    dfs(0, -1)

    ans := make([]int, n)
    ans[0] = subScore[0]
    // 对于 x 的儿子 y，计算包含 y 的子图最大得分
    var reroot func(int, int)
    reroot = func(x, fa int) {
        for _, y := range g[x] {
            if y != fa {
                // 从 ans[x] 中去掉子树 y，剩余部分记作 F
                scoreF := ans[x] - max(subScore[y], 0)
                // 换根后，x 挂在 y 的下面，F 变成 y 的一棵子树
                // 计算 F 对 y 的贡献：如果 F 的最大得分 > 0，选 F，否则不选
                ans[y] = subScore[y] + max(scoreF, 0)
                reroot(y, x)
            }
        }
    }
    reroot(0, -1)
    return ans
}

模板二：维护最大次大（例如 3241 题）

class Solution:
    def timeTaken(self, edges: List[List[int]]) -> List[int]:
        n = len(edges) + 1
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        # sub_res[x] 保存子树 x 的最大深度，次大深度，以及最大深度要往哪个儿子走
        sub_res = [None] * n
        # 计算 sub_res[x]
        def dfs(x: int, fa: int) -> None:
            max_d = max_d2 = my = 0
            for y in g[x]:
                if y == fa:
                    continue
                dfs(y, x)
                w = 2 - y % 2  # 从 x 到 y 的边权
                max_y = sub_res[y][0] + w  # 从 x 出发，往 y 方向的最大深度
                if max_y > max_d:
                    max_d2 = max_d
                    max_d = max_y
                    my = y
                elif max_y > max_d2:
                    max_d2 = max_y
            sub_res[x] = (max_d, max_d2, my)
        dfs(0, -1)

        # ans[x] 表示当 x 是树根时，整棵树的最大深度
        ans = [0] * n
        # 计算 ans[x]
        def reroot(x: int, fa: int, from_up: int) -> None:
            max_d, max_d2, my = sub_res[x]
            ans[x] = max(max_d, from_up)
            for y in g[x]:
                if y == fa:
                    continue
                w = 2 - x % 2  # 从 y 到 x 的边权
                mx = max_d if y != my else max_d2
                # 站在 x 的角度，不往 y 走，能走多远？
                # 要么往上走（from_up），要么往除了 y 的其余子树走（mx），二者取最大值
                reroot(y, x, max(from_up, mx) + w)  # 对于 y 来说，加上从 y 到 x 的边权 w
        reroot(0, -1, 0)
        return ans

java

class Solution {
    public int[] timeTaken(int[][] edges) {
        int n = edges.length + 1;
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, _ -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            g[x].add(y);
            g[y].add(x);
        }

        // subRes[x] 保存子树 x 的最大深度，次大深度，以及最大深度要往哪个儿子走
        int[][] subRes = new int[n][];
        dfs(0, -1, g, subRes);

        // ans[x] 表示当 x 是树根时，整棵树的最大深度
        int[] ans = new int[n];
        reroot(0, -1, 0, g, subRes, ans);
        return ans;
    }

    // 计算 subRes[x]
    private void dfs(int x, int fa, List<Integer>[] g, int[][] subRes) {
        int maxD = 0;
        int maxD2 = 0;
        int my = 0;
        for (int y : g[x]) {
            if (y == fa) {
                continue;
            }
            dfs(y, x, g, subRes);
            int w = 2 - y % 2; // 从 x 到 y 的边权
            int maxY = subRes[y][0] + w; // 从 x 出发，往 y 方向的最大深度
            if (maxY > maxD) {
                maxD2 = maxD;
                maxD = maxY;
                my = y;
            } else if (maxY > maxD2) {
                maxD2 = maxY;
            }
        }
        subRes[x] = new int[]{maxD, maxD2, my};
    }

    // 计算 ans[x]
    private void reroot(int x, int fa, int fromUp, List<Integer>[] g, int[][] subRes, int[] ans) {
        int maxD = subRes[x][0];
        int maxD2 = subRes[x][1];
        int my = subRes[x][2];
        ans[x] = Math.max(maxD, fromUp);
        for (int y : g[x]) {
            if (y == fa) {
                continue;
            }
            int w = 2 - x % 2; // 从 y 到 x 的边权
            int mx = y != my ? maxD : maxD2;
            // 站在 x 的角度，不往 y 走，能走多远？
            // 要么往上走（fromUp），要么往除了 y 的其余子树走（mx），二者取最大值
            reroot(y, x, Math.max(fromUp, mx) + w, g, subRes, ans);
        }
    }
}

cpp

class Solution {
public:
    vector<int> timeTaken(vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        // sub_res[x] 保存子树 x 的最大深度，次大深度，以及最大深度要往哪个儿子走
        vector<tuple<int, int, int>> sub_res(n);
        // 计算 sub_res[x]
        auto dfs = [&](this auto&& dfs, int x, int fa) -> void {
            int max_d = 0, max_d2 = 0, my = 0;
            for (int y : g[x]) {
                if (y == fa) {
                    continue;
                }
                dfs(y, x);
                int w = 2 - y % 2; // 从 x 到 y 的边权
                int max_y = get<0>(sub_res[y]) + w; // 从 x 出发，往 y 方向的最大深度
                if (max_y > max_d) {
                    max_d2 = max_d;
                    max_d = max_y;
                    my = y;
                } else if (max_y > max_d2) {
                    max_d2 = max_y;
                }
            }
            sub_res[x] = {max_d, max_d2, my};
        };
        dfs(0, -1);

        // ans[x] 表示当 x 是树根时，整棵树的最大深度
        vector<int> ans(n);
        // 计算 ans[x]
        auto reroot = [&](this auto&& reroot, int x, int fa, int from_up) -> void {
            auto [max_d, max_d2, my] = sub_res[x];
            ans[x] = max(max_d, from_up);
            for (int y : g[x]) {
                if (y == fa) {
                    continue;
                }
                int w = 2 - x % 2; // 从 y 到 x 的边权
                int mx = y != my ? max_d : max_d2;
                // 站在 x 的角度，不往 y 走，能走多远？
                // 要么往上走（from_up），要么往除了 y 的其余子树走（mx），二者取最大值
                reroot(y, x, max(from_up, mx) + w); // 对于 y 来说，加上从 y 到 x 的边权 w
            }
        };
        reroot(0, -1, 0);
        return ans;
    }
};

func timeTaken(edges [][]int) []int {
    n := len(edges) + 1
    g := make([][]int, n)
    for _, e := range edges {
        x, y := e[0], e[1]
        g[x] = append(g[x], y)
        g[y] = append(g[y], x)
    }

    // subRes[x] 保存子树 x 的最大深度 maxD，次大深度 maxD2，以及最大深度要往儿子 y 走
    subRes := make([]struct{ maxD, maxD2, y int }, n)
    // 计算 subRes[x]
    var dfs func(int, int)
    dfs = func(x, fa int) {
        res := &subRes[x]
        for _, y := range g[x] {
            if y == fa {
                continue
            }
            dfs(y, x)
            w := 2 - y%2 // 从 x 到 y 的边权
            maxD := subRes[y].maxD + w // 从 x 出发，往 y 方向的最大深度
            if maxD > res.maxD {
                res.maxD2 = res.maxD
                res.maxD = maxD
                res.y = y
            } else if maxD > res.maxD2 {
                res.maxD2 = maxD
            }
        }
    }
    dfs(0, -1)

    // ans[x] 表示当 x 是树根时，整棵树的最大深度
    ans := make([]int, n)
    // 计算 ans[x]
    var reroot func(int, int, int)
    reroot = func(x, fa, fromUp int) {
        sub := subRes[x]
        ans[x] = max(sub.maxD, fromUp)
        for _, y := range g[x] {
            if y == fa {
                continue
            }
            w := 2 - x%2 // 从 y 到 x 的边权
            mx := sub.maxD
            if y == sub.y { // 对于 y 来说，上面要选次大的
                mx = sub.maxD2
            }
            // 站在 x 的角度，不往 y 走，能走多远？
            // 要么往上走（fromUp），要么往除了 y 的其余子树走（mx），二者取最大值
            reroot(y, x, max(fromUp, mx)+w) // 对于 y 来说，加上从 y 到 x 的边权 w
        }
    }
    reroot(0, -1, 0)
    return ans
}

834. 树中距离之和 2197
2581. 统计可能的树根数目 2228
3772. 子图的最大得分 2235
2858. 可以到达每一个节点的最少边反转次数 2295
310. 最小高度树也可以用拓扑排序做
3241. 标记所有节点需要的时间 2522
3372. 连接两棵树后最大目标节点数目 I 做到 $O ((n + m) k)$ ，解决 $n$ 和 $m$ 很大但 $k$ 很小的场景
3967. 任务完成时间 II（会员题）

注：前后缀分解，可以视作一条链上的换根 DP。

§12.5 其他树形 DP

十三、图 DP

另见【题单】图论算法中的「全源最短路：Floyd」，本质是多维 DP。

十四、博弈 DP

十五、概率 DP、期望 DP

专题：输出具体方案（打印方案）

注意这些题目和回溯的区别，某些回溯题目要求输出所有方案，这里只要求输出一个。

讲解

专题：前后缀分解

部分题目也可以用状态机 DP 或者分组循环（见双指针题单）解决。

如果涉及到的只是若干元素，而不是前缀/后缀这样的一段元素，也可以用「枚举右，维护左」思考，见数据结构题单。

专题：跳跃游戏

其他

算法题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

如果你发现有题目可以补充进来，欢迎评论反馈。

数据结构

数据库

离散数学

数字电路

概率论

数学建模

软件工程

面向对象程序设计

Python 与数据分析

计算机组成

操作系统

计算机网络

编译原理

图形学

自然语言处理

Linux 实验

分布式系统

Internet原理与技术

BlogWeb

Stars Saying

黑马商城

苍穹外卖

黑马点评

黑马商城单体版

JavaWeb AI Tlias

RuoYi DKD

LinkQwen

InterX

LeetCode Agent Lab

00-预备知识

01-PR1108-逐代码段解析

02-PR1135-Cube化逐代码段解析

03-两个Bug深度剖析

04-开发心得与数值性能实测

01-PR1169-模型推理性能优化

02-PR1194-固定Shape及分档推理适配

NumPy

PyTorch

Python 八股文

LeetCUDA

LeetGPU

Triton

前言 ​

一、入门 DP ​

§1.1 爬楼梯 ​

§1.2 打家劫舍 ​

答疑 ​

§1.3 最大子数组和（最大子段和） ​

思考题 ​

二、网格图 DP ​

§2.1 基础 ​

§2.2 进阶 ​

三、背包 ​

§3.1 0-1 背包 ​

§3.2 完全背包 ​

§3.3 多重背包（选做） ​

§3.4 分组背包 ​

§3.5 树上背包（选做） ​

四、经典线性 DP ​

§4.1 最长公共子序列（LCS） ​

§4.1.1 基础 ​

§4.1.2 进阶 ​

§4.2 最长递增子序列（LIS） ​

§4.2.1 基础 ​

§4.2.2 进阶 ​

五、划分型 DP ​

§5.1 判定能否划分 ​

§5.2 最优划分 ​

§5.3 约束划分个数 ​

六、状态机 DP ​

§6.1 买卖股票 ​

§6.2 基础 ​

§6.3 进阶 ​

七、其他线性 DP ​

§7.1 一维 DP ​

§7.2 不相交区间 ​

§7.3 子数组 DP ​

§7.4 合法子序列 DP ​

§7.5 子矩形 DP ​

§7.6 多维 DP ​

前言

一、入门 DP

§1.1 爬楼梯

§1.2 打家劫舍

答疑

§1.3 最大子数组和（最大子段和）

思考题

二、网格图 DP

§2.1 基础

§2.2 进阶

三、背包

§3.1 0-1 背包

§3.2 完全背包

§3.3 多重背包（选做）

§3.4 分组背包

§3.5 树上背包（选做）

四、经典线性 DP

§4.1 最长公共子序列（LCS）

§4.1.1 基础

§4.1.2 进阶

§4.2 最长递增子序列（LIS）

§4.2.1 基础

§4.2.2 进阶

五、划分型 DP

§5.1 判定能否划分

§5.2 最优划分

§5.3 约束划分个数

六、状态机 DP

§6.1 买卖股票

§6.2 基础

§6.3 进阶

七、其他线性 DP

§7.1 一维 DP

§7.2 不相交区间

§7.3 子数组 DP

§7.4 合法子序列 DP

§7.5 子矩形 DP

§7.6 多维 DP

§7.7 计数 DP

八、区间 DP

§8.1 最长回文子序列

§8.2 区间 DP

九、状态压缩 DP（状压 DP）

§9.1 排列型状压 DP ① 相邻无关

§9.2 排列型状压 DP ② 相邻相关

§9.3 旅行商问题（TSP）

§9.4 子集状压 DP

§9.5 轮廓线 DP

§9.6 SOS DP

§9.7 其他状压 DP

十、数位 DP

§10.1 统计合法元素的数目

§10.2 统计合法元素的价值总和

§10.3 其他数位 DP

十一、优化 DP

§11.1 前缀和优化 DP

§11.2 单调栈优化 DP

§11.3 单调队列优化 DP

§11.4 树状数组/线段树优化 DP

§11.5 字典树优化 DP

§11.6 矩阵快速幂优化 DP

§11.7 斜率优化 DP

§11.8 WQS 二分优化 DP

§11.9 其他优化 DP

十二、树形 DP

§12.1 树的直径

§12.2 树上最大独立集

§12.3 树上最小支配集

§12.4 换根 DP

§12.5 其他树形 DP

十三、图 DP

十四、博弈 DP

十五、概率 DP、期望 DP

专题：输出具体方案（打印方案）

专题：前后缀分解