dp 专题总结

基础准备

当一个问题较为复杂，而它与子问题之间表现出良好的关系时，我们通常可以考虑由子问题推出原问题的答案。然而某些子问题会在被利用于求解原问题时重复求解，使得复杂度提高；因为原问题存在多种子问题的分解方式，有可能因为选择了不当的分解方式而使得复杂度提高。上述两个问题分别对应了 问题与子问题的求解顺序问题 和 问题状态的设计问题 ，我认为 dp 的核心就是探讨这两个问题的做法，即 dp 中的 dp顺序 和 dp状态，当然 dp优化 也在 dp 状态这一块中占据了很大的位置。这两者（或者说三者）是互相联系的，通常需要同时进行考虑。

dp 可以解决的问题类型有二：最优化问题和求某个值，如果是求某个值的话更加偏向于递推问题或计数类（说实话这两类问题有什么区别吗。。。

各种 dp 模型

• 区间 dp ：虽然说是区间 dp ，但早已从“区间”二字拓展开了。这类 dp 的问题通常能被描述成一个二元组 (x,y) ，而其从子问题的合并则是将两个二元组合并。

• 背包 dp：

  这类问题要求规划一些物品的选择方案以实现在代价和法的情况下价值最大化，所以问题状态通常有两种：价值总和和容量，对应的每个物品有两个属性：价值和代价。

  物品之间的 dp 顺序通常无关全局答案紧要，有时合理安排物品顺序可以做到子问题的重复利用。

  同时背包在物品顺序这一维上还具有一些神秘的可合并性。

  • 01 背包：最简单的背包，每个物品只有两种选择状态（可分别用 0 和 1 来表示，即名称的由来）

  • 完全背包：每个物品有无数个。

  • 多重背包：每个物品的数量给定。

  • else：通常都是物品与物品之间有某些依赖关系，然后要综合利用以上三种背包综合解决。

• 状压 dp：通常问题的某些维度中含有数量复杂度较高的类型，比如将一个大小为 n 的集合的所有状态作为一个维度，其复杂度是 O(2^n) 的，又或者是一个排列，那就是 O(n!) 。但由于这些维度 n 的规模较小，因此可以直接枚举 dp 。

• 树形 dp：一类在树上进行的 dp ，dp 的基本范式是从子节点（同时也是子问题）的解递归合并到父节点，最后获得整颗树的答案。

• 计数 dp：顾名思义，就是专门计数的 dp ，所以其实下面的数位 dp 可以算是计数 dp 的一种。没有固定的模式，需要组合数学知识（倒不如说它就是专门考这个的？

• 数位 dp：一类基于数字的位与位之间关系的计数 dp ，几乎都是要求求解满足某些数字特征的数有多少个。

dp 中较为通用的 trick

• 倍增优化：有时会有这样的状态：每次单步转移 n \rightarrow n+1 ，然而 n 可能非常大，而转移又满足一些奇妙的可加性（有点类似向量的加性），这是就可以将单步转移改为每次转移 2^i 步，就可以将一个维度的复杂度降至 O(\log n) ，比如这题：P3509 [POI 2010] ZAB-Frog，很容易处理出每个点单步转移后的结果，然而因为跳跃次数太多，而这种“跳到下一个点”的转移符合可加性（A \rightarrow B=A \rightarrow M \rightarrow B），所以可以将跳的次数维度倍增设成“跳 2^i 次后”。

• 破环为链：应用很广的一个技巧，在 dp 中主要就是特殊处理环断处的状态和转移，例：P6064 [USACO05JAN] Naptime G 。

• 贪心优化：应用这个技巧优化某个状态时，只需不断问自己：是否只关心这个状态的最值？一个很经典的应用是将 bool dp 数组转为 int 数组从而减少枚举某一维状态的浪费，例：CF1476F Lanterns

• 交换状态和值：来自记忆深处某道题的经验，想不起来是哪题了。貌似需要上一个贪心技巧作为状态和值交换的桥梁。

• 子问题直接计算对全局的贡献：适用于子问题的解受到其他非包含子问题影响（即两问题有交但并不是包含关系），且影响可拆分的情况，例：P3177 [HAOI2015] 树上染色 。

• 减少暴力 dp 的状态：先暴力 dp ，然后一步一步通过分讨/发现冗余信息（可以通过联系所求或性质）减少所记状态数，例：P12546 [UOI 2025] Convex Array

杂项

一段一段转移的 dp

有这么一类在序列上进行规划的 dp ，方程通式长这样：

w(l,r) 是区间 [l,r] 的价值函数。

姑且不论 w 的计算代价，光是枚举状态通常就已经有 O(n^2) 了，然而对于不同的 w 及待选决策 j 的边界有不同的优化 dp 转移的方式来降低这一复杂度。

• 单调队列优化

用 P10978 Fence 作为例子，设 f_{i,j} 表示前 i 个人刷满前缀 j 的最大收入，分类讨论后其中一条柿子是

即

像这种左右边界随 j 单调，w 只与待选决策有关的情况就能用单调队列优化，这里就是维护 f_{i,j}-jP_i 。

• 线段树优化

改一下刚才的柿子（顺便简化一下）：

这下左右边界的单调性没了，但仍然满足 w 只与待选决策有关，所以通过添加一个 \log 的复杂度将单调队列变为线段树等数据结构仍然可以做。

有时可能 w 还会遇上绝对值符号，通常做法是拆开分正负分别搞。

如果使用平衡树等数据结构还能支持更复杂的操作。

剩下的还有斜率优化和四边形不等式优化（感觉 noip 不会考所以先不写）

排列插入段 dp

例题：P5999 [CEOI 2016] kangaroo

一般就是规定升序或降序插入排列的每一个数，设 f_{i,j} 表示已经插了前缀 i ，分成了 j 段的答案，插入转移一般是考虑四种情况：插入段头，插入段尾，开新段，合并两段，注意这里的插入是相对插入而非绝对插入，所以可以看出这里本质是将对每个合法排列计数转换为对合法插入或合并操作序列计数从而使得问题可以被规划。