数位 dp 的题往往具有以下特征：

  • 要求统计满足一定条件的数的数量
  • 判定条件和数位上的值有关
  • 询问是一个区间 $l\sim r$，有时也只有上界
  • 区间很大，往往超过 $10^9$，暴力会超时

在遇到数位 dp 的时候，第一步就是使用差分的方法，把一个区间的答案拆成两个区间相减，$ans_{[l,r]}=ans_{[0,r]}-ans_{[0,l-1]}$。

尽管有的题目的数位 dp 不采用记忆化搜索更为方便，但所有数位 dp 都可以写成一样的数位 dp 模板。所以只要掌握了数位 dp 的模板，数位 dp 就拿下了。

蒟酱自用万能数位 dp 模板不怕前导零99成新

using loli=long long;
basic_string<int>sta;
loli dfs(int pos,bool zer,bool lim,...){
	if(!pos)return ...
	if(~f[pos][zer][lim][...])return f[pos][zer][lim][...];
	loli ans=0;
	for(int i=zer,num=lim?sta[pos]:9;i<=num;i++){
		ans+=dfs(pos-1,0,lim&&i==num,...)
	}
	return f[pos][zer][lim][...]=ans;
}
loli solve(loli n){
	memset(f,-1,sizeof f);
	sta.clear();
	do sta+=int(n%10),n/=10;while(n);
	sta=0+sta;
	loli ans=dfs(siz(sta)-1,1,1,...);
	for(int i=siz(sta)-2;i>=0;i--)ans+=dfs(i,1,0,...);
	return ans;
}

其中 f[pos][zer][lim] 表示当前处理到了第 pos 位，zer 的值 1/0 分别表示当前这位能/否写 0 防止枚举到有前导 0 的不合法的数字，lim 的值 1/0 表示前面所有位是否紧贴最大值，如果前面前面所有位都紧贴最大值，这一位的取值就有限制，否则可以任意取。

Luogu P2602 数字计数：给定两个正整数 $a,b$，求在 $[a,b]$ 中的所有整数中，每个数码各出现了多少次，$a,b\le10^{12}$。

不妨做 $10$ 次，第 $D$ 次去做数码 $D$ 的出现次数。
只需要统计数码 $D$ 的出现次数 cnt 这一个量。
转移也很简单，ans+=dfs(pos-1,0,lim&&i==num,cnt+(i==D));。

loli dfs(int pos,bool zer,bool lim,int cnt){
	if(!pos)return cnt;
	if(~f[pos][zer][lim][cnt])return f[pos][zer][lim][cnt];
	loli ans=0;
	for(int i=zer,num=lim?sta[pos]:9;i<=num;i++){
		ans+=dfs(pos-1,0,lim&&i==num,cnt+(i==D));
	}
	return f[pos][zer][lim][cnt]=ans;
}
loli solve(loli n){
	memset(f,-1,sizeof f);
	sta.clear();
	do sta+=int(n%10),n/=10;while(n);
	sta=0+sta;
	loli ans=dfs(siz(sta)-1,1,1,0);
	for(int i=siz(sta)-2;i>=0;i--)ans+=dfs(i,1,0,0);
	return ans;
}

Luogu P2657 [SCOI2009] windy 数：给定两个正整数 $a,b$，求在 $[a,b]$ 中的所有整数中，有多少数满足任意相邻两数码差至少为 $2$，$a,b\le2\times10^{9}$。

只需要记录上一位填的数码 pre，在枚举当前位时进行特判即可。
小技巧：填首位数字时，把 pre 当成 $11$ 可以减少很多特判。

loli dfs(int pos,bool zer,bool lim,int pre){
	if(!pos)return 1;
	if(~f[pos][zer][lim][pre])return f[pos][zer][lim][pre];
	loli ans=0;
	for(int i=zer,num=lim?sta[pos]:9;i<=num;i++){
		if(abs(pre-i)>1)ans+=dfs(pos-1,0,lim&&i==num,i);
	}
	return f[pos][zer][lim][pre]=ans;
}
loli solve(loli n){
	memset(f,-1,sizeof f);
	sta.clear();
	do sta+=int(n%10),n/=10;while(n);
	sta=0+sta;
	loli ans=dfs(siz(sta)-1,1,1,11);
	for(int i=siz(sta)-2;i>=0;i--)ans+=dfs(i,1,0,11);
	return ans;
}

CF55D Beautiful numbers：给定两个正整数 $a,b$，求在 $[a,b]$ 中的所有整数中，有多少数满足这个数可以被它每一个非零数码整除，$a,b\le9\times10^{18}$。

我们可以对每一个数码 $1\sim9$ 记录其是否出现过，然后记录这个数模 $2520$ 的结果，如果这个数模 $2520$ 的结果能被其每个出现过的数码整除就合法。
更快的写法没必要记录每个数码是否出现过，只需要记录这些数码的 $\operatorname{lcm}$ 即可，但 $\operatorname{lcm}$ 是跳跃的，可以写离散化，也可以用 unordered_map 记录 dp 数组。

unordered_map<int,loli>f[20][2][2][2521];
loli dfs(int pos,bool zer,bool lim,int val,int mul){
	if(!pos)return val%mul==0;
	if(f[pos][zer][lim][val].count(mul))return f[pos][zer][lim][val][mul];
	loli ans=0;
	for(int i=zer,num=lim?sta[pos]:9;i<=num;i++){
		ans+=dfs(pos-1,0,lim&&i==num,(val*10+i)%2520,lcm(mul,i?i:1));
	}
	return f[pos][zer][lim][val][mul]=ans;
}
loli solve(loli n){
	// memset(f,-1,sizeof f);
	for(int i=0;i<20;i++)for(int j=0;j<2521;j++){
		f[i][0][0][j].clear();
		f[i][0][1][j].clear();
		f[i][1][0][j].clear();
		f[i][1][1][j].clear();
	}
	sta.clear();
	do sta+=int(n%10),n/=10;while(n);
	sta=0+sta;
	loli ans=dfs(siz(sta)-1,1,1,0,1);
	for(int i=siz(sta)-2;i>=0;i--)ans+=dfs(i,1,0,0,1);
	return ans;
}

然而超时了，问题出现在每次询问都要清空状态，太浪费时间，可以把 zer lim 不放进记忆化数组来节省时间。

unordered_map<int,loli>f[20][2521];
loli dfs(int pos,bool zer,bool lim,int val,int mul){
	if(!pos)return val%mul==0;
	if(!zer&&!lim&&f[pos][val].count(mul))return f[pos][val][mul];
	loli ans=0;
	for(int i=zer,num=lim?sta[pos]:9;i<=num;i++){
		ans+=dfs(pos-1,0,lim&&i==num,(val*10+i)%2520,lcm(mul,i?i:1));
	}
	return zer||lim?ans:f[pos][val][mul]=ans;
}
loli solve(loli n){
	sta.clear();
	do sta+=int(n%10),n/=10;while(n);
	sta=0+sta;
	loli ans=dfs(siz(sta)-1,1,1,0,1);
	for(int i=siz(sta)-2;i>=0;i--)ans+=dfs(i,1,0,0,1);
	return ans;
}

什么？还是超时？你把 unordered_map 换成离散化就过了。
不想改怎么办？我们应该分析一下 zer 到底是干什么用的，有无 zer 影响的是前导零，这在一些记录连续数位或者回文或者出现次数或者相邻数位关系的题目上有作用，对于这题，我们的前导零不影响取模结果，所以可以将这维删去，而前面两题记录 zer 的确可以减少我们的分类讨论。
语言建议选 C++17 (GCC 7-32)，这个快一点。

unordered_map<int,loli>f[20][2521];
loli dfs(int pos,bool lim,int val,int mul){
	if(!pos)return val%mul==0;
	if(!lim&&f[pos][val].count(mul))return f[pos][val][mul];
	loli ans=0;
	for(int i=0,num=lim?sta[pos]:9;i<=num;i++){
		ans+=dfs(pos-1,lim&&i==num,(val*10+i)%2520,lcm(mul,i?i:1));
	}
	return lim?ans:f[pos][val][mul]=ans;
}
loli solve(loli n){
	sta.clear();
	do sta+=int(n%10),n/=10;while(n);
	sta=0+sta;
	loli ans=dfs(siz(sta)-1,1,0,1);
	return ans;
}