定义一个数字是“好数”，当且仅当它的十进制表示下有不超过3个数字1∼9

举个例子：4,200000,102034,200000,10203是“好数”，然而4231,102306,72774200004231,102306,7277420000不是

给定[l,r]，问有多少个x使得l≤x≤r，且x是“好数”

一共有T(1≤T≤10^4)组数据，对于每次的询问，输出一行一个整数表示答案

数位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;
ll dp[maxn][22];

ll dfs(int len, int cnt, int top) {
    if (!len) {
        if (cnt <= 3) return 1;
        return 0;
    }
    if (!top && dp[len][cnt] != -1) return dp[len][cnt];
    int up = (top ? digit[len] : 9);
    ll res = 0;
    for (int i = 0; i <= up; i++) {
        res += dfs(len - 1, cnt + (i >= 1), top && (i == up));//如当i>=1计数+1
    }
    if (!top) dp[len][cnt] = 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, 1);
}

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