常规DP篇
简单总结：
对问题进行类比转化，
（将问题转化为子问题。）
（发掘性质）
寻找DP主体，并产生一些关于决策和转移的想法。
设计DP状态
（设计DP顺序）
设计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. 限制拆分
可以把限制的判断拆分到转移中进行。
真实思考逻辑
采用梦熊OJ提高组题目来讲解：
给定 $n,V$ 和一个长为 $m$ 的序列 $(p_1,q_1),(p_2,q_2),\dots,(p_m,q_m)$。
请求出有多少长度为 $n$ 的正整数序列 $a$，其所有元素 $a_i$ 满足 $1\le a_i\le V$，将其按 $k=1,2,\dots,m$ 依次执行如下操作后，$a$ 不降：
- 若 $a_{p_k}>a_{q_k}$，则交换 $a_{p_k}$ 与 $a_{q_k}$ 的值。
答案对 $10^9+7$ 取模。
$n<=18, m<=500, 1<=V<=10^9$
首先，本问的$a_i$不降的条件，会对计数带来一定重复，所以需要标注排列中不同数字的个数。
然后，采用全排列型要求的DP算法(总和为$O(3^nn)$)，复杂度很接近了，但是询问的限制不能归纳到DP数组里，明示需要发掘性质解决。
现在，最重要的是回顾思路，很多时候你都会发现一些问题，不要紧张，再去试试别的方法，或者改一下已有的方法就行。
首先，我们意识到元素的相对大小是关键，然后想到将它加入到DP数组中，然后意识到了DP数组的递推性质，可以设F(S,i)为i标号的S状态下的的答案有多少个。这个DP复杂度是$O(3^nn)$的，事实上，这种简单的逻辑链我也思考了10分钟以上，这是因为意识到什么能够符合DP数组的性质并不容易。
紧接着，只要这个元素能被交换到最后即可，采用辅助数组，统计出任意一组元素是否可以被交换过去即可。最后统计答案即可。
采用高维前缀和技巧的话，复杂度会降到$O(2^nn^2)$水准。
这样我们就解决了一道乙中的问题。
