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

灵茶山艾府
924141
发布于 未知归属地
位运算树递归记忆化数学动态规划博弈周赛数据结构数据结构与算法单调队列单调栈双周赛概率与统计学习分享

前言

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

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

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

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

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

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

一、入门 DP

§1.1 爬楼梯

讲解

§1.2 打家劫舍

答疑

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

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

思维扩展：

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

有两种做法：

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

思维扩展：

思考题

完成本章后，请思考：什么时候要返回 ，什么时候要返回 ？

二、网格图 DP

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

讲解

§2.1 基础

思维扩展：

§2.2 进阶

三、背包

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

§3.1 0-1 背包

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

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

进阶：

§3.2 完全背包

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

思维扩展：

§3.3 多重背包（选做）

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

求方案数

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

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

二进制优化

§3.4 分组背包

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

§3.5 树上背包（选做）

注：目前力扣只有无依赖的背包，时间复杂度为 ，其中 是树的节点个数， 是背包容量。如果有依赖，可以优化到 。

四、经典线性 DP

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

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

一般定义 表示对 的求解结果。

§4.1.1 基础

思维扩展：

§4.1.2 进阶

思考题：

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

思路和代码见 评论。

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

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

做法有很多：

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

§4.2.1 基础

§4.2.2 进阶

思维扩展：

思考题：

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

解答（评论）

五、划分型 DP

§5.1 判定能否划分

一般定义 表示长为 的前缀 能否划分。

枚举最后一个子数组的左端点 ，从 转移到 ，并考虑 是否满足要求。

§5.2 最优划分

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

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

枚举最后一个子数组的左端点 ，从 转移到 ，并考虑 对最优解的影响。

§5.3 约束划分个数

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

一般定义 表示将长为 的前缀 分成 个连续子数组所得到的最优解。

枚举最后一个子数组的左端点 ，从 转移到 ，并考虑 对最优解的影响。

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

六、状态机 DP

一般定义 表示前缀 在状态 下的最优值。 一般很小。

§6.1 买卖股票

讲解【基础算法精讲 21】

§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

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

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

一般定义 表示下标区间 的最优值。

§8.1 最长回文子序列

§8.2 区间 DP

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

  1. 可以消除相邻的匹配字符。
  2. 相邻匹配字符消除后，原本不相邻的字符会变成相邻，可以继续消除。换句话说，设子串 ，如果 和 是匹配的（可以消除），且子串 可以完全消除，那么子串 可以完全消除。
  3. 设子串 ，如果子串 和 可以完全消除，那么子串 可以完全消除。

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

定义 表示消除 到 的最优值。

  • 根据性质 2，可以把 缩小成子问题 。
  • 根据性质 3，可以枚举子串 的右端点，即枚举 ，把 划分成子问题 和 。注意这里枚举 的步长是 ，因为每次消除 个字符，被消除的子串长度一定是偶数。

边界：，即空串。

答案：。

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

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

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

学习指南：

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

状压 DP 可以把时间复杂度（通常来说）优化至 。可以解决 的问题。

一般有两种定义方式：

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

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

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

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

时间复杂度（通常来说）是 。

§9.3 旅行商问题（TSP）

本质上就是排列型 ②。

相似问题：

§9.4 子集状压 DP

一般定义 表示未选（或者已选）的集合为 时，和题目有关的最优值。通过枚举 （或者 的补集 ）的子集来转移。

时间复杂度（通常来说）是 ，证明：

对于大小为 的集合，它的大小为 的子集有 个，每个子集又有 个子集。根据二项式定理，，所以「枚举子集的子集」的总体时间复杂度为 。

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

相关问题：

§9.5 轮廓线 DP

思维扩展：

§9.6 SOS DP

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

原理讲解（方法二）

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

Python3
Java
C++
Go
# 设 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

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

Python3
Java
C++
Go
# 设 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

§9.7 其他状压 DP

十、数位 DP

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

§10.1 统计合法元素的数目

数位 DP v1.0 模板讲解

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

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

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

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

注：只有上界约束的题目，相当于 或者 。

Python3
Java
C++
Go
# 代码示例：返回 [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)

从低到高：

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

每个元素 都有一个相应的价值 ，计算 中的满足题目约束的元素的价值总和。

例如 是计算满足题目约束的元素和， 是计算满足题目约束的元素的数位和。

模板（数位和）：

Python3
Java
C++
Go
# 计算在 [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]

§10.3 其他数位 DP

十一、优化 DP

§11.1 前缀和优化 DP

§11.2 单调栈优化 DP

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

§11.3 单调队列优化 DP

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

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

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

§11.5 字典树优化 DP

§11.6 矩阵快速幂优化 DP

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

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

时间复杂度一般为 。

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

请看我的知乎科普文章：

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

时间复杂度一般为 。

§11.7 斜率优化 DP

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

讲解

§11.8 WQS 二分优化 DP

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

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

一般时间复杂度为 或者 。

讲解

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

§11.9 其他优化 DP

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

十二、树形 DP

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

§12.1 树的直径

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

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

§12.2 树上最大独立集

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

§12.3 树上最小支配集

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

§12.4 换根 DP

也叫二次扫描法。

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

  1. 站在 的视角，去掉子树 。设剩余部分为 。
  2. 以 为根时， 挂在 的下面， 变成 的一棵子树。

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

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

Python3
Java
C++
Go
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

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

Python3
Java
C++
Go
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

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

§12.5 其他树形 DP

十三、图 DP

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

十四、博弈 DP

十五、概率 DP、期望 DP

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

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

讲解

专题：前后缀分解

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

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

专题：跳跃游戏

其他

算法题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

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

评论 (464)