关于 DP
1.暴力DP
\(A\).线性 DP
没什么具体的定义，是同时针对一个或几个区间上的 dp。一般就是推出状态转移方程后直接码上。
一个要注意的点就是：分类讨论是这类题主要的难点，分讨可以体现在状态设计上，但更多的是在转移。
\((1)\) 转移中分讨：守望者的逃离、TJOI2007] 线段。
\((2)\) 状态上分讨：找爸爸
\((3)\) 双线程：方格取数
\(B\).背包 DP
这类题目中每个物品都有体积和价值，并且有容量的限制。
\((1)\).\(01\) 背包，完全背包，多重背包
这里可以将 \(01\) 背包、完全背包、多重背包统一为多重背包，其中完全背包中的每个物品的最多可选数量就是 $\lfloor \dfrac { 容积}{体积} \rfloor $。
多重背包的样板题：樱花，以下为主要代码：
for(int i=1;i<=n;i++)
{p[i]=(node){ read(),read(),read() };if(!p[i].c) p[i].c=m/p[i].w;
}
for(int i=1;i<=n;i++)for(int j=m;j>=0;j--)for(int k=0;k<=p[i].c;k++)if(j-k*p[i].w>=0)ckmax(dp[j],dp[j-k*p[i].w]+k*p[i].v);
从以上代码可以看出，多重背包的复杂度较大。一个显然的问题是：对于一个物品，我们重复枚举了等价的选择方案（例如：对于有 \(k\) 个同一物品，选第一个和第二个与选第二个和第三个显然是一样的），那么找到一个可以不重不漏的物品拆分方法就可以大大降低复杂度。常用的方法就是二进制分组，可以见背包 DP - OI Wiki中相应部分。
另一种方法就是单调队列优化。
这里提一下单纯的 \(01\) 背包和完全背包的简化写法：
设 \(dp[j]\) 表示在前 \(i\) 个物品中用 \(j\) 的容量可以获得的最大总价值，这里省去了关于 \(i\) 的一维，因此：
对于 \(01\) 背包：
for(int i=1;i<=n;i++)for(int j=m;j>=w[i];j--)ckmax(dp[j],dp[j-w[i]]+v[i]);
对于完全背包：
for(int i=1;i<=n;i++)for(int j=w[i];j<=m;j++)ckmax(dp[j],dp[j-w[i]]+v[i]);
可以见到，两者的代码上差别主要在第二重循环正序和倒序上，实际上的差异就是在对第 \(i\) 个物品计算 \(dp[j]\) 时，\(dp[j-w[i]]\) 是否被这个物品更新过，\(01\) 背包通过倒序循环来保证 \(dp[j-w[i]]\) 未被物品 \(i\) 更新，从而保证对于每个容量 \(j\)， 每个物品最多只会更新容量 \(j\) 一次，而完全背包则恰恰相反，处理物品 \(i\) 时，\(dp[j-w[i]]\) 被物品 \(i\) 以任意次数更新了。
\((2)\).分组背包
实际上就是树上背包的一个简化的形式，又叫有依赖的背包。
典型题目：金明的预算方案。
\((3)\).背包建模
这大概时背包 DP 的一个重大的应用吧，需要转化为价值和体积。
典型题目：飞扬的小鸟，Cow Exhibition G。
\(C\).区间 DP
从区间转移到区间，最显著的特点就是可以从一个小区间的答案计算出大区间的答案。
一般来讲，计算区间 \([l,r]\) 具体的方式有两种：分为两个并列的区间 \([l,k]\) 和 \([k+1,r]\) ，递归到内部区间 \([l+1,r-1]\) 后统计端点。
\((1)\).分为两个区间：石子合并、USACO16OPEN 248 G、能量项链、Polygon。
\((2)\).递归后统计端点价值：Coloring Brackets。
DP 常见套路1
如果题目可以转化为处理一个 \(01\)序列，那么大概率是枚举一个极长 \(0/1\) 段的起始位置，状态数组常为 \(dp[i][0/1]\)，表示在位置 \(i\) 结束的极长 \(0/1\) 段，方程常为 \(dp[i]=\max_{i=1}^{j-1} (dp[j]+cost(j+1,i))\)。
题目：Game Rooms 、染色。
\(D\).数位 DP
个人认为，这简直是 DP 中最背板的一类(doge)，并且总是采用记忆化搜索的方式书写。
典型问法：求在区间 \([l,r]\) 中满足某些条件的数的个数。
首先要转化成前缀和的形式：设 \(ans_{[l,r]}\) 表示区间 \([l,r]\) 中满足条件的数的个数，有 \(ans_{[l,r]}=ans_{[1,r]}-ans_{[1,l-1]}\)。
接下来就是求解 \(ans_{[1,x]}\)。
求解过程中需要讲数位 DP 的精华之处：前导位压制，用来保证我们找到的数都在区间 \([1,x]\) 中。
这里解释以下”前导位压制“的意思：
考虑一个填数的过程：给定一个数 \(x\)，要求填出一个不超过 \(x\) 的数。
例如 \(x=123456789\)，假设你已经填了前 \(4\) 位成 \(1234-----\)，这时要填第五位，因为不能超过 \(x\)，那么你只能在第五位填 \(0、1、2、3、4、5\)，但如果填的是 \(1231-----\)，那么你就可以在第五位任意填一个 \(0\) 到 \(9\) 的数。我们把与第一种类似的情况称为被前导位压制，与第一种类似的情况称为不被前导位压制。
从这个例子可以看出，填出 \(1231-----\)、\(1232-----\)、\(1134-----\) 等情况后，因为后面都可以随便填，它们接下来的情况都是一样的，这就可以用记忆化搜索来储存，之后查询到就直接调取答案。
以一道简单的题同类分布为例：
\(1\).需要取出 \(x\) 的每一位，存在 \(num\) 中（注意这里是从低位开始存）：
inline void GetNum(int x)
{memset(num,0,sizeof(num));len=0;while(x) num[++len]=x%10,x/=10;
}
\(2\).设状态数组，一定要设置一维处理到第 \(i\) 位，然后你就可以自由添加维度，只要这些维度可以帮助你判断所填的数是否符合条件。在本道题中，状态数组为 \(dp[i][left][mod]\)。要记住一点：dp数组所存的一定是未被前导位压制时的答案。
\(3\).设计记搜状态，一定要设置表示处理到第 \(i\) 位的一维和表示是否被前导位压制的一维，其他的维度同 dp 数组。对于本题，就是 \(dfs(i,left,mod,limit)\)。
\(4\).在 dfs 的过程中，需要找到当前数位可填写的最大值 \(up\)，当 \(limit==false\) 即未被前导位压制时，\(up=9\)，否则 \(up=num[i]\)。
\(5\).dp 数组要初始化为 \(-1\)，因为方案数显然可以为 \(0\)。
\(6\).只要当前位之前有一位数不是贴着上界填，就不算被前导位压制，\(limit==false\)。
其他的就是正常记搜了。
int dfs(int p,int left,int mod,bool limit,int sum,int *t)
{if(p==0) return (left==0) && (mod==0);if(!limit && ~dp[p][left][mod][limit])return dp[p][left][mod][limit];int upper=limit?t[p]:9;int tot=0;for(int x=0;x<=upper;x++){if(x>left) continue;tot+=dfs(p-1,left-x,(mod*10+x)%sum,limit&&x==upper,sum,t);}if(!limit) dp[p][left][mod][limit]=tot;return tot;
}
这题的完整代码，注意函数命名略有不同（这题很早前写的，现在码风已经变了）：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
const int N=19;
const int M=9*N;inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }return f*x;
}int L,R,tmp[N+1],len;
int dp[N+1][M+1][M+1][2];
// dp[p][left][mod][limit]:
// 处理到第 p 位(从高到低)
// 剩余需要累加的数字之和为 left
// 当前数对 sum 取模为 mod
// 是否被前导位压制 0/1int calc(int p,int left,int mod,bool limit,int sum,int *t)
{if(p==0) return (left==0) && (mod==0);if(!limit && ~dp[p][left][mod][limit])return dp[p][left][mod][limit];int upper=limit?t[p]:9;int tot=0;for(int x=0;x<=upper;x++){if(x>left) continue;tot+=calc(p-1,left-x,(mod*10+x)%sum,limit&&x==upper,sum,t);}if(!limit) dp[p][left][mod][limit]=tot;return tot;
}void fx(int x,int *t,int &pos)
{while(x){t[++pos]=x%10;t[0]+=t[pos];x/=10;}
}int solve(int x)
{memset(tmp,0,sizeof(tmp));int len=0;fx(x,tmp,len);int total=0;for(int sum=1;sum<=9*len;sum++){memset(dp,-1,sizeof(dp));total+=calc(len,sum,0,true,sum,tmp);}return total;
}signed main()
{L=read(),R=read();printf("%lld\n",solve(R)-solve(L-1));return 0;
}
相似的题目：windy 数、手机号码、数字计数
(-------------------------施工中-------------------------)