对于一个题目，我们有暴力搜索算法。而 dp 就是尽可能将同一类的东西合并到一个状态上。
如何检查 dp 的正确性？
- 检查集合内部转移是否一致。
- 检查方案数是否正确。
状压 dp
有好几种状态压缩的方式：
- 记录“选了哪些东西”这样的信息，可以用一个长度为 \(n\) 的 01 串，对应一个十进制数。
- 记录可重无序集合：如果不关心顺序，只关心它们分别出现了多少值，可以记录无序集合，如果集合内的数字之和保证小于等于某一个数 \(S\)，那么状态的个数小于 \(S\) 的分拆数，大概 \(53\) 以下的分拆数能过。
- 网格图，考虑一行一行转移，然后要记录 \(1 \sim i\) 行的信息，比如黑色格子组成的连通块，使用最小表示法：考虑同一个连通块上所有点用一个数字来表示，但是从左到右数字第一个出现的位置符合升序。这样就可以一格一格转移。
- 插头 dp：高进制状压。可以自己定义的东西。
其实相当于哈希了。状态给他搞成一个方便处理的数字或者数组。
树形 dp
换根 dp：先求出子树内的所有点到自己的影响，然后求出子树外的所有点到自己的影响，先从下往上做，然后从上往下做。
树形背包：背包大小为 \(m\) 的树形背包，复杂度为 \(O(nm)\)。
拓扑序相关：
如果带修：结合树剖线段树等算法一起做，用矩阵。
区间 dp
什么时候会想到区间 dp：转化出无交的情况。
数位 dp
如果考虑进位的，从低到高来；考虑比较大小的，从高到低来（比如某一个区间，那么考虑是否和原数前面几个数都一样），需要记录的记录一下就好了。
自动机上 dp
AC 自动机上可以 dp。但是我们现在说的是自己建立自动机的 dp：三步骤：考虑我们的状态，将每个可行状态当成一个节点，然后搜索出转移，最后直接跑 dp。算出的是精确状态数，可能可以缩小一些状态数。
这个做法是建立了一个自动机，因为自动机其实是基于 dp 建立的所以我们叫它 dp 套 dp。
一般用来解决这样的问题：
- 如果给定一个字符串，可以使用 dp 判断它是否合法。
- 需要求每个位置在许多字符中任取的时候有多少合法的串。
我们的方法是：直接对记录状态的那个 dp 数组进行压缩，然后根据内层 dp 的转移，建立一个自动机，然后在这个自动机上跑 dp。
QOJ1251. Even Rain
这题目，我设计状态的时候，考虑钦定目前 dp 的位置是前缀 max，然后状态 \(O(nk)\)，转移 \(O(k^2)\) 并且很复杂；可以将前缀 max 的位置放进状态，然后 \(O(1)\) 转移。
给我的一个教训是：如果某一个状态，要么要加入进状态里面，要么要 dp 它，都是躲不开的，那么考虑加入进状态可能会比 dp 它少判断很多东西，并且更优。