题目大意：给你一个数的范围 [A，B] ，问你这段区间内，有几个数满足如下条件：
1、两个相邻数位上的数的差值至少为 2 。
2、不包含前导零。
很简单的数位DP，可想只需标记前导零 lead， 前一个数 pre ，即可暴力统计答案，再记忆化就行了，但是有些地方还要细心一点。
比如在枚举到第一个有效位时（即非前导零），它当前只有一个数，而我们需要设 q = true （q 表示枚举到当前位时，是否满足条件，即相邻位之差是否达到 2 ）。即我需要保证枚举到第二个有效数位时，要与第一个有效数位作差值比较的话，那么在枚举第一个有效位时，不能使得 q == false。
然后根据样例 1 可以知道，个位数也算。那么为了使第一位满足 abs（i - pre）>= 2 的话，那么我们需要使得一开始 pre == -1 即可，因为 i 最少会为 1 。
代码如下：
根据条件枚举数位
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
int A,B;
int a[],dp[][];
ll dfs(int pos,int pre,bool lead,bool limit){
if(pos==) return ;
if(!limit&&!lead&&dp[pos][pre]!=-) return dp[pos][pre];
int up=limit?a[pos]:;
ll res=;
for(int i=;i<=up;i++){
if(lead&&i==) res+=dfs(pos-,-,true,limit&&i==a[pos]);
else{
if(abs(i-pre)>=){
res+=dfs(pos-,i,false,limit&&i==a[pos]);
}
}
}
if(!limit&&!lead) dp[pos][pre]=res;
return res;
}
ll solve(ll x)
{
int pos=;
while(x){
a[++pos]=x%;
x/=;
}
return dfs(pos,-,true,true);
}
int main()
{
//freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
memset(dp,-,sizeof(dp));
while(~scanf("%d%d",&A,&B)){
printf("%lld\n",solve(B)-solve(A-));
}
}
直接枚举，根据 q 值判断是否正确。需要三维 DP 来保存 q 的状态。
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
int A,B;
int a[],dp[][][];
ll dfs(int pos,int pre,bool q,bool lead,bool limit){
if(pos==) return q;
if(!limit&&!lead&&dp[pos][pre][q]!=-) return dp[pos][pre][q];
int up=limit?a[pos]:;
ll res=;
for(int i=;i<=up;i++){
if(lead&&i==) res+=dfs(pos-,pre,q,true,limit&&i==a[pos]);
else res+=dfs(pos-,i,q&&(abs(pre-i)>=),false,limit&&i==a[pos]);
}
if(!limit&&!lead) dp[pos][pre][q]=res;
return res;
}
ll solve(ll x)
{
int pos=;
while(x){
a[++pos]=x%;
x/=;
}
return dfs(pos,-,true,true,true);
}
int main()
{
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
memset(dp,-,sizeof(dp));
scanf("%d%d",&A,&B);
printf("%lld\n",solve(B)-solve(A-));
}