hzy's DP

要求：

最优子结构：求解 i 需要 j k 两个状态，用到的一定是 j k 的最优解

无后效性：
只关心状态值，不关心状态是如何推出来的。
状态一旦确定，不会受到之后阶段的决策的影响
只关注 j k 的最优解，而不需要考虑是否有可能使用了公共的资源而导致最终解不合法

常见类型：

序列DP：
状态 [ i ] 表示前 i 个元素组成的状态。
状态 [ i ] 表示用到了第 [ i ] 个元素时组成的状态。

区间DP：
常见的转移是枚举中间的断点 k，拆分成 [ l , k ] 与 [ k + 1 , r ]
有时候可以用四边形不等式优化
有时候性质特殊，可以从 [ l + 1 , r ] 或者 [ l , r ? 1 ] 中的一个转移

数位DP：
按照数字的位数划分状态进行 DP
一般为求 [l,r] 中满足条件 P(i) 的数字个数
通常来说上界会很大，暴力枚举会超时（比如 10^18）
条件 P(i) 通常与数字的大小无关，而与数字的组成相关
原始形式 —— f [ i ] [ 0 / 1 ]，考虑到数字从高向低第 i 位，前面的数字是否达到上界(如数字上界为1234，前 3 位枚举了 123，则这一位只能枚举 1 ~ 4，而不是 0 ~ 9)
考虑DP时，先设计一个最简单的状态，看看能不能转移到下一状态，若无法转移，则考虑增加维度（如加上之前状态对当前状态产生的“影响”）
正推可能比逆推容易

概率DP：
设状态 f [N] 表示距离目标还差 N 步时的期望
根据每一步决策的概率写转移方程 ： f [ i ] [ j ] = p ? f [ i ? 1 ] [ j ] + (1 ? p) ? f [ i ] [ j ? 1 ]
期望：
E( X + 1 ) = E( X ) + 1
E( ( X + 1 ) ² ) = E( X ² ) + 2 * E( X ) + 1
有可能会自己转移到自己，这时需要移项代数变形

状压DP：
一般会先将所有合法状态搜出来，然后编上号进行 DP

记忆化搜索：好写

优化：

转移过程优化：

单调队列：
f [ i ] = min { g( j ) | L[ i ] ≤ j < i} + w( i )
L[i] 随 i 单调不降， w( i ) 是转移方程组仅和 i 有关的部分，g( j ) 是转移方程中仅和 j 有关的部分
对于 k < j 有 g( k ) ≥ g( j )，那么决策 k 就是毫无用处的，用单调队列维护 递增

斜率优化：
存在 i j 的交叉项
一个数列 a[] 分成若干组，一个组 [L, R] 的代价为 M + ( ∑( L, R ) ai ) ²，求分组的最小代价。
? f [ i ] = min{ f [ j ] + ( sum[ i ] ? sum[ j ] ) ² | 1 ≤ j < i } + M

减少冗余状态
根据 DP 方程寻找优化的方法，可以尝试修改一下状态的定义

计算过程优化：

部分和优化：前缀和

矩阵快速幂：转移方程中的系数为常系数，转化为矩阵相乘 O(log n)

状态设计优化：

交换答案与状态：
LCS，n ≤ 1e6, m ≤ 1e3 —— 答案与第一维对调，通过预处理 A 的每一位的下一个 a, b, . . . , z 出现的位置，O(m ² + 26n)