题目大意：求给定一个区间内满足每一位的数相差大于(2)且没有前导零的数的个数。
( ext{Solution:})
我们可以按照数位(dp).设状态为当前要(dp)第(pos)位，上一位填的是(pre,)当前是不是顶到最大值((fg)),当前是不是有前导零。
那么我们可以获得一个转移：(dp[pos][pre][fg][zero])由它的后面一位(dp[pos-1][pre'][fg'][zero'])转移而来。转移的时候，我们枚举可行的数，并改变相应状态即可。
实现上我们可以(dfs).当当前位置处理完了就返回(1)(因为要计数)，枚举的时候把所有不可能状态去掉即可。
初值之所以设前一位填的是(11)是因为这样不论是哪一个数字与它的差都会大于(2)，这才能保证第一位哪个数都可以填。
#include<bits/stdc++.h>
using namespace std;
int L,R,a[2000],dp[20][20][2][2];
int dfs(int pos,int pre,int fg,int zero){
if(!pos)return 1;
if(dp[pos][pre][fg][zero])return dp[pos][pre][fg][zero];
int res=0;
for(int i=0;i<=9;++i){
if((i<=a[pos]||!fg)&&(abs(i-pre)>=2||zero)){
res+=dfs(pos-1,i,fg&&(i==a[pos]),zero&&(!i));
}
}
dp[pos][pre][fg][zero]=res;
return res;
}
int calc(int num){
int cnt=0;
memset(dp,0,sizeof(dp));
while(num){
a[++cnt]=num%10;
num/=10;
}
return dfs(cnt,11,1,1);
}
int main(){
cin>>L>>R;
cout<<calc(R)-calc(L-1)<<endl;
//复杂度是dp数组大小*for循环转移的大小
return 0;
}