每日AC

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int dp[20][11]; int digit[20];
int len;
int dfs(int pos, int pre, bool flag) {

if (pos == len) {
    return 1; 
}
if (!flag && dp[pos][pre + 1] != -1) {
    return dp[pos][pre + 1];
}
int limit = flag ? digit[pos] : 9; 
int start = (pre == -1) ? 0 : pre; 
int ans = 0;
for (int d = start; d <= limit; ++d) {
    int new_pre;
    bool new_flag = flag && (d == digit[pos]);
    if (pre == -1) {
        new_pre = (d == 0) ? -1 : d;
    } else {
        new_pre = d;
    }
    ans += dfs(pos + 1, new_pre, new_flag);
}
if (!flag) {
    dp[pos][pre + 1] = ans;
}
return ans;

}

// 计算0到n的不降数个数 int f(int n) {

if (n < 0) return 0;
len = 0;
if (n == 0) {
    digit[len++] = 0;
} else {
    int temp = n;
    while (temp) {
        digit[len++] = temp % 10;
        temp /= 10;
    }
    reverse(digit, digit + len);
}
memset(dp, -1, sizeof(dp)); 
return dfs(0, -1, true);

}

int main() {

int a, b;
while (cin >> a >> b) {
    cout << f(b) - f(a - 1) << endl;
}
return 0;

}