跳到主要内容

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

By 灵茶山艾府

最近编辑于 2024-07-01

HX注​

恕我直言, 这个价值三千七百万!

前缀和优化 DP【力扣周赛 410】 43:28 开始, 聊一聊怎么刷题, 其中提到了dp (前面有手把手指导记忆化1:1翻译成dp的步骤)

学习dp的重点, 就是锻炼寻找子问题的能力, 剩下的都是代码能力上的东西!

前言​

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

我能做的，是帮你节省找题的时间，并把这些题分类整理好。有着相同套路的题，一起做效率会更高，也更能领悟到 DP 的精髓。所以推荐按照专题刷。

题目已按照难度分排序（右侧数字为难度分）。如果遇到难度很大，题解都看不懂的题目，建议直接跳过，二刷的时候再来尝试。

一、入门 DP​

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

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

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

§1.1 爬楼梯​

§1.2 打家劫舍​

通用套路: f[i]=max⁡(f[i−1],f[i−2]+a[i])f[i] = \max(f[i - 1], f[i - 2] + a[i]) # 不能选择相邻(a[i - 1], a[i + 1]), 则分: 不选, 选 两种情况

对于选择了a[i]就不能选择a[i] - 2 ，a[i] - 1 ，a[i] + 1 或者 a[i] + 2的同理: f[i]=max(f[i−1],f[j−1]+a[i])f[i] = max(f[i - 1], f[j - 1] + a[i]) # 不选, 选(其中a[j - 1] < arr[i] - 2)

对于值域做法, 可以先使用哈希表统计, 映射到数组, 再通过索引做记忆化/dp的参数

§1.3 最大子数组和 (最大子段和)​

有两种做法:

  1. 定义状态 f[i]f[i] 表示以 α[i]α[i] 结尾的最大子数组和，不和 ii 左边拼起来就是 f[i]=a[i]f[i]=a[i], 和 ii 左边拼起来就是 f[i]=f[i－1]+a[i]f[i] = f[i － 1] + a[i], 取最大值就得到了状态转移方程 f[j]=max⁡(f[i−1],0)+a[i]f[j] = \max(f[i - 1],0) + a[i], 答案为 max⁡(f)\max(f)。这个做法也叫做 KadaneKadane 算法。

  2. 用前缀和解决，具体见 我的题解。

思维扩展：

二、网格图 DP​

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

讲解

§2.1 基础​

§2.2 进阶​

三、背包​

讲解：0-1 背包 完全背包

§3.1 0-1 背包​

每个物品只能选一次。

§3.2 完全背包​

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

§3.3 多重背包​

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

注：力扣上只有求方案数的题目。

§3.4 分组背包​

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

四、经典线性 DP​

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

讲解：最长公共子序列 编辑距离

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

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

讲解：最长递增子序列

做法有很多:

  1. 枚举选哪个（见讲解）。
  2. 贪心+二分（见讲解）。
  3. 计算 aa 和把 aa 排序后的数组 sortedA\textit{sortedA} 的最长公共子序列。
  4. 数据结构优化（见 2407 题）。

思维扩展：

思考题：

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

解答（评论）

五、状态机 DP​

讲解：状态机 DP

一般定义 f[i][j]f[i][j] 表示前缀 a[:i]a[:i] 在状态 jj 下的最优值。一般 jj 都很小。代表题目是「买卖股票」系列。

注: 某些题目做法不止一种，除了状态机 DP 以外，也有前后缀分解的做法。

六、划分型 DP​

§6.1 判定能否划分​

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

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

§6.2 计算划分最优值​

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

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

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

§6.3 约束划分个数​

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

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

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

§6.4 不相交区间​

七、其他线性 DP​

§7.1 一维​

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

§7.2 特殊子序列​

比较特殊的一类题型，递推比记忆化搜索好写。

§7.3 矩阵快速幂优化​

部分题目由于数据范围小，也可以用线性 DP。

§7.4 子矩形​

§7.5 多维​

八、区间 DP​

讲解：区间 DP

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

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

§8.1 最长回文子序列​

§8.2 其他区间 DP​

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

§9.1 排列型 ① 相邻无关​

学习指南：

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

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

一般有两种定义方式：

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

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

§9.2 排列型 ② 相邻相关​

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

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

讲解：从全排列到状压 DP

§9.3 旅行商问题（TSP）​

本质上就是排列型 ②。

§9.4 枚举子集的子集​

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

时间复杂度（通常来说）是 O(3n)\mathcal{O}(3^n)O(3n)，证明见 题解。

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

§9.5 其他状压 DP​

十、数位 DP​

v1.0 模板讲解

v2.0 模板讲解

十一、数据结构优化 DP​

§11.1 前缀和优化 DP​

§11.2 单调栈优化 DP​

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

§11.3 单调队列优化 DP​

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

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

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

§11.5 字典树优化 DP​

§11.6 其他优化 DP​

十二、树形 DP​

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

§12.1 树的直径​

讲解：树形 DP：树的直径

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

§12.2 树上最大独立集​

讲解：

§12.3 树上最小支配集​

讲解：树形 DP：监控二叉树，包含 968 的变形题。

§12.4 换根 DP​

也叫二次扫描法。

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

§12.5 其他树形 DP​

十三、图 DP​

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

十四、博弈 DP​

十五、概率/期望 DP​

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

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

讲解

专题：前后缀分解​

部分题目也可以用状态机 DP 解决。

专题：把 X 变成 Y​

部分题目也可以用 BFS 解决。

专题：跳跃游戏​

其他 DP​

编辑此页
最后由 Heng_Xin_666 于 更新
请作者喝奶茶:
Alipay IconQR Code
Alipay IconQR Code
本文遵循 CC CC 4.0 BY-SA 版权协议, 转载请标明出处
Loading Comments...
0%