$\Huge\color{orchid}{点击此处获取更多干货}$

数位类动态规划

数位类动态规划主要解决的问题，都跟一个范围内的所有数有关，主要分为2类：
1. 某些特定数码及其组合出现过的总次数
2. 构成该数的所有数位满足一定条件的数量
其中第一类问题相对比较简单，也是本帖着重讨论的内容，第二类问题由于比较多样化，具有一定难度，在提高篇中才会遇到。

本问题需要统计$0\sim 9$每一个数码在某范围内出现的总次数，笨办法就是对每个数不断取模后用10去除，得到每一位数字之后再累加，这是一个时间复杂度为$O(n*logn)$的算法，其中$n$指的是范围的长度。但如果$n$的数量级特别大，达到了$10^7$及以上，即便是这样的算法仍然会耗时巨大，而数位dp就可以显著的减少时间复杂度。

数位dp的通常方法也是递归法即记忆化搜索，思考方式则利用到了前缀和思想，对于范围$L\sim R$上的问题，先变成前缀$0\sim N$上的问题，然后对$0\sim R$和$0\sim L-1$分别解决一次，最后将两者结果相减即可得出最终结果。以$0\sim N$为例，假设$N=239$，从低到高数，第1、2、3位的数码分别为9、3、2，为了确保考虑到的数不大于$N$，当第3位取0、1时，第2位可以取所有的10个数码，但第3位取2时，第2位就需要受限制，只能取到3及以下的数码。因此，高位的数码可以按照是否达到上限为标准分为两类讨论，如果未达上限，则低位数码选择不受限制；如果达到了上限，则低位数码要受限制，并且同样分此两类

由此可以得出，数位dp必定考虑的两个维度为当前数位的位阶$lv$，以及数码选择是否受限，即布尔值$limit$，可以给出一个粗略的dp图表：

显而易见的是，在转移时，受限制的状态只会使用一次，但是不受限制的状态会被重复利用，因此$limit$这一维度可以省略，只有不受限制的状态会被存入dp表。

对于本问题，dp时可以再加两个维度：
1. 前导0情况$zero$。由于数码0也纳入了被统计的范围，而它不能作为前导0出现，因此转移时需要判断当前填上的0是否为前导0，和$limit$一样，非前导0状态会被重复利用，而前导0状态只会用一次，只有非前导0状态会被存入dp表。
2. 待统计的数码已经出现的次数。这个可以作为dp表的第2维度使用，此时表内的$dp(lv,cur)$就表示当前位阶为$lv$，该数码已经出现了$cur$次，按照此前的规则继续枚举，最终该数码能得到的总数。当$lv=0$即枚举完每一个数位后，可以直接将$cur$返回。

最后一个问题：当前数位在什么情况下会导致$cur$的增加？
也需要分两种情况来讨论：
1. 待统计数码为0：非前导0状态$(zero = false)$，或者已经到了最低位$(lv=1)$
2. 待统计数码不是0：可选数码中含有该数码

C++ 代码

下面的代码中，会将实现细节写在注释里

#include <iostream>
#include <cstring>
#include <climits>
using namespace std;

// 64位带符号整数型数值最多含有19位
// 如果输入中不包含数字的最多位数，可将位阶最大值定为20
// 如果给出了数字的最多位数，那就按照实际的最多位数来定
const int MAXL = 20;

// 位阶最大值为19，那么数码的最大数量也为19
int dp[MAXL][MAXL];
int digit[MAXL];

/**
 * @brief 统计从low到high的所有数中，数码d在数位上出现了多少次
 * @param d 待统计数码
 * @param low,high 范围上下界
 * @return 数量
 */
int digitCount(int d, int low, int high);

/**
 * @brief 前缀0~n中数码d的数量
 * @param d 待统计数码，仅用于传参
 * @param n 前缀的上界
 * @return 数量
 */
int countBelowN(int d, int n);

/**
 * @brief 记忆化搜索核心函数
 * @param d 待统计数码
 * @param lv 当前数位的位阶（从低到高）
 * @param limit 数码选择是否受限（默认true）
 * @param zero 前导0状态（默认true）
 * @param cur 当前数码d已经出现的次数（默认0）
 * @return 最终能得到的数码d数量
 */
int dfs(int d, int lv, 
    bool limit = true, bool zero = true, 
    int cur = 0);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int low, high;
    while (true) {
        cin >> low >> high;
        if (low == 0 && high == 0) break;
        if (low > high) swap(low, high);        //不保证输入的low一定不大于high
        for (int i = 0; i <= 9; i++) {
            cout << digitCount(i, low, high) << " ";
        }
        cout << endl;
    }
    return 0;
}

int digitCount(int d, int low, int high) {
    //前缀上限小于10，不管其他数位如何，0一定会出现一次，可加入特判
    if (d == 0 && low < 10) return countBelowN(d, high) - 1;
    else return countBelowN(d, high) - countBelowN(d, low - 1);
}

int countBelowN(int d, int n) {
    memset(dp, -1, MAXL * MAXL * sizeof(int));  //每次调用时分别独立计算
    memset(digit, 0, MAXL * sizeof(int));
    int lv = 0;
    while (n > 0) {                             //算出每个数位的上限
        digit[++lv] = n % 10;
        n /= 10;
    }
    return dfs(d, lv);                          //初始情况当作包含前导0并且高位受限
}

int dfs(int d, int lv, bool limit, bool zero, int cur) {
    if (lv == 0) return cur;                    //到底了，返回
    if (!limit && !zero && dp[lv][cur] != -1) {
        return dp[lv][cur];                     //不受限制，非前导0才会涉及dp表存取
    }
    int ans = 0;
    int top = limit ? digit[lv] : 9;
    for (int i = 0; i <= top; i++) {            //枚举每个数码
        //高位已受限制，当前位已达上限，属于受限制的情况
        //处于前导0的状态下，当前枚举到数码0，继续保持前导0状态
        if (d == 0) {   //非前导0状态，或处于最低位，可以选择0
            ans += dfs(d, lv - 1, 
                limit && top == i, zero && i == 0, 
                cur + (i == 0 && (!zero || lv == 1)));
        }
        else {
            ans += dfs(d, lv - 1, 
                limit && top == i, zero && i == 0, 
                cur + (i == d));
        }
    }
    if (!limit && !zero) dp[lv][cur] = ans;
    return ans;
}