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

灵茶山艾府

698392

2024.03.19

2025.11.25

发布于未知归属地

位运算树递归记忆化搜索数学动态规划博弈周赛数据结构数据结构与算法单调队列单调栈双周赛概率与统计学习分享

前言

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

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

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

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

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

一、入门 DP

§1.1 爬楼梯

讲解

§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 基础

思维扩展：

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})$ 。如果有依赖，可以优化到 $O (nW)$ 。

3562. 折扣价交易股票的最大利润 2458

四、经典线性 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 进阶

思维扩展：

368. 最大整除子集约 1800
2901. 最长相邻不相等子序列 II 1899

思考题：

给定整数 $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 (nk)$ 优化至 $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]$ 。

§7.2 不相交区间

§7.3 子数组 DP

思维扩展：

§7.4 合法子序列 DP

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

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

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

思维扩展：

§7.5 子矩形 DP

§7.6 多维 DP

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

思维扩展：

638. 大礼包

八、区间 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）

§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$ 的子集有 $(m n)$ 个，每个子集又有 $2^{m}$ 个子集。根据二项式定理， $m = 0 \sum n (m n) 2^{m} = (2 + 1)^{n} = 3^{n}$ ，所以「枚举子集的子集」的总体时间复杂度为 $O (3^{n})$ 。

值得注意的是，枚举子集的子集还可以用「选或不选」来做，对于存在无效状态的情况，可以做到更优的时间复杂度。具体见 1349 题解最后的写法。

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

相关问题：

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

§9.5 SOS DP

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

原理讲解（方法二）

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

Python3

Java

C++

# 设 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++

# 设 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.6 其他状压 DP

十、数位 DP

§10.1 统计合法元素的数目

数位 DP v1.0 模板讲解

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

下面是数位 DP v2.1 模板。相比 v2.0，不需要写 $isNum$ 参数。

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

Python3

Java

C++

# 代码示例：返回 [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 可以判断能否不填数字，无需 is_num 参数
        # 如果前导零不影响答案，去掉这个 if block
        if limit_low and i < diff_lh:
            # 不填数字，上界不受约束
            res = dfs(i + 1, 0, True, False)
            start = 1

        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)

从低到高：

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

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

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

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

模板（数位和）：

Python3

Java

C++

# 计算在 [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]