前言
本【指北】适合正在学习 DP 的 OIer。
本【指北】中不仅有简单内容，还有较难内容，总体来讲适合不同水准的选手。
本人才疏学浅，请大佬们在评论区中指出错误，我会加以改进与完善！
Part 0 DP 是啥
What is DP? What can DP do? What can't DP do?
动态规划（Dynamic Programming），简称 DP。
DP 能干嘛？我为啥不贪心？
- 基础的 DP 较为简单，且容易实现。
- DP 能够得到贪心获得不到的正确答案。
- DP 可扩展性强，你可以在大部分地方使用。
（点名表扬某 AI, 打 CF 全写的是 DP）
这么说，DP 是万能的？不不不。
下面列出了 DP 的部分缺点：
-
复杂度较高，有些时候需要优化
-
手推柿子需要有一定数学基础
-
对新手不太友好
-
不太好理解
-
标准式用处不大，只能用于概念的理解
-
状态设计需要结合题目
不过，我们面对部分问题，仍有相应的解决方案。
话不多说，开始踏上我们的学习路程吧！
Part 1 线性 DP
线性 DP，顾名思义，就是给你一条直线，以直线上的点坐标为状态，答案从之前已决策过的点中转移过来。
下面给出线性 DP 的一般式（非标准，自己总结的）：
\[f_i = f_{i - a} + v \]我们结合一道经典例题进行讲解：
以 P1095 守望者的逃离为例。题目链接传送门
在这道题里面，我们发现可以把时间套在 \(i\) 上，那么进行分类讨论（设 \(f(i)\) 为当时间为 \(i\) 时，策略是魔力能耗则耗，不能耗则恢复的最大的行走距离；而 \(M\) 为当时间为 \(i\) 时，能耗则耗，不能耗则恢复的魔力数目 ）：
① \(M \ge 10\)
显然，消耗魔力闪现比走路更快，能耗则耗，选择消耗魔力。
此时，\(f_i = f_{i - 1} + 60\)，\(M\) 减去 10。
② \(M < 10\)
显然，他耗不动，所以尝试停下来。
此时，\(f_i = f_{i - 1}\)，\(M\) 加上 4。
接下来，如果停下来回魔力的状态比不耗魔力走路的状态要慢，那选择不耗魔力走路。
为什么是对的呢？
显然，我每一个状态都有最优子结构，我每一个状态只从前面的最优的状态转移过来，自然是对的。
回顾一下内容。接下来提供几道例题：
摆花 甚至不需要分类讨论。
乌龟棋 暴力 DP。
Part 2 背包问题
背包问题，顾名思义，就是给你一坨没有价值有重量的物品，一個有容量的背包，让你把价值总计最大的那些物品扔进去。
那么，我们根据物品可取几个，将背包问题分为了 0/1 背包、多重背包和完全背包。
Part 2.1 0/1 背包
物品只能取一个或零个。
下面给出 0/1 背包的一般式（设 \(f_{i, j}\) 为考虑到第 \(i\) 个物品时，背包容量为 \(j\)）：
\[f_{i, j} = \max \begin{cases} f_{i - 1, j} \\ f_{i - 1, j - w_i} + v_i \\ \end{cases} \]① 不取
此时，相当于考虑到第 \(i - 1\) 个物品，而不消耗容量，即 \(f_{i, j} = f_{i - 1, j}\)
② 取
此时，相当于考虑到第 \(i - 1\) 个物品，消耗 \(w_i\) 的容量，而获得 \(v_i\) 的价值，即 \(f_{i, j} = f_{i - 1, j - w_i} + v_i\)
Tips
有些题目的空间限制会把你卡没，所以考虑优化。
我们看到 \(f_i\) 只与 \(f_{i - 1}\) 有关系，所以将表示考虑到第 \(i\) 个物品的那一维去掉，即：
\[f_j = \max \begin{cases} f_j \\ f_{j - w_i} + v_i \\ \end{cases} \]注意将体积 \(j\) 倒着遍历，否则会取到当前这一行的状态。
这个优化像是将数组滚动起来，因此被称为滚动数组优化。
Part 2.2 多重背包
物品可以取有限个。
下面给出多重背包的一般式（设 \(f_{i, j}\) 为考虑到第 \(i\) 个物品时，背包容量为 \(j\)，取 \(k\) 个物品）：
\[f_{i, j} = \max \begin{cases} f_{i - 1, j} \\ f_{i, j - k \cdot w_i} + k \cdot v_i \\ \end{cases} \]方程容易理解，下面考虑优化。
我们学欧姆定律时，有没有想过电阻箱的几个电阻为什么不是二的 \(k\) 次方？
于是我们想到，把每个物体最多能取的个数进行二进制的拆分，将问题转换为 0/1 背包，将时间复杂度优化至 \(\mathcal{O}(M \sum_{i = 1}^N \log_2 w_i)\)，十分优秀。
Part 2.3 完全背包
物品可以无限取。
下面给出完全背包的一般式（设 \(f_{i, j}\) 为考虑到第 \(i\) 个物品时，背包容量为 \(j\)）：
\[f_{i, j} = \max \begin{cases} f_{i - 1, j} \\ f_{i, j - w_i} + v_i \\ \end{cases} \]这是什么意思呢？就是要么不取，要么取。
这不跟 0/1 背包一毛一样吗... 等一下，第二项怎么改了？
是的，因为我可以仍在考虑这一物品时继续取，所以是 \(f_{i, j - w_i}\)。
跟 0/1 背包一样，完全背包也有优化，不过体积 \(j\) 是正着遍历的。
Part 3 区间 DP
顾名思义，以区间为状态进行转移，常用方程：
自两个区间合并而来的，枚举划分点 \(k\)（有时合并需要费用 \(w\)）。
\[f_{l, r} = f_{l, k} + f_{k + 1, r} + w \]注意区间合并时为了保证状态已经计算过，循环中第一维是步长（区间长度）。
下面结合一道例题：Zuma
先设计状态，设 \(f_{l, r}\) 为消除区间 \([l, r]\) 的最小花费。
则易知：
\[\large f_{l, r} = \min_{k = l}^{r - 1} \begin{cases} f_{l, k} + f_{k + 1, r} \\ f_{l + 1, r - 1} \quad (arr_l = arr_r) \\ \end{cases} \]就是说若两头相同，则可以转移自一个回文串（一个回文串首末加上同一个数还是回文串）。
否则枚举划分点，转移自两个区间之和。两者取最小值。
之后可以做做例题：涂色
Part 4 图上 DP
注：因为树形 DP 也算是图上 DP，所以不单独拎出来说了。
顾名思义，图上 DP 就是在一张图上做 DP。
本部分前置芝士：链式前向星、Tarjan 缩点、DFS。
对于每个节点，都进行 DP，那么常用方程如下（设 \(u\) 为当前节点，\(v\) 为可达的节点）：
\[f_u = \min\{f_v + w_{u \to v}\} \]关于例题，树形 DP 与图上 DP 的题目多得过于泛滥，而且方程多样，不再赘述。
若想看本人的例题讲解，请移步至（都是有思维量的题目，新手也可以先去写 选课、没有上司的舞会 和 二叉苹果树）：
小问题：
当你发现有环怎么办？
可以使用 Tarjan 缩点，使得原图变成了 DAG，这样就没有环的问题了。
Part 5 数位 DP & 状压 DP
注：由于这两种 DP 思想有点像，故将它们放在一起。
Part 5.1 数位 DP
顾名思义，数位 DP 即在数字的每一位做 DP。
能用在哪里呢？计数类 DP 有可能是。
下面结合一道例题进行分析：P2657 windy 数
根据题意，要我们求出 \([a, b] (a < b)\) 内的 Windy 数的个数。
思索一下发现可以先求出 \([1, a]\) 与 \([1, b + 1]\) 内的 Windy 数，然后相减即为正确答案。
那么就可以设计 DP 方程辣。设 \(f_{i, j}\) 为考虑到第 \(i\) 位上一位的数为 \(j\) 的方案个数。
方程很好写：
\[f_{i, j} = \sum_{k = 0}^9 \begin{cases} 0 &\quad (|j - k| < 2) \\ f_{i - 1, k} &\quad (|j - k| \ge 2) \\ \end{cases} \]不过求完之后还是得计算最终答案。设 \(ans_x\) 为 \([1, x]\) 区间内的 Windy 数，答案由三部分组成 (\(len_x\) 为 \(x\) 的位数，从高到低) :
- 所有位数小于 \(len_x\) 的。
- 位数为 \(len_x\) 但是最高位小于 \(x\) 的最高位的。
- 位数为 \(len_x\) 而且最高位等于 \(x\) 的最高位的。从 \(len_x - 1\) 到 \(1\) 枚举每一位，先枚举可能的 \(j\) 转移累加，如果该位与上一位之差小于 \(2\) 就说明后面的数就已经处理过了，不必继续判断。
这样这题就做完啦。
Part 5.2 状压 DP
顾名思义就是把方程的状态压缩至可以储存。例题 [P2704 [NOI2001] 炮兵阵地]([P2704 NOI2001] 炮兵阵地 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)).
看完题就应该会设计啦。我们将每一行每一个格子放不放炮兵的状态压成二进制数，这样就不会 MLE.
设 \(f_{i, s, ps}\) 表示考虑到第 \(i\) 行，该行状态为 \(s\), 上一行状态为 \(ps\) 的最大炮兵放置数目，则有 (上一行状态为 \(pps\), 状态 \(s\) 的炮兵数目记为 \(sum_s\)) :
\[f_{i, s, ps} = \max \begin{cases} f_{i, s, ps} \\ f_{i - 1, ps, pps} + sum_s \quad (\text{需要满足条件}) \\ \end{cases} \]那么问题来了，这个条件是什么？
首先要保证答案合法才能转移，因此涉及到的所有状态都不能有相邻的炮兵。
那么就分两种情况考虑：
- 状态本身：右移一位，位与原状态；右移两位，位与原状态。有任意一个不为 \(0\) 的就不合法。注意不能在山丘上放炮兵...
- 状态之间：本行状态与上一行状态位与，本行状态与上上行状态位与，上行状态与上上行状态位与。有任意一个不为 \(0\) 的就不合法。
那么这样就做完啦。不过结合前面学的滚动数组，你就不能优化一下吗？
发现我的方程中求一行只会用到前一行的答案，因此可以使用滚动数组优化空间。
下面推荐几道用到状压思想的题目：
P3869 宝藏 虽然不是 DP, 但是也可以用来练习状压。
P1879 Corn Fields G 类似于炮兵阵地，思路清晰。
P1896 互不侵犯 长得挺像八皇后的哈哈。
P4011 孤岛营救问题 也不是 DP, 但是是状压分层图经典好题。
Part 6. 轮廓线 / 插头 DP
是的，你没有听错！现在就在 10 min 之内教会你插头 DP.
轮廓线 DP, 顾名思义就是在棋盘问题中，将当前决策格子作为已决策与未决策格子划分构造一条线，如图：
那么就以轮廓线为状态，去进行转移。这也用到了状压的思想。
插头 DP, 顾名思义 就是将一个格子拆成四个插头：
然后记录轮廓线上的插头状态，进行 DP.
为啥要定义插头？很简单，它规定了格子是否能够相连，而大部分棋盘问题格子都是可以相连的。这样我们可以根据轮廓线上的插头转移自所有合法状态。
下面来看 CDQ 大佬《基于连通性状态压缩的动态规划问题》中的例题：P5056 插头 DP
考虑将插头的相连性记录至状态，那就有了两种表示法：
1. 最小表示法
很简单，就是从左到右把联通的插头标为同一个编号。
2. 括号表示法
考虑到插头两两匹配的特性，可以联想到括号匹配。
定义轮廓线上的联通分量最左端的插头记为左括号，最右端的插头记为右括号，没有插头记为 \(0\):
可以看到明显是个括号匹配。我们可以用三进制记录，不过为了方便使用四进制。
那么选好了表示法以后就可以快乐的分类讨论了。
1. 没有左、上插头
直接新建一个联通分量。往下面和右边造插头。
2. 两个插头都有
那就合并呗，否则造不出回路。
注意当这两个插头联通时，只有当这个格子为最后一个可以铺线的格子时才合法。
（因为只能产生一个环，既然你这一步都完成了整个环，那么后面的格子就无法成为环的一员了）
3. 只有一个插头
那就把线接下来，然后分成建右、下插头两种情况。
至此，分类讨论结束。题目就做完啦。
下面推荐几道插头 DP 练手题：
P5347 俄罗斯方块 千万不要做，太难了。
P6758 Vim 略微有点需要转化。
P4262 白金元首与莫斯科 骨牌覆盖问题。
P3272 地板 当年可是紫题啊... 思路简单，抓住 L 形特点即可。（不过还是凭着恶臭的分类讨论晋升到了黑题）
Part 7. 经典优化
没错我们终于来到了优化部分。
Part 7.1 单调队列优化
针对线性 DP 的方程，考虑维护其贡献单调性，进行单调队列优化。做法就是把有价值的保留，没意义的删掉。
例题：P1725 琪露诺
考虑枚举 \(i\) , 枚举要跳的位置 \(j\), 复杂度为 \(\mathcal{O}(N (R - L + 1))\), 无法通过。
先列出方程吧：
\[f_i = \max_{i - L \le j \le i - R} \{f_{j} + A_i\} \]然后就发现单调队列的用处了：可以让窗口大小为 \(R - L + 1\), 然后维护 \(f_i\), 每次都从最优者转移，再入队。
这样复杂度就下降了，成为了 \(\mathcal{O}(N)\) 的线扫。
Part 7.2 斜率优化
就是针对方程：
\[f_i = a_i \cdot b_j + c_i + d_j \]的玄学优化。
例题：P3195 玩具装箱
先预处理前缀和 \(sum\), 然后写出柿子 (令 \(A_i = sum_i + i, B_i = A_i + L + 1\)) :
\[\begin{aligned} f_i &= \min \{f_j + (sum_i - sum_j - L + i - j - 1)^2\} \\ &= \min \{f_j + (A_i - B_j)^2\} \\ &= \min \{f_j + A_i^2 - 2A_i B_j + B_j^2\} \\ \end{aligned} \]假定 \(f_i = f_j + A_i^2 - 2A_i B_j + B_j^2\), 令 \(X = B_j, Y = f_j + B_j^2\):
\[Y = f_i + 2A_i X - A_i^2 \]这个就成了斜率为 \(2A_i\) 的直线。那么任务就是缩小截距。
发现题目中的好多玩意都具有单调性，考虑单调队列优化：
维护一个下凸壳，使得相邻两点之间的连线斜率单调上升。弹出对当前无意义的点（就是斜率小于 \(2A_i\) 的）获得当前最优，计算出 \(f_i\), 弹出在凸壳内部的点（截距肯定大），插入这个点。
那就做完啦。复杂度为 \(\mathcal{O}(N)\).
Part 7.3 CDQ 分治
啊啊啊又是 CDQ 大佬。
简单来讲就是先求解左边的子问题 （后序遍历！！！）, 再处理左边的答案对于右边的答案的影响，再解决右边的子问题。
例题：P4027 货币兑换
先贴柿子：
\[x_i = f_i \frac{Rate_i}{A_i Rate_i + B_i}, y_i = f_i \frac{1}{A_i Rate_i + B_i}, f_i = \max \begin{cases} f_{i - 1} \\ \max \{ x_j A_i + y_j B_i\} \end{cases} \]斜率乱搞：
\[\frac{y_j - y_k}{x_j - x_k} > - \frac{A_i}{B_i} \]什么竟然没有单调性... 那么就要请出我们的 CDQ 分治了。
首先按照 \(- \frac{A_i}{B_i}\) 排序，左半边按照时间排序，确保用时间早的更新时间晚的。
再单调队列建立上凸壳转移，最后再按照 \(x\) 排个序即可。复杂度 \(\mathcal{O}(N \log_2^2 N)\), 勉强能过，尝试优化。
发现 CDQ 分治的壳子其实是个归并排序的壳子，那么再往里面添加归并排序即可。复杂度 \(\mathcal{O}(N \log_2 N)\), 可以通过。
Part 7.4 WQS 二分
应用范围：恰好选 \(m\) 个的最优方案。
应用前提：设 \(g_i\) 为强制选 \(i\) 个物品的最优方案，那么把所有的 \((i, g_i)\) 画出后一定形成一个凸壳。
那么 WQS 二分就是一个能去掉这一限制的东东。
不妨求一下 \(g_m\). 先二分斜率，毕竟斜率对应的凸壳切点是惟一的（共线的除外），快速算出切点。
然后因为答案同样具有单调性，所以可以二分求解。考虑如何快速计算切点。
发现我们要的切点使得切线的截距最大，而 \(b = g_x - kx\), 于是截距的意义就变成了所有物品的价值减去 \(k\), 这样就不再有限制了。
下面来看例题：P6246 邮局 加强版。默认大家都会邮局了，下面讲解如何优化成 \(\log\) 级。
发现邮局建的越多越好，所以直接建 \(M\) 个，随便联想一下转换成恰好建 \(M\) 个。
然后直接可以上 WQS 二分啦！？突然发现方程不太符合 WQS 的思想？
易证方程的决策单调性，所以我们考虑将找决策点 \(pos\) 变为找决策点可以转移到的目标。那么就直接记录可以转移到的范围即可，使用单调队列维护（考虑某个点是否会选择转移自它）。
那么就真的可以上 WQS 二分辣！复杂度 \(\mathcal{O}(N \log_2 N \log \omega)\), 可以通过。
Part 7.5 四边形不等式优化
对于区间 DP 的优化。
四边形不等式：
\[w_{a, b} + w_{c, d} \le w_{a, d} + w_{b, c} \quad (a \le b \le c \le d) \]即交叉小于包含。那如何证明方程符合四边形不等式呢？
四边形不等式判定定理：
若对于任意 \(a < b\) 均有 \(w_{a, b} + w_{a + 1, b + 1} \le w_{a, b + 1} + w_{a + 1, b}\), 则 \(w_{a, b}\) 满足四边形不等式。
证明：
对于任意 \(a + 1 < c\) 都有 \(w_{a, c} + w_{a + 1, c + 1} \le w_{a, c + 1} + w_{a + 1, c}, w_{a + 1, c} + w_{a + 2, c + 1} \le w_{a + 1, c + 1} + w_{a + 2, c}\).
可以推出来：
\[w_{a, c} + w_{a + 2, c + 1} \le w_{a, c + 1} + w_{a + 2, c} \]于是可以推广至任意数。发现 \(b\) 亦是如此，证毕。
决策单调性：
满足四边形不等式一定满足决策单调性。证明：
设 \(pos_i\) 为 \(f_i\) 的决策点。要证明 \(pos_{i - 1} \le pos_i\), 先假设 \(pos_{i - 1} > pos_i\).
易得 \(f_{pos_i} + w_{pos_i, i} \le f_{pos_{i - 1}} + w_{pos_{i - 1}, i}, w_{pos_i, i - 1} + w_{pos_{i - 1}, i} \le w_{pos_i, i} + w_{pos_{i - 1}, i - 1}\), 综合可得：
\[f_{pos_i} + w_{pos_i, i - 1} \le f_{pos_{i - 1}} + w_{pos_i, i - 1} \]这样就发现问题了，怎么 \(pos_i\) 变成 \(f_{i - 1}\) 的决策点了？因此假设不成立，原命题得证。
下面直接看例题：P4767 邮局
方程：
\[f_{i, j} = \min \{f_{k, j - 1} + w_{k + 1, i}\} \]于是开始证明，先证明简单的 \(j = 1\) :
\[\begin{aligned} f_{i, 2} + f_{i + 1, 1} &\ge f_{i, 1} + f_{i + 1, 2} \\ f_{i, 2} + w_{1, i + 1} &\ge f_{i + 1, 2} + w_{1, i} \\ \end{aligned} \] 标签：指北,插头,入门,pos,Part,到入,cases,例题,DP From： https://www.cnblogs.com/JackMerryYoung/p/16667411.html