思路分析

一：对于这种区间的数位dp问题，首先转化为前缀和的思路分析，即sum（l, r) = sum(0, r) - sum(0, l-1);

二：将输入的边界x转化为k进制存入数组备用

ll solve(int x, int target) {
    memset(dp, -1, sizeof dp);
    int len = 0;
    while (x) {
        arr[++len] = x % 10;
        x /= 10;
    }
    return dfs(len, -1, true, true);//后俩参数是lead 和 limit ，一般都初始化为true
}

三：记忆化搜索按照从高位到低位的顺序进行dfs，记忆化搜索的结构一般为以下

//dp维度一般为dfs参数中除了limit和lead以外的所有参数都要作为dp的维度
//pos:从高位到低位的第几位 pre:当前位的上一位 limit:控制当前位的枚举范围 lead：是否有前导0 
ll dfs(int pos, int pre, bool limit, bool lead){
    if(!pos) return 1;//表示找到了一个满足答案的数
    if(!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];//这里都是固定写法，记住就好了
    int up = limit ? arr[pos] : 9;//这里就是找到枚举范围
    int ans = 0;//用来记录当前的答案
    for(int i = 0;i <= up;++i){
        //讨论前导0
        if(lead){
            ans += dfs(...);
        }else{
            ans += dfs(...);
        }
    }
    if(!limit && !lead) dp[pos][pre] = ans;
    return ans;
}

四：本题求的是0-9中每个数出现的次数，上面分析的是满足某个性质的数的个数（return 1，可以看出来），所以这个题就不需要pre参数了，把它替换为sum，表示0-9中某个数出现的次数，dp的维度就变为pos和sum

C++ 代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2001, M = 20;
int arr[M];
ll dp[M][N];

ll dfs(int pos, int target, ll sum, bool limit, bool lead){
    if(!pos) return sum;
    if(!lead && !limit && (dp[pos][sum] != -1)) return dp[pos][sum]; 

    int top = limit ? arr[pos] : 9;
    ll ans = 0;
    for(int i = 0;i <= top;++i)
        if(lead) 
            ans += dfs(pos-1, target, sum + ((i == target) && (i != 0)), limit && (i == arr[pos]), lead && (i == 0));
        else 
            ans += dfs(pos-1, target, sum + (i == target), limit && (i == arr[pos]), lead && (i == 0));

    if(!limit && !lead) dp[pos][sum] = ans;
    return ans;
}

ll solve(int x, int target) {
    memset(dp, -1, sizeof dp);
    int len = 0;
    while (x) {
        arr[++len] = x % 10;
        x /= 10;
    }
    return dfs(len, target, 0, true, true);
}

int main() {
    int a, b;

    while (  cin >> a >> b,  a || b) {
        if (a > b) swap(a, b);
        for (int i = 0; i <= 9; i ++)
            cout << solve(b, i) - solve(a-1, i) << " ";
        cout << endl;
    }

    return 0;
}