链接: https://www.luogu.com.cn/problem/P2657
记忆化搜索
其实不记忆化搜索也能过,直接搜...

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[10], f[16][2][10];

ll dfs(int pos, int lit, int begin, int last){
    if(pos == 0) return 1;
    if(!lit && f[pos][begin][last] != 0) return f[pos][begin][last];
    int high = lit ? a[pos] : 9;
    int ret = 0;
    for(int i = 0; i <= high; i++){
        if(!begin || abs(last - i) > 1) ret += dfs(pos - 1, lit && i == high, begin || (i != 0), i);
    }
    if(!lit) f[pos][begin][last] = ret;
    return ret;
}

ll work(int n){
    int cnt = 1;
    while(n > 0){
        a[cnt++] = n % 10;
        n/=10;
    }
    return dfs(cnt - 1, 1, 0, -2);
}

int main(){
    int n,m;
    cin>>n>>m;
    if(n > m) swap(n,m);
    printf("%lld", work(m) -  work(n - 1));
}