常规DP篇

问题转化

动态规划的核心是将问题转化为一些子问题。

根据子问题可以分类为：

1. 覆盖问题

例如，要覆盖所有点，可以将状态设计为覆盖一段前缀，并且中间不允许出现断点。

2. 匹配问题

通过记录匹配的端点信息和权值来解决问题。
例如，The Karting 问题中，选端点作为 $dp$ 的主体，转移中用到了费用提前计算的思想。此外对于匹配问题（比如这道题是端点的配对），首先拆解贡献到匹配点上，考虑到某一个匹配点时候带着贡献和需要匹配的变量转移，这样就能够保证转移的顺序性。

3. 末状态性质：

对于多过程的问题，可以考虑末状态的性质，并直接对末状态进行计算。
例如，在期望题中，通过观察发现等概率出现的方案，直接对此方案计数，如绿宝石之岛。

4. 立体空间（高维）问题减少变量

通过 45 度旋转将问题的变量从多变少，如 Jumping sequence。

5. 简化问题

尽可能地简化问题，例如将具有平行关系的点缩在一起。
例如，Black, White and Grey Tree 问题中，把一个同色的连通块缩成一个点。

6. 计数问题转化

转换DP主体。
Trick:计数问题中所有限制问题优于存在限制问题

7. 分类讨论

分类讨论除去无效状态

8. 子序列问题转化

通过证明不交转化成区间问题，尽量向简单的 DP 模型靠拢。
例如，在 AmShZ Wins a Bet 问题中，通过区间问题求解。

寻找子问题

寻找子问题的核心思想是找状态之间的相似性。

制造限制

CF1439D 顺序匹配问题中枚举空位

辅助数组

不能归纳到DP数组的信息用辅助数组转移

枚举法/等效子问题

对于不能处理的有关元素，寻找当前问题的等效子问题，就可以把这个影响传递下去，完成转移，或者可以通过枚举法来消除所谓影响。

那么怎么找等效子问题呢？

1.多角度思考：
从不同角度思考问题，找到最优解。例如，从不同限制主体或不同维度入手解决问题。

2.类比法：
通过类比相似问题，找到解决当前问题的方法。例如，通过类比已有的 DP 问题，找到适用的转移方法。

3.归纳法：
通过归纳具体实例，找到一般规律。例如，通过具体实例归纳出状态转移公式。

以上方法是基础分析法，也是通用的。

发掘性质

DP问题的解密中性质是线索。

1. 发现性质：

当直接 DP 需要考虑的情况太多时，可以手动寻找一些最优解需要满足的必要条件，从而有的放矢地进行 DP。
例如，CF1368H1 和 Division into Two 问题中，通过手动寻找条件简化问题。

2. 猜测性质：

在限制较少的题目中，可以猜测性质以简化问题。
例如，CF573D 问题中，当限制条件不多时（比如本题只限制了某人不能匹配某马），那么可以强行摆脱限制（比如本题证明是跨越三个点那么怎么限制都阻止不了你调整），调整法是很重要的思维方式。

3. 讨论特殊情况：

通过讨论特殊情况可以发现好的性质。
例如，泳池问题中，讨论 0 的情况得到调和级数的性质。

4. 递归方法：

当限制主体数量级巨大时，可以考虑通过归纳、递归的方法描述限制，并且这种方法很容易拓展到 DP 形式。
例如，Density of subarrays 问题中，通过递归描述限制。

决策状态

选定DP主体，并产生一些关于决策和转移的想法。

1. 多个量分讨

把问题改成多个量选/不选的问题，并尽量独立它们的影响，用 DP 决策这个过程。

2. 排除冗余

限定方式排除多余的方式。

3. 计数题

思考什么量可以用计数原理快速算方案，然后用 DP 决策这些量。

4. 枚举法

使用枚举法帮助思考需要决策的状态，然后用 DP 加速枚举的过程。

5. 选择 DP 主体

例如，在 CF1474F 问题中，选择 x 轴为 DP 主体不容易，但选择 y 轴为 DP 主体问题迎刃而解。对于偏序关系更高级的理解，可以从不同的限制入手。

6. 整体思想

例如，卡农问题中，以集合为主体而非数。

7. 值域规划

遇到集合最优化问题时，可以考虑在值域上规划，选值域为 DP 主体。
例如，CF1463F 问题中，通过值域规划加数论简化问题。

设计DP状态

确定以上步骤后，开始设计DP状态。

1. 保留相关量：

只保留和代价计算有关的量，如果代价只和数量有关，并且可以通过数量还原出集合，可以将状压的一维改成线性。
例如，CF1188D 问题中，通过线性状压简化状态。

2. 枚举大状态：

当状态很大时，可以通过枚举将某些量拿出状态。
例如，Game with Cards 问题中，通过枚举简化状态。

3. 全局变量局部化：

当问题前后相互影响时，可以将全局变量定义到局部状态中。
例如，密室逃脱 和 Red and Black Tree 问题中，通过局部化全局变量简化问题。

4. 设计相反状态：

设计相反状态，如最小花费步数转化为最大减少步数。
例如，Paint 问题中，通过相反状态简化问题。

5. 取代状态

把和限制紧密贴合的量设计到状态里面，阴间出题人可能会用题目描述来引导你设计非常慢的 状态，做一些基本的题意转化即可：皮配

确定DP顺序

DP顺序在一部分题中很重要，它的技巧与用处有以下

1. 操作主体：

时间顺序并不能区分事件时，用XXX事件完成状态来解决。

2. 单向影响：

如果一个东西对另一个东西有单向影响，先处理前面那个有助于考虑影响。

3. 图问题顺序：

在图问题中，通常选择单调的一维作为顺序维，例如时间。

4. 修改顺序：

DP 顺序尽量让限制紧凑，在独立前提下篡改顺序。集合选数

5. 限制影响状态

可能需要根据限制的特性，提前或延迟计算一些状态。

6. 顺序减少状态

合适的 DP 顺序可以减少 DP 状态。

考虑如何转移

对于以上转移信息的补充。

1. 大步小步：

大步适于考虑转移，但可能复杂；小步适于考虑转移，但可能耗时。
例如，Appleman and a Game 问题中，通过大步小步切换优化转移。

2. 计数 DP 顺序：

转移中存在的限制很烦，在一些计数问题中，对于多个元素的限制可以考虑某些元素任意选，另一些元素为了满足限制而具有确定的选法。此外，计数 $dp$ 中选择的顺序是十分重要的。
例如，卡农问题。

3. 复合 DP：

设计多个 DP 状态，互相转移的方法。
例如，模拟赛6*A 和 CF1439D 问题中，通过复合 DP 优化转移。

4. 不同 DP 模型：

考虑不同的 DP 模型和复合 DP。
例如，密室逃脱 问题中，通过复合 DP 优化转移。

5. 正难则反

正难则反是很重要的技巧，比如在计算第一次到达的方案数的题目中，容斥掉的项就是子问题。

6. 限制拆分

可以把限制的判断拆分到转移中进行。

1.2 高阶动态规划（Advanced DP）

1.2.1 状态压缩

1.基本概念：
* 状态压缩用于减少状态数量，常用于解决高维状态问题。例如，将多个布尔变量压缩成一个整数表示。

2.应用场景：
* 例如，集合覆盖问题、旅行商问题等。
* 例如，在 CF1188D 问题中，通过线性状压简化状态。

3.实现方法：
* 使用位运算进行状态压缩，例如，通过掩码操作处理多个布尔变量。

1.2.2 树形动态规划

1.基本概念：
* 树形 DP 用于处理树结构上的动态规划问题。通过树的分治思想，递归处理子树问题。

2.应用场景：
* 例如，树的最长路径问题、树的子树计数问题等。
* 例如，在 航天基地 问题中，通过树形 DP 优化。

3.实现方法：
* 通过递归处理每个节点的子树信息，然后将子树信息汇总到父节点。

1.2.3 斜率优化

1.基本概念：
* 斜率优化用于处理具有单调性的 DP 转移，常用于解决凸函数或凹函数相关的问题。

2.应用场景：
* 例如，最小化或最大化线性函数、处理具有单调性的最优解问题等。

3.实现方法：
* 使用单调队列或单调栈维护斜率，快速找到最优解。

1.2.4 凸包优化

1.基本概念：
* 凸包优化用于处理二维平面上的最优解问题，通过维护一个凸包，快速找到最优解。

2.应用场景：
* 例如，处理二维平面上的最近点对问题、最优线段问题等。

3.实现方法：
* 通过维护一个动态凸包，使用二分查找或扫描线方法快速找到最优解。

1.3 实战技巧

1.3.1 快速调试

1.打印中间状态：
* 在调试过程中，通过打印中间状态检查 DP 转移是否正确。

2.测试边界情况：
* 通过测试边界情况，确保 DP 程序在所有输入情况下都能正确运行。

1.3.2 优化复杂度

1.降低时间复杂度：
* 通过优化 DP 转移过程，减少不必要的计算。例如，使用前缀和或差分数组减少复杂度。

2.降低空间复杂度：
* 通过优化状态表示，减少空间占用。例如，使用滚动数组优化空间复杂度。

1.3.3 思维拓展

1.多角度思考：
从不同角度思考问题，找到最优解。例如，从不同限制主体或不同维度入手解决问题。

2.类比法：
通过类比相似问题，找到解决当前问题的方法。例如，通过类比已有的 DP 问题，找到适用的转移方法。

3.归纳法：
通过归纳具体实例，找到一般规律。例如，通过具体实例归纳出状态转移公式。

总结

动态规划是解决复杂优化问题的有力工具。通过系统掌握动态规划的思维过程和高阶技巧，可以高效解决各种实际问题。在实际应用中，灵活运用这些技巧，结合具体问题的特点，设计出最优的解法。