C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 384K, 提交时间: 2021-02-21 18:04:54

#include<bits/stdc++.h>
using namespace std;
int l,r,dp[20][20],bound[20];
int dfs(int pos,int pre,bool head,bool flag){
    if(pos==0)return 1;
    if(!flag&&pre>0&&dp[pos][pre]!=-1)return dp[pos][pre];
    int maxs=flag?bound[pos]:9,ans=0;
    for(int i=0;i<=maxs;i++){
        if(abs(i-pre)>=2||head)  ans+=dfs(pos-1,i,head&&(i==0),flag&&(i==maxs));
    }
    if(!flag)dp[pos][pre]=ans;
    return ans;
}
int kk(int x){
    int p=0;
    while(x>0){
        bound[++p]=x%10;
        x/=10;
    }
    return dfs(p,-100,1,1);
}
int main(){
    memset(dp, -1, sizeof(dp));
    cin>>l>>r;
    cout<<kk(r)-kk(l-1);
}