AcWing 1083. Windy数

#include 

using namespace std;
const int N = 15;
int a[N];
int dp[N][N];

/**
 *
 * @param pos   当前位置
 * @param pre   前一位数位的数字是多少
 * @param lead  本位是不是需要考虑前导0
 * @param limit 是否贴着上界
 * @return
 */
int dfs(int pos, int pre, bool lead, bool limit) {
    if (pos == -1) return 1;
    if (!limit && !lead && ~dp[pos][pre]) return dp[pos][pre];
    int res = 0, up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; i++)
        if (abs(pre - i) >= 2) {
            bool st = lead && !i;
            res += dfs(pos - 1, st ? -2 : i, st, limit && i == up);
        }
    return limit ? res : dp[pos][pre] = res;
}

int cal(int x) {
    int pos = 0;
    while (x) a[pos++] = x % 10, x /= 10;
    return dfs(pos - 1, -2, true, true);//pre 给初值-2,保证首位是啥都可以
}

signed main() {
    int l, r;
    cin >> l >> r;
    memset(dp, -1, sizeof dp);
    cout << cal(r) - cal(l - 1) << endl;
    return 0;
}