windy 数(Windy Numbers) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

long long memo[15][12];
string s;

long long dfs(int pos, int last, bool lead, bool tight) {
    if (pos == (int)s.size()) return 1;
    if (!tight && !lead && memo[pos][last] != -1) return memo[pos][last];
    int up = tight ? (s[pos] - '0') : 9;
    long long res = 0;
    for (int d = 0; d <= up; ++d) {
        if (lead) {
            res += dfs(pos + 1, d, d == 0, tight && (d == up));
        } else if (abs(d - last) >= 2) {
            res += dfs(pos + 1, d, false, tight && (d == up));
        }
    }
    if (!tight && !lead) memo[pos][last] = res;
    return res;
}

long long solve(long long x) {
    if (x <= 0) return 0;
    s = to_string(x);
    for (int i = 0; i < 15; ++i) {
        for (int j = 0; j < 12; ++j) {
            memo[i][j] = -1;
        }
    }
    return dfs(0, 0, true, true) - 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long a, b;
    if (!(cin >> a >> b)) return 0;
    cout << solve(b) - solve(a - 1) << "\n";
    return 0;
}