windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，

在A和B之间，包括A和B，总共有多少个windy数？

数位dp

#include <bits/stdc++.h>
#include <iostream>
#include <string.h>
#include <math.h>

using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 22;

int digit[maxn], tot, d;
int cnt[10];
ll dp[maxn][10][10];

ll dfs(int len, int pre, int top, int limit) { //
    if (!len) return 1;
    if (!limit && dp[len][pre][top] != -1) return dp[len][pre][top];
    int up = (limit?digit[len]:9);
    ll res = 0;
    for (int i = 0; i <= up; i++) {
        if (top == 0) {
            res += dfs(len - 1, i, i, (limit && (i == up)));
        } else if (abs(pre - i) >= 2) {
            res += dfs(len - 1, i, (top?top:i), (limit && (i == up)));
        }
    }
    if (!limit) dp[len][pre][top] = res;
    return res;
}

ll solve(ll n) {
    memset(dp, -1, sizeof(dp));
    tot = 0;
    while (n) {
        digit[++tot] = n % 10; n /= 10;
    }
    return dfs(tot, 0, 0, 1);
}

int main() {
    freopen("in.in", "r", stdin);
//    freopen("o2.out", "w", stdout);
    ll l, r;
    cin >> l >> r;
    cout << solve(r) - solve(l - 1) <<endl;
    return 0;
}