写在前面
目录
题目完成进度
20/22(数据更新ing～)
一、线性DP
线性DP大概就是个入门的感jio(虽然也有难题)，所以在这里就不过多赘述，只是大致讲一下。
线性DP有三类经典例题，最长上升子序列(LIS)，最长公共子序列(LCS)，数塔问题。这里主要是要理解DP的“阶段”“状态”“决策”三要素，然后记住应用DP的三个条件：“子问题重叠性”“最优子结构”“无后效性”。
同时这一节还讲到了DP的初步优化：离散化、贪心、变量维护决策集合(啥玩意？？？)、前缀和预处理等，根据题目的具体情况灵活使用。
接下来搬运几道例题：
二、背包
1.0/1背包
0/1背包的问题模型如下：
给n个物品，其中第i个物品的体积为$V_i$，价值为$W_i$。有一容积为m的背包，求放入背包的物品的最大总价值。
0/1背包是最基础的啦，这里就不多讲，主要注意一下循环的顺序就好。
直接上例题——
2.完全背包
完全背包的问题模型如下：
给n种物品，其中第i种物品的体积为$V_i$，价值为$W_i$，并且有无数个。有一容积为m的背包，求放入背包的物品的最大总价值。
参考0/1背包的做法，不过要把0/1背包的倒序循环改为正序循环，这就对应着每种物品可以使用无数次。
int f[M];memset(f,0xcf,sizeof(f));f[0]=0;for(int i=1;i<=n;i++) for(int j=v[i];j<=m;j++) f[j]=max(f[j],f[j-v[i]]+w[i]);int ans=0;for(int i=0;i<=m;i++) ans=max(ans,f[i]);
上两道例题——
3.多重背包
多重背包的问题模型如下：
给n种物品，其中第i种物品的体积为$V_i$，价值为$W_i$，并且有$C_i$个，放进体积为m的背包里，求最大价值。
这里介绍解决多重背包问题的三种方法：直接拆分法，二进制拆分法，单调队列法。
•直接拆分法
这是解决多重背包问题最直接也最简单的方法，很显然可以想到的做法，即把第i种物品看做独立的$C_i$个物品,然后按照0/1背包的做法解决问题。
int f[M];//f[i]表示占用背包体积为i时的最大价值memset(f,0xcf,sizeof(f));//赋初始值为无穷小f[0]=0;for(int i=1;i<=n;i++) for(int j=1;j<=c[i];j++) for(int k=m;k>=v[i];k--) f[k]=max(f[k],f[k-v[i]]+w[i]);int ans=0;for(int i=0;i<=m;i++) ans=max(ans,f[i]);
•二进制拆分法
求最大整数p满足$2^0+2^1+…+2^p\le C_i$，然后设$R_i=C_i-2^0-2^1…-2^p$，so…
1.根据p的最大性，故有$2^0+2^1+…+2^{p+1}>C_i$，则可以推出$2^{p+1}>R_i$，因此从$2^0,2^1,…,2^p$中选出若干个相加可以表示出$0～R_i$之间的任何整数。
2.从$2^0,2^1,…,2^p$以及$R_i$中选出若干个相加，可以表示出$R_i～R_i+2^{p+1}-1$之间的任何整数，而根据$R_i$的定义可得：$$R_i+2^{p+1}-1=C_i-\frac{1*(1-2^{p+1})}{1-2}+2^{p+1}-1=C_i$$因此上面的结论就可以修改为：从$2^0,2^1,…,2^p$以及$R_i$中选出若干个相加，可以表示出$R_i～C_i$之间的任何整数。
综上所述，我们可以把数量为$C_i$的物品拆成p+2个物品，他们的体积分别为：$2^0*V_i,2^1*V_i,…,2^p*V_i,R_i*V_i$，这p+2个物品可以凑成$0～C_i*V_i$之间所有能被$V_i$整除的数，并且不能凑成大于$C_i*V_i$的数。这等价于原问题中体积为$V_i$的物品可以使用$0～C_i$次。
•单调队列法
咕咕咕
来道例题吧QAQ
4.分组背包
分组背包的问题模型如下：
给n组物品，其中第i组有$C_i$件物品，第i组的第j个物品的体积为$V_{i,j}$，价值为$W_{i,j}$。有一容积为m的背包，每组至多选择一个物品放入背包，求最大总价值。
背包类问题的解法都是大同小异，所以这里就直接上代码了(我才不是懒得讲了)
int f[M];memset(f,0xcf,sizeof(f));for(int i=1;i<=n;i++) for(int j=m;j>=0;j--) for(int k=1;k<=c[i];k++) if(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);int ans=0;for(int i=0;i<=m;i++) ans=max(ans,f[i]);
三、区间DP
区间DP属于线性DP的一种，它以“区间长度”作为DP的“阶段”，使用区间的左右端点描述两个维度。在区间DP中，一个状态由若干个比它更小且包含与它的区间所代表的状态转移而来，因此区间DP的决策往往就是划分区间的方法。
直接上例题讲解吧QWQ
四、树形DP
给定一棵有n个结点的树，我们任选一个结点为根结点，从而定义出每个结点的深度和每棵子树的根。在树上设计DP算法时，一般以结点从深到浅(子树从小到大)的顺序作为DP的“阶段”。DP算法的状态表示中，第一维通常是结点编号(代表以该节点为根的子树)。大多数时候，我们采用递归的方式实现树形DP，对于每个结点x，先递归在它的每个子结点上进行DP，在回溯时，从子结点向结点x进行状态转移。
先上一道例题——
除了自上而下的递归，我们也可以用自下而上的拓扑排序来执行树形DP。
在有些题目中，树是以一张n个点、n-1条边的无向图形式给出的，在这种情况下，我们就要用邻接表存下这n-1条边，任选一个点出发执行DFS，并注意标记结点是否已经被访问过，以避免在遍历中沿着反向边返回父节点。
•背包类树形DP
这类题目被称为背包类树形DP，又称有树形依赖的背包问题。它实际上是背包与树形DP的结合。除了以“结点编号”为树形DP的阶段，通常我们也会把当前背包的体积作为第二维状态，状态转移时，我们要处理的实际上是一个分组背包问题。
•二次扫描与换根法
五、环形与后效性处理
•环形结构上的DP问题
在许多环形结构问题中，我们都能够通过枚举法，选择一个位置把环断开，变成线性结构进行计算，最后根据每次枚举的结果求出答案。这样的环形问题称为“可拆解的环形问题”，我们可以采取适当的策略避免枚举，使时间复杂度降到最低。
这里主要介绍两种策略：
1.执行两次DP，第一次在任意位置把环断开成链，按照线性问题求解；第二次通过适当的条件和赋值，保证计算出的状态等价于把断开的位置强制相连。
2.断环为链
上两道例题，分别是使用了这两种策略求解——
•有后效性的DP转移方程
有时候我们会遇到形似DP的题目，但是不满足“无后效性”的条件。这时候我们可以把DP的各个状态看做未知量，状态的转移看做方程，然后用高斯消元求出状态转移方程的解。
在更多的题目中，DP的状态转移“分阶段带环”——我们需要把DP和高斯消元相结合，在整体层面采用DP框架，而在局部使用高斯消元解出互相影响的状态。
小二上例题——
Broken Robot
六、状态压缩DP
七、倍增优化DP
八、数据结构优化DP
九、单调队列优化DP
十、斜率优化
十一、四边形不等式
十二、计数类DP
十三、数位统计DP
数位统计DP是与数字相关的一类计数问题。在这类题目中，一般给定一些限制条件，求满足限制条件的第k小的数是多少，或者求在区间[L,R]内有多少个满足限制条件的数。解决方法大致为先用DP进行预处理，然后基于拼凑的思想，用“试填法”求出最终的答案，一些细节部分要根据题目要求来调整。
上例题～QWQ
月之谜