DP类型
DP的一般形式是表示出能代表出与后续或答案有关的当前的状态，并在这些状态中进行转移
DP的难点在于状态的设计和转移的优化。
由于DP属于一种思想，不同的情况下状态设计和转移都不一样，下面对于每种DP都会给出问题来讲解。
序列DP
将问题放在序列上，在序列上设计状态和转移，是一种非常常见的DP。
题目：洛谷P2519 [HAOI2011]problem a
模型建立
求最少有多少人没说真话，可以先求最多有多少人说真话。
我们考虑将所有人的成绩排序后的一个序列A。
第i个人说的是真话，当且仅当$A_{a_i+1}=…=A_{n-b_i}$，将这个区间看成一条线段，这样的话n个人就是n条线段。
不难发现，如果两条线段相交但不重合，说明两个人中至少一人说了谎，而且对某一线段重合的线段个数不能超过线段的长度（包含的点数）。
这样的话，我们的问题就转化成，对于n个线段，选出最多的线段个数，使得这些线段要么不相交，要么完全重合且对于同一个线段重合的线段个数不超过该线段的长度。
状态设计及转移优化
重合的线段我们都放到一起，记一个总数并与长度取较小值，这样的话任意两条线段都是不重合的，那么就只用考虑不相交了
如何我们以右端点为第一关键字，以左端点为第二关键字进行排序，显然我们遍历所有线段，那么如何设计状态呢？
设dp[i]为前i个线段中能选的线段的最多个数，那么转移方程显然为$dp[i]=dp[last]+cnt$，其中last为右端点小于i左端点的最后一个线段，cnt为前面提到的总数。
对每个i枚举j，复杂度为$O(n^2)$，所以我们要对这部分进行优化。
考虑到我们的线段是以r为右端点为第一关键字排序的，也就是说线段的右端点是有序的，那么我们就可以二分找到右端点比i的左端点小的最靠后的线段，将dp记录成前缀最大值，就可以$O(\log n)$查找线段，$O(1)$转移了。
Solution(Accepted)
1 | struct Segment { |
区间DP
区间DP的状态一般表示为$dp[i][j][…]$，即区间$[i,j]$这一段的答案。
例题
CF1132F. Clear the String
题目大意是给你一个长度为$n\le 500$的字符串，每次可以删去一段由相同字符构成的连续子串，问删完所有字符最少需要多少次操作。
Solution
这是一道非常模板的区间DP，我们设$dp[l][r]$为删去区间$[l,r]$的所有字符需要的最少操作次数。
至于转移，区间DP常用的方法是枚举区间大小进行转移，这里也是如此。
我们从小到大枚举区间的大小，然后枚举该大小的区间：
- 若区间两端相等，说明可以通过删去中间后两端连在一起删
- 若区间两端不相等，我们将区间分成两段，分别去删，取最小的次数。
于是我们的转移方程就出来了：
- $s[l]=s[r],dp[l][r]=min\{dp[l+1][r],dp[l][r-1]\}$
- $s[l]\not=s[r],dp[l][r]=min\{dp[l][r],dp[l][k]+dp[k+1][r]|l\le k< r\}$
1 | for (int len = 2; len <= n; ++len) { |
数位DP
数位DP常用于统计或查找一个区间满足条件的数，然后按数位顺序DP，一般需要仔细分情况讨论。
常见处理方式有：拆成[1,R]和[1,L)，记忆化，预处理等。
洛谷P2657 [SCOI2009] windy 数
状态建立及转移
一道相当常规的数位DP，我们可以将[L,R]的答案拆成[1,R]-[1,L-1]的答案，这样的话我们只要能计算1到x的windy数就可以了。
我们设dp[i][j]表示i位数最高位为j时的windy数，显然的转移是$dp[i][j]=sum(dp[i-1][k])$，其中k满足$abs(k-j)\ge 2$
接下来我们就用dp来求解[1,x]的所有windy数1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46int dp[N][N], num[N];
void presolve() {
for (int i = 0; i <= 9; ++i)dp[1][i] = 1;
//这里要包括0的原因是我们dp的过程中，类似于20 30这些数依然是windy数，所以0虽然不是windy数，但却能产生贡献
for (int i = 2; i <= 10; ++i) {
for (int j = 0; j <= 9; ++j) {
for (int k = 0; k <= 9; ++k) {
if (abs(j - k) <= 1)continue;
dp[i][j] += dp[i - 1][k];
//为什么这里j k要从0开始呢？这是考虑到我们会求在高位都一定时，从某位开始的所有windy数
//此时这些位就可能是0了
}
}
}
}
int solve(int x) {
if (!x)return 0;
int ans = 0;
for (*num = 0; x; x /= 10)
num[++*num] = x % 10;
for (int i = *num - 1; i >= 1; --i)
for (int j = 1; j <= 9; ++j)//这里j不从0开始的原因很简单，j为0的话实际上数字就不是i位了，会重复计算
ans += dp[i][j];
//唯独*num位数最麻烦
for (int i = 1; i < num[*num]; ++i)
ans += dp[*num][i];
//接下来专注于最高位为num[*num]时的*num位数
for (int i = *num - 1; i >= 1; --i) {
//从次高位开始一直到最低位，每一步计算当前位比num[i]小的数的所有贡献（因为后面的所有数都能取到，
//只用考虑当前位与高一位是否冲突），之后只剩这一位为num[i]的情况，我们就再去求下一位的所有贡献
for (int j = 0; j < num[i]; ++j) {
if (abs(j - num[i + 1]) >= 2)
ans += dp[i][j];
}
if (abs(num[i + 1] - num[i]) < 2)return ans;
//这时已经不可能再有多的贡献，因为在接下来的计算中我们的前提就是前面的所有位都是确定的，所以此处必然使剩下的所有数不成立
}
return ans + 1;//上面的计算并没有包括自身，此处要加上自身
}
int main(void) {
presolve();
int l = fast_IO::read(), r = fast_IO::read();
fast_IO::write(solve(r) - solve(l - 1));
return 0;
}
概率DP
概率DP是求事件概率或期望的DP的总称。
对于求概率问题，有时利用补集转化，或者将其转化为计数问题；
对于求期望问题，大多时候利用期望的线性性来解决问题。
贝叶斯公式
条件概率$P(y|x)$
联合概率$P(y,x)$
$P(x,y)=P(y|x)P(x)=P(x)P(y)$
$P(x,y)=P(x|y)P(y)$
贝叶斯公式：$P(y|x)=\dfrac{P(x|y)P(y)}{P(x)}$
例题：期望的线性性
洛谷P3239 [HNOI2015]亚瑟王
题目概述：给你$N$张牌，每张牌有一个发动概率$P_i$以及伤害$D_i$。共有$R$回合，每回合会按编号从小到大依次考虑本次游戏中还未发动的卡牌，依次尝试发动；如果发动成功，进入下一回合。求期望伤害之和。共$T$组数据。
$T\le 444,N\le 220,R\le 132$
这个题如果直接去算每一局的期望，非常难设状态（需要状压），而根据期望的线性性，我们考虑每张牌被发动的概率，那么总伤害就为每张牌造成的期望伤害之和。
我们设dp[i][j]表示前i张牌中一共出了j张的概率，sump[x]表示x这张牌在整局游戏中被打出来的概率。
对于转移，首先我们来看sump的转移，我们枚举前i-1张牌中出牌数j，由题意可知i之前打出的j张牌都不会考虑到第i张牌（因为打出去以后本轮就结束了），同时也说明有r-j轮可能会考虑到第i张牌，于是我们的转移方程就出来了，$sump[i]=\sum\limits_{j=0}^rdp[i-1][j]\cdot(1-(1-p[i])^{r-j})$，此处要注意，我们将“中间某处选第i张牌”采用了补集转换的思想，因为求出“中间没有任何一处选第i张牌”显然是更方便的。
再来看看dp[i][j]的转移，这里显然要分两种情况讨论：是否选择了当前的第i张牌：
- 没有选择，那么$dp[i][j]=dp[i-1][j]\cdot (1-p[i])^{r-j}$，与上面类似，这里是后面r-j轮都不选i
- 若选择了，那么$dp[i][j]=dp[i-1][j-1]\cdot(1-(1-p[i])^{r-j+1})$，也是类似，前j-1张不可能选到i
最后答案即为$\sum\limits_{i=1}^nsump[i]\times d[i]$
1 | double p[N], dp[N][N], sump[N], sum[N][N]; |
树形DP
树形DP是指基于树形结构的动态规划，一般有：
- 树的直径：DP记录子树内的最长路
- 树的重心：DP记录子树大小
- 树上点权独立集：DP记录子树的根是否选择
- 树形依赖背包：在dfs序上DP，或通过将父节点的DP值传入孩子DP
- 虚树：后面会重点讲
- …
虚树
在原树上保留需要的点和它们的LCA的树成为虚树，换句话说，我们尽可能合并了中间的点。
虚树适用于对同一棵树多次查询且查询的总点数在某一范围内的情况。
我们对每次查询建一棵虚树，该树的点树不会超过查询点个数的2倍，这样就保证了复杂度。
对于建树的过程，都是同样的方法，根据要求来合并被忽略的树链上的信息。
建树
虚树的最大难点在于建树。
首先我们预处理出整颗树的dfs序dfn，因为dfs序是沿着树链递增的。
使用一个栈，栈底到栈顶的元素形成虚树的一个树链（从上到下）。
对于一次查询，将所有的关键点按照dfn进行排序，然后从dfn小的点开始以此操作每个关键点，根据栈中树链的信息进行建树。
具体过程如下：
- 如果栈为空或者只有一个元素，此时将点入栈
- 否则取lca=LCA(st[top],x)，若lca=st[top]，说明x是st[top]的后代，因此将x入栈，表示延长当前树链。
- 否则说明x与当前的st[top]分属于两个不同的链，而根据dfs序的性质，此时st[top]已经是一条链的终点。
所以此时我们需要将lca的包含st[top]的部分退栈，退出来的部分构成一条树链。如果此时lca不在栈中，则lca也要入栈以保证虚树的结构，最后将x入栈。 - 最后将栈中剩余的元素相邻连边（剩下的全都是链的顶点和最后一条链，也可以看成是一条长链）
1 | void _insert(int x) { |
状压DP
基于状态压缩的DP是由于状态用单个简单的变量直接存储导致空间浪费，而采用压缩的状态的动态规划，例如：
- 插头DP：维护当前已决策和未决策的一条Z字形轮廓线的插头状态，用括号序列配对插头，每次只需分情况考虑即可，不过这类DP状态较多，需要细心调。
例题、Tourism
给定一个n个点m条边的无向图，每个点有点权，保证任意两点之间简单路径长度不超过10。
现在要求选出一些点，使得每个点要么自己被选，要么其相邻的点被选。
一个方案的代价定义为选取点的点权和，求最小代价。
$n\le 20000,m\le 25000,0\le A_i\le10000$
思路
考虑任意两点简单路径长度不超过10这个条件。
我们不妨把生成树做出来，这样的话树的深度不超过10，于是我们就可以讲某点到根的路径上所有点的选取情况进行状态压缩。由于生成树并不能包含无向图中所有的边，因此点之间可能通过非树边连在一起。为了考虑这种情况，这里对每个点而言就有三种状态：被选取、未被选取但已被覆盖、未被选取且未被覆盖。因此我们使用三进制数来维护一个点到根路径上点的状态，这样一共有$O(3^{10})$种状态。
于是我们就在这棵生成树上DP，首先设状态dp[i][j]表示对于i节点，当其到根节点的状态为j时，生成树中除了节点i到根上的点以外所有dfs序比i小的节点全被覆盖时的最小代价。
至于转移，我们分别考虑选当前点和不选当前点的情况：
- 若不选当前点，如果前面走过的点中有一个点被选且存在一条边连接这两个点，当前点的状态就是被覆盖。
- 若选当前点，如果前面走过的点有点没被覆盖且存在一条边连接这两个点，则那个点的状态就要改为被覆盖
可以看出，两类转移都需要我们先找出所有指向已走过点的返祖边。
最后再将当前点被覆盖的两个状态的dp值取小上传。
另外，这里由于空间复杂度高，需要使用滚动数组，或者可以直接将第一维表示为深度。
1 | int getst(int st, int x) { return st / mi[x] % 3; } |
DP套DP
背包专题
背包是线性DP中的重要模型
0/1背包
所谓0/1背包，就是一堆物品分别有价值w[i]和占用空间v[i]，每种物品都是一个，现在要用空间大小为m的背包装物品，求出所装物品的价值和最大值是多少。
而最基础的想法，就是直接设状态$dp[i][j]$表示前i个物品中用大小为j的背包能得到的最大价值，转移也很明显$dp[i][j]=max\{dp[i-1][j-v[i]]+w[i]|v[i]\le j\le m\}$。
我们发现每次转移只和上一行有关，于是可以用滚动数组优化空间。
更仔细地观察发现，我们都是用前面的值去更新后面的值，于是我们改变j的枚举顺序，从大到小枚举，就可以只用一维数组来达到目的。
这样的话空间复杂度$O(m)$，时间复杂度$O(nm)$
1 | for (i = 1; i <= n; ++i) |
完全背包
完全背包就是在0/1背包的基础上对物品的个数没有限制，求相同的问题。
其实只要我们把上面优化过的0/1背包改变枚举顺序，就是完全背包了，因为我们允许对同一个物品重复选择。1
2
3for (i = 1; i <= n; ++i)
for (j = v[i]; j <= m; ++j)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
多重背包
上面两种背包都是非常特殊的情况，更一般的，我们考虑每个物品i分别有$C[i]$个，那么问题就变成了多重背包。
一种非常暴力的做法就是将$C[i]$个物品全部拆开，将问题变成0/1背包，这样的话时间复杂度是$O(\sum\limits_{i=1}^nC[i]m)$。
这个复杂度是比较高的，那么有没有什么更好的办法呢？
二进制拆分
我们还是考虑将$C[i]$拆分，但我们采用更优秀的拆分方法，使得拆出来的物品尽量少，而且这些物品的组合可以表示$1\sim C[i]$中的任何一个数。我们考虑将其拆分成$C[i]=2^0+2^1+2^2+…+2^k+rest,rest<2^{k+1}$，这样的话对于$x<2^{k+1}$都可以很容易凑出，而对于$2^{k+1}< x\le C[i]$，我们发现$x-rest< 2^{k+1}$，也就是说$x-rest$是可以通过前面的部分组合出来的，因此我们可以组合出任意一个x。
1 | //C进行拆分 |
这样同样将问题转化成了0/1背包，但是时间复杂度更优秀，为$O(nm\log\max(C_i))$。
单调队列优化
我们仔细观察转移的过程，寻找规律，来看看转移方程
$dp[i][j]=\max\{dp[i-1][j],dp[i-1][j-k\cdot v[i]]+k\cdot w[i]|k\in [1,\min(\dfrac{m}{C[i]},C[i])]\}$
我们发现，j mod v[i]相同时的j之间才会产生转移，于是我们可以按这个进行分组。
而考虑到能转移到j的是区间$[j-C[i]*v[i],j]$的最大值，因此我们用复杂度优秀的单调队列来完成维护最大值的工作。
那么总复杂度是多少呢？我们枚举了n类物品，对每类物品i分成C=v[i]类，枚举k的范围是$\dfrac{m}{v[i]}$，因此总复杂度为$O(nm)$
1 | for (int i = 1; i <= n; ++i) { |
分组背包
给定N组物品，规定每组物品中最多选一个，求大小为m的背包能装的最大价值。
事实上我们只需要先枚举组，再枚举背包的容量，再枚举组内物品就行了。
倒序枚举背包容量，空间复杂度降到一维。1
2
3
4for (int i = 1; i <= n; ++i)
for (int j = m; j >= 0; --j)
for (int k = 1; k <= C[i]; ++k)
dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
树上背包
咕咕咕