非常哈人动态规划，使我脑子旋转。

概念

数位动态规划：简称为「数位 DP」，是一种与数位相关的一类计数类动态规划问题，即在数位上进行动态规划。这里的数位指的是个位、十位、百位、千位等。

数位 DP 一般用于求解给定区间 [left, right] 中，满足特定条件的数值个数，或者用于求解满足特定条件的第 k 小数。

数位 DP 通常有以下几个特征：

1. 题目会提供一个查询区间（有时也会只提供区间上界）来作为统计限制。
2. 题目中给定区间往往很大（比如 [-1e9, 1e9]，无法采用朴素的方法求解。
3. 题目中给定的给定的限定条件往往与数位有关。
4. 要求统计满足特定条件的数值个数，或者用于求解满足特定条件的第 k 小数。

例题

计数问题

338. 计数问题 - AcWing题库

如果每次都要求一次[a, b]间0~9出现次数，必然会出现大量重复计算。因此可以利用前缀和思想，实现一个函数count(n, x)，统计1~n中数字x出现的次数，然后区间[a, b]内数字x出现的次数就是count(b, x) - count(a-1, x)。

例如，要统计1~n中1出现的次数，可以分别求出1在区间内每个数的每一位上出现的次数，然后将这些次数累加。

然后看看它的子问题，统计1~n在各个位上出现的次数。

例如，要求1在第四位上出现的次数，可以先将数据展开为1 <= xxx1yyy(符合条件的数) <= abcdefg = n，然后分情况讨论以找到1~n中所有第四位为1的数：

• xxx可以是000 ~ abc-1，那么yyy就得是000 ~ 999，也就是abc * 1000个数。
• xxx = abc，还得分子情况：
  • d < 1，发现abc1yyy怎么取值都比abc0efg大，因此没有符合条件的数。
  • d = 1，yyy可以取000 ~ efg，也就是efg + 1个数。
  • d > 1，yyy可以取000 ~ 999，也就是1000个数。

然后1 ~ n中所有第四位为1的数就是上面情况的总和。

这里漏了几个边界情况：

• 假设要统计0在第四位上出现的次数，那么第一种情况会出错。如果xxx取000，第四位也是0，那么整个数就是个三位数，第四位根本不存在。因此，在统计0的时候，第一种情况xxx应该取001 ~ abc-1。
• 最高位不可取0，因此“统计0在最高位上出现的次数”这个子问题是不存在的，我们要直接从最高位的下一位开始枚举。

参考代码如下：

// 获取num数组从第l位到第r位的数
int getNum(const vector<int> &num, int l, int r)
{
    int res = 0;
    for (int i = l; i >= r; --i)
        res = res * 10 + num[i];
    return res;
}

// 获取10^x
int power10(int x)
{
    int res = 1;
    while (x--)
        res *= 10;
    return res;
}

// 统计[1 ~ n]内数字x出现的次数
int count(int n, int x)
{
    // n不可能取0
    if (n == 0)
        return 0;

    // 将n的各位数放到数组中, 然后修改n为总位数
    vector<int> num;
    while (n)
    {
        num.push_back(n % 10);
        n /= 10;
    }
    n = num.size();

    // 开始统计次数, 从高位开始枚举, 这里num0起点, 所以i = n-1.
    int res = 0;
    // 最高位不可取0, 要直接从最高位的下一位开始枚举.
    for (int i = n - 1 - !x; i >= 0; i--)
    {
        // 当前枚举的不是最高位才有情况1
        if (i < n - 1)
        {
            res += getNum(num, n - 1, i + 1) * power10(i);
            // 情况1的边界情况: x = 0, 要从0...1开始枚举
            if (!x)
                res -= power10(i);
        }

        // 情况2
        if (num[i] == x)
            res += getNum(num, i - 1, 0) + 1;
        else if (num[i] > x)
            res += power10(i);
    }

    return res;
}

int main()
{
    int a, b;
    while (cin >> a >> b, a || b)
    {
        // a可能大于b
        if (a > b)
            swap(a, b);
        // 统计[a, b]内数字0~9出现的次数
        for (int i = 0; i < 10; ++i)
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << '\n';
    }
}

练习题