动态规划总结

· · 个人记录

动态规划在考试中一直都是一个大头项，此处仿照 OI-Wiki 的方式对 DP 进行总结。

背包 DP

背包分为：01 背包（每个只能选一次），完全背包（每个选择无限次），多重背包（每个可以选若干次），依赖背包（有前置需求），分组背包（同一组只能选若干个）。

01 背包

通常为双层 DP，第一层枚举物品，第二层枚举容量，第二层需要逆向。

  1. 双栈使01背包可逆。 在使用双指针优化 dp 时，有时并不容易进行删除操作，此时我们就可以使用两个栈来维护我们的双指针。例题：版子。

完全背包

通常为双层 DP，第一层枚举物品，第二层枚举容量，第二层需要正向。

多重背包

一方面，可以通过二进制将若干相同物品压成一个物品，化为 01 背包，另一方面，使用单调队列。

依赖背包

类似于一个树形结构，在每个儿子间 01 背包即可。

分组背包

将一组的背包一波一起转移即可。

区间 DP

区间 DP 的状态与一般的 DP 不大相同，f_{i,j} 表示区间 i\sim j 的答案，多为左端点与右端点匹配型，多为由左端点 +1，右端点 -1 转移而来，有时可以改用记搜更为便利，相信最为经典的区间 DP 无疑有他，就是我们的石子合并。

常见技巧：拆环成链，左右端点标记，四边形不等式一维优化，四边形不等式二维优化。

标志的数据范围应当在 10^2 \sim 10^3 级。

树形 DP

树形 DP 典型的应该是这题。
在处理时，发现有若干对矛盾或是依赖的情况并且形成一个有向无环图，抑或是树形时，就可以使用。
分类：

  1. 链上的 dp，其实感觉和线性 dp 区别不大，在链上的 dp，常常利用树链剖分。
  2. 子树内的 dp，在几个子树间选择、决策。

小技巧：

  1. 上下界优化（常见技巧）。
  2. 继承优化（让重儿子继承父亲的指针，这样不需要在重儿子转移（有点像树上启发式合并？）），Hotel加强版。
  3. 换根这个技巧，应该不用说才对，用来维护转移根节点时，只有几个节点的 dp 数组发生变化，[POI2008] STA-Station。
  4. 树链剖分，只能说非常好用。对于路径上的 dp，但凡线性上可以使用线段树维护，基本上都可以用树链剖分。[TJOI2015] 旅游 。
  5. 倍增，适用性强，但是常数略大。
  6. 树上启发式合并（Dsu on Tree)。
  7. 长链剖分优化。
  8. 不知道这几年发了什么疯，常常与二分结合[NOIP2012 提高组] 疫情控制。

状压 DP

状压 dp 是运用二进制枚举来进行转移的 dp，其数据范围极具特色，多为 10\sim 20，基本上一眼可以观察出。状压 dp 不仅是一部分题目的正解，而且大部分题目皆会以状压 dp 的数据范围出一部分的部分分，是骗分爱好者不可不学的技巧，但是，缺点在于优化的没有前途。

一部分技巧:

  1. 子集枚举优化至 O(3^n)：for(int P=st;P;P=(P-1)&st)。
  2. 贪心进行转移。
  3. 找基准点进行转移。
  4. 状态压缩：
    1. 将二维压成一维。P4297 [NOI2006] 网络收费。
    2. 将确定的一个二进制位压走。
  5. 以某个结点为一维进行辅助转移。最小斯坦纳树。
  6. 双向状压，类似于 meet in the middle。P4799 [CEOI2015 Day2] 世界冰球锦标赛。

数位 DP

数位 dp 往往都是这样的题型，给定一个闭区间 [l,r]，让你求这个区间中满足某种条件的数的总数。
数位 dp 实质上就是正常的 dp，是按照每一个数位进行决策，然后再进行记忆化而已。
其数据范围与状压 dp 同具特色，多为 10^{9}\sim 10^{100000}，此类题只有几种可能：数学、循环节、倍增、特殊以及数位 dp。

多以记搜写法，简单方便，但是在需要优化空间时，就要转化成递推，滚动数组即可。

概率 DP

概率 dp 同下方的计数概率 dp 是最令人讨厌的两大 dp，题目特色体现在题面。
简单技巧：

  1. 从最后结果转移到起点，ABC314E。
  2. 多与高斯消元或状压结合。

期望 DP

烦人题，简单总结一下方法。

  1. 容斥。
  2. 高斯消元。
  3. 有时在贡献较小时，可以转化成概率 dp，即期望等于 \sum 贡献 \times 概率。P9346 无可奈何花落去。

计数 DP

计数 dp 是 dp 中最为烦人的之一，没有一个大的方向感，只能靠刷题锻炼题感，题目特色体现在题面。

  1. 不重不漏
  2. 围绕基准点来防止重复，CF559C。
  3. 等效代换，离散化思想：
    1. 用 1\sim i 的数，最左边的为 j。
    2. 用 i 个不同的数，最左边的排名为 j。
  4. 将等于转化成小于等于，再用容斥求解。
  5. 利用根号分治。
  6. 计数转概率，乘上总方案数。HDU5378。
  7. 与组合数学常常结合。

DP 优化

空间上优化

空间上，有时可以将可行型的二维数组，转化成一维的最优解，或是用 bitset 优化。

时间上

在写 dp 时，常常会出现一些极具性质的转移，此时我们可以优先考虑优化转移，实在不可，再优化状态。

数据结构优化

用线段树的区间修改，区间查询维护转移，可以在转移时发现多为区间上的修改，即可使用。
使用树状数组，适用范围与线段树相似，但是常数更小，也有一点约束性。
使用单调栈，多为在没有查询范围，但是在某个权值上的最优转移，大多与其他优化方式相配合，如斜率优化。
使用单调队列，多为转移有区间限制，并在某个权值上的最优转移，如经典滑动窗口。

分治优化

  1. 根号分治 对于一些问题，我们在某一个值小时另一个就大，这个值大后另一个值就会变小，我们就可以利用这个小的值来优化。
    例如：哈希冲突。

  2. CDQ分治 主要用来维护三维偏序，是比较经典的解法。 第一维，通过主函数排序。
    第二维，通过归并中合并解决。
    第三维，通过数据结构解决。
    三维偏序（陌上花开）。 OI Wiki。

  3. 分治

    1. 可以对中间结点分开分治。
    2. 对于最大值进行分治。

斜率优化

在转移时我们有时会得到 f_i=\min f_j+q_i*g_j 这样的转移式，我们并不能简单进行转移，因此我们使用 CDQ 分治或单调栈或二分解决或李超线段树。
[SDOI2012] 任务安排。 OI-Wiki。

四边形不等式（决策单调性）

决策单调性指的是形如 f_i=\max(f_k+c)，称最终修改的下标的最佳转移点为k_i，对于 \forall j<i,k_j\le k_i。

设 w(i,j) 是定义在整数集合上的二元函数。若对于定义域上的任意整数 a，b ，其中 a< b，都有 w(a,b+1)+w(a+1,b)\ge w(a,b)+w(a+1,b+1) 成立,则称 w 满足四边形不等式。

可以用来辅助转移一维 dp，二维 dp。 OI-Wiki。

矩阵优化 dp

在转移时，发现转移的方式都是一模一样的，并且转移次数极多，可以考虑用矩阵优化我们的 dp。 使用矩阵快速幂来优化转移次数，可以将一个次数极多的转移优化至 \log 级。

特殊小技巧

  1. 在转移时间复杂度较小时，并且有修改操作时，可以使用线段树来辅助转移计算。[COCI2015-2016#1] RELATIVNOST
  2. 有时，我们可能不仅仅可以记忆化我们的 dp 数组，我们在辅助转移中，可能也有一部分是反复计算的，同样可以记忆化。为了方便，有时可以使用间接递归来解决。P9229 扩展九连环。
  3. 高斯消元可以使用稀疏矩阵优化，可能可以拿到更多的分。