数位DP板子题。
DP[i][j]记录到第i位前一位数字是j的数字数。
下附代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int dp[20][15]; 4 int dim[20]; 5 int dfs(int x,int st,int jb){ 6 if (!x) return 1; 7 if (!jb && dp[x][st]!=-1) return dp[x][st]; 8 int maxn=9,ret=0; 9 if (jb) maxn=dim[x]; 10 for (int i=0; i<=maxn; i++){ 11 if (abs(st-i)<2) continue; 12 if (st==11 && i==0){ 13 ret+=dfs(x-1,11,(jb==1 && i==maxn)); 14 } 15 else ret+=dfs(x-1,i,(jb==1 && i==maxn)); 16 } 17 if (!jb) return dp[x][st]=ret; 18 return ret; 19 } 20 int main(){ 21 string a,b; 22 cin>>a>>b; 23 memset(dp,-1,sizeof(dp)); 24 for (int i=0; i<a.length(); i++){ 25 dim[a.length()-i]=a[i]-'0'; 26 } 27 dim[1]-=1; 28 int j=1; 29 while (dim[j]<0){ 30 dim[j]+=10; 31 dim[j+1]-=1; 32 j++; 33 } 34 int l=dfs(a.length(),11,1); 35 for (int i=0; i<b.length(); i++){ 36 dim[b.length()-i]=b[i]-'0'; 37 } 38 int r=dfs(b.length(),11,1); 39 printf("%d",r-l); 40 }