背包 DP
背包 dp 解决形如用一些物品，有一些限制，装满这个容量的方案/最小代价。
四种板子
- 01背包，循环从高到低
- 完全背包，循环从低到高
- 多重背包，二进制分组（低到高）然后01背包
- 分组背包，每组在最内层，外层跑01背包
分组的特殊情况：
- 有依赖的背包：拆成 \(siz\) 件物品然后跑一遍分组。
简单优化：
- 对于存在性背包，可以用
bitset优化。 - 对于容量值域巨大但是体积巨小的，考虑先贪心一大部分再背包，正确性其实是可以保证的。
求最优方案总数
- 转移的时候同时记录方案数，变优了重新记录。
特殊的，普通背包无法做可以考虑辅助数组和加维度，或者可能观察转移来减少状态数。
例题
蓝色题：
P1782 分组和多重放在了一起，分别做一遍即可。
P2014 依赖性形成树形结构，考虑确定转移顺序并且多加一维表示在哪个节点上就好了。
P2515 放到了树上，发现环一定全选/全不选所以先缩点，然后就是选课。
P3188 背包也可以和状压结合，也可以跑多次背包。
P4158 不常见的转移方法+数组辅助转移。
P4322 树上背包时间复杂度是 \(O(n^2)\) 的性质+01分数规划。
P14508 寻找等价性质来减少状态。
紫色题：
P4516 考虑多加几个状态来转移，算是板子了（加上这个点选没选 和 这个点被没被覆盖）。
区间 DP
定义
区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。
令状态 \(𝑓(𝑖,𝑗)\) 表示将下标位置 \(𝑖\) 到 \(𝑗\) 的所有元素合并能获得的价值的最大值，那么 \(𝑓(𝑖,𝑗) =\max\{𝑓(𝑖,𝑘) +𝑓(𝑘 +1,𝑗) +𝑐𝑜𝑠𝑡\}\)，\(𝑐𝑜𝑠𝑡\) 为将这两组元素合并起来的价值。
性质
区间 DP 有以下特点：
合并：即将两个或多个部分进行整合，当然也可以反过来；
特征：能将问题分解为能两两合并的形式；
求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。
经典做法：
- 考虑枚举最后/第一步。
- 考虑固定序列最后结尾的数来方便计数。
怎样处理环
考虑倍长链然后对 \(n\) 个答案取 \(\max\)。
例题
P2470 典型的定义。
P7414 套了个结论的板子。
P3147 能用倍增写的区间 DP。
一类源于关路灯的经典模型：
某些路灯你要在某个时间（后）才能关，你速度有限，问关完所有路灯最小代价。就是先找到一个转弯的性质就好了。
-
P11432 反向关路灯
-
P2466 比较难预处理，其他一样。
-
P4870 代价有点不一样（这个是某一时间前才有贡献）。
P4766 枚举最后一步，\([l,r]\) 代表完全被其包含。
P9493 发现从两侧到中间填数很好计算贡献，所以就变成了区间 DP。
P13586 发现两个入栈出栈匹配形如区间匹配然后去递归，所以用区间 DP，解决。
DAG 上的 DP
\(DAG\) 有很好的 DP 性质。我们可以和拓扑排序等结合在一起就很能搞了。
而 DAG 的 dp 主要是利用一些问题的二元关系构造 DAG 图建模。
DAG 连通性
我们会考虑 \(bitset\) 优化 DP，然后就是 \(O(\frac{n^2}{w})\) 了。
题目
P4099 经典例题，DAG 上拓扑序个数，（虽然我现在还不会）。
DAG上的DP问题 搜到的博客。
省选联考 2025 追忆
树形 DP
树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的，他可以结合很多性质，所以比价杂乱也比较多样，主要是用上了树的性质。
AT_agc007_e 从这道题你就合一看出来能有非常多种优化方法。
hdu7401 从这里你可以看出来状态定义的多样性。
因为太多种所以对题目分类给出需要注意的点。
例题
P1269 简单贪心为基础的dp。
P1270 依赖性背包，但还是板子。
P1453 P1543 加强到了基环树，对基环树我们有很多种处理：
- 拓扑排序找环。
- 单调队列处理直径。
- 分类讨论处理环上染色/计数。
- 把环拆开做 \(O(n)\) 次树形 DP。
P2607 基环树的判断（所有点有一个出度/入度）分别对应内向/外向基环树。
P3177 树上背包复杂度为 \(O(n^2)\) 的来源。
P3237 性质题，确实要降蓝。
P3574 P5521很经典的模型：
- 我们设计状态 \(g_i\) 表示完成 \(i\) 内所有人的最短时间，\(f_i\) 表示走完需要的最短时间。
- 考虑怎么访问最优，显然是让 \(g_i-f_i\) 从大到小排序来访问咯（邻项交换证明）。然后转移的时候注意 DFS 和 DP 要分开否则数组移动会出问题。
- 有些会套一个二分 ，比如下面这个题：巧克力糖果
P6554 比较麻烦的换根。
P6594 贪心+二分的 DP。用了极差的性质，枚举时点的权在一个范围内，枚举这个范围。
continue...