预警：由于是从$Vergil$学长那里和$Mathison$大神那里学来的，所以清一色记忆化搜索！qwq
巨佬的数位dp讲解（未来的咕咕日报头条）：
https://www.luogu.org/blog/virus2017/shuweidp
数位dp嘛，顾名思义...就是与每个数上的那位有关系...（废话）
一般问题形式都是，在区间$[l,r]$中，满足xx条件的数有多少。然后数据范围一般巨大，枚举是不可能的，这辈子是不可能的。所以一般我们都把它当做字符串处理，预处理出每一位的数（数位），即之后的$border$数组。先求出1~r内满足范围的数，在求出1~l-1范围内的数，运用前缀和的思想一减的。
关于处理成字符串：
一种高精处理方法
scanf("%s",p+);
int lenp=strlen(p+);
int last=lenp;
while(p[last]==''&&last) last--;
for(int i=last+;i<=lenp;i++) p[i]='';
p[last]--;
for(int i=;i<=lenp;i++) a[lenp-i+]=p[i]-'';
memset(dp,-,sizeof(dp));
ans1=dfs(lenp,,);
scanf("%s",q+);
int lenq=strlen(q+);
for(int i=;i<=lenq;i++) a[lenq-i+]=q[i]-'';
memset(dp,-,sizeof(dp));
ans2=dfs(lenq,,);
printf("%d\n",ans2-ans1);
另一种暴力搞，longlong范围内才可。
l--;
while(l)
{
border[++len]=l%;
l/=;
}
memset(dp,-,sizeof(dp));
ans1=dfs(len,,);
len=; while(r)
{
border[++len]=r%;
r/=;
}
memset(dp,-,sizeof(dp));
ans2=dfs(len,,);
len=;
printf("%lld\n",ans2-ans1);
记忆化搜索？其实感觉他是dp的本质吧...（说错了不要打我啊qwq）。搜索我们要遍历所有状态，遍历完就溜，啥也不记下来，没心没肺；dp我们也要遍历全部状态，但是长心眼了，懂得存起来，用空间换时间；然后dp是和记忆化搜索学的，所以记忆化搜索也记录了搜过的状态，当现在搜的之前搜过，就直接调用之前的结果。Update：Vergil学长表示他认为dp的本质是最短路 把各状态当作图的节点，然后与开始节点连的边为初始值...
既然我们记搜了，那么肯定我们需要知道每次记录哪些量：一般地，我们会记到$pos$（现在在第几位，个人习惯从右往左为第1位到第$len$位）、$pre$（上一位是哪个数字，用于与上一位有关的情况）、$ling$前导零标记、$limit$最高位标记、$st$是否已经满足要求了，还有其他实际情况需要的。开始从主程序进来的时候，$ling$和$limit$都是1。
图自@Mathison真·大神
另外，当$limit=1$不能记录和调用dp值！当$ling=1$也不能调用记录dp值！
以上是概论，现在分两种题型扯几道例题。
第一种题型：问你数位满足是否有xx数 or 没有xx数
- 例1 hdu2089不要62
题目大意：问你$[l,r]$中不含4且不含连续62的数的个数。
真·入门题。因为不含，所以只要有4或62连续，之后我们就不用搜了。
#include<cstdio>
#include<algorithm>
#include<cstring> using namespace std;
typedef long long ll; int l,r,len;
int border[];
ll ans1,ans2,dp[][]; ll dfs(int pos,int pre,int limit)
{
if(pos<) return ;
if(!limit && dp[pos][pre]!=-) return dp[pos][pre];
ll tmp=;
ll lim=limit ? border[pos] : ;
for(int i=;i<=lim;i++)
{
if(i==) continue;
if(i==&&pre==) continue;
tmp+=dfs(pos-,i,(limit&&i==lim));
}
if(!limit) dp[pos][pre]=tmp;
return tmp;
} int main()
{
while(scanf("%d%d",&l,&r)!=EOF&&l!=&&r!=)
{
l--;
while(l)
{
border[++len]=l%;
l/=;
}
memset(dp,-,sizeof(dp));
ans1=dfs(len,,);
len=; while(r)
{
border[++len]=r%;
r/=;
}
memset(dp,-,sizeof(dp));
ans2=dfs(len,,);
len=;
printf("%lld\n",ans2-ans1);
}
return ;
}
- 例2 hdu3555Bomb
题目大意：问你1~n中含连续49的数的个数。
数位dp入门题。因为题目问的是“含”，所以我们必须记一个$st$，看之前是否满足。这里就不能像上一道题一样不满足直接$continue$掉了。因为之后还有希望满足啊qwq。
//求1~n 含有连续49的数字有多少
#include<cstdio>
#include<algorithm>
#include<cstring> using namespace std;
typedef long long ll; int T,len;
int border[];
ll dp[][][];
char sta[]; ll dfs(int pos,int pre,int st,int limit)
{
if(pos<) return st;
if(!limit && dp[pos][pre][st]!=-) return dp[pos][pre][st];
ll tmp=;
ll lim=limit ? border[pos] : ;
for(int i=;i<=lim;i++)
tmp+=dfs(pos-,i,st||(i==&&pre==),limit&&i==lim);
if(!limit) dp[pos][pre][st]=tmp;
return tmp;
} int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%s",sta+);
len=strlen(sta+);
for(int i=;i<=len;i++)
border[i]=sta[len-i+]-'';
memset(dp,-,sizeof(dp));
printf("%lld\n",dfs(len,,,));
}
return ;
}
- 例3 poj3208 Apocalypse Someday
第2种题型：问你数位是否满足一些比较复杂的要求（就不是上面那么简单了）
- 例1 [SCOI2009]Windy数
- 例2[ZJOI2010]数字计数
- 例3 LuoguP3413萌数
- 例4 hihocoder#1791幸运数字
- 例5 bzoj1799[AHOI2009]同类分布
- 例6 某qbxt测试题
例题会尽量都补上的qwq
关于输出方案：本来想试着输出下方案的，后来发现实际输出的时候其实会少很多。因为我们记忆化！当一个状态下的值已经确定了，我们就不再切身实际地搜，而是直接调用之前结果了，也就方案会少输出了。当然，没记忆化的时候，显然我们可以输出全部方案。
数位dp。。。按Mathison大佬的话，还是非常套路模板化的，唯一要注意的是举一反三和前导零的处理...。