很少做数位(dp)的题，做道题学习一下吧。
记忆化搜索，(f[10][10][2][2])分别记录当前位置，上一位数，是否有前导零和是否有大小上限。
题目要满足相邻两个数相差不小于2，如果有前导零就可以无视这个限制，如果没有就要先判断一下。
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[10][10][2][2],c[10],num,a,b;
int dfs(int wei,int last,int qdl,int xz){
if(wei==0) return 1;
if(f[wei][last][qdl][xz])
return f[wei][last][qdl][xz];
int lim=xz?c[wei]:9,&tot=f[wei][last][qdl][xz];
for(int i=0;i<=lim;i++){
if(!qdl&&abs(last-i)<2)
continue;
tot+=dfs(wei-1,i,qdl&&!i,xz&&i==lim);
}
return tot;
}
inline int work(int x){
num=0;
memset(f,0,sizeof(f));
while(x){
c[++num]=x%10;
x/=10;
}
return dfs(num,0,1,1);
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d%d",&a,&b);
printf("%d
",work(b)-work(a-1));
return 0;
}