题目链接：https://loj.ac/problem/10165#submit_code
思路：数位dp，记录是否为前导0，已经是否为上边界和前一个数的值即可，如果前面已经有数了，那要和前一个数之差的绝对值要大于等于2才行。具体实现请看代码。
#include<bits/stdc++.h> using namespace std; typedef long long ll; int a[30]; ll dp[30][20]; //pos : 位数 qd : 是否为前导 flag : 是否处于上边界 x : 上一个位数的值 ll dfs(int pos,bool qd,bool flag,int x) { if(pos==0) return 1; int up=flag?a[pos]:9;//确定上边界 if((!flag)&&(!qd)&&dp[pos][x]!=-1)//如果之前已经求出，则直接返回 return dp[pos][x]; ll tmp=0; for(int i=0;i<=up;i++) { if(i==0&&qd)//依旧是前导0 tmp+=dfs(pos-1,qd,flag&&i==a[pos],0); else if(qd)//前面的数是前导0，这是第一个数，不需要考虑差要大于等于2 tmp+=dfs(pos-1,false,flag&&i==a[pos],i); else if(abs(i-x)>=2)//要保证两个数的差大于等于2 tmp+=dfs(pos-1,false,flag&&i==a[pos],i); } if((!flag)&&(!qd)) dp[pos][x]=tmp;//记录值，方便下次直接返回 return tmp; } ll fun(int x) { int pos=0; while(x)//将x的每一位进行分解 { a[++pos]=x%10; x/=10; } return dfs(pos,true,true,0); } int main() { memset(dp,-1,sizeof(dp)); int l,r; cin>>l>>r; cout<<fun(r)-fun(l-1)<<endl; }