数位 dp 解法

本文介绍了数位 dp 解法。

算法学习笔记(22)：数位DP（数位动态规划） - 知乎 (zhihu.com)

https://leetcode.cn/problems/count-of-integers/solutions/2601111/tong-ji-zheng-shu-shu-mu-by-leetcode-sol-qxqd/

适用场景

求解区间 $[l, r]$ 内满足约束条件的数的数量。

数位 dp 方法

第一步，采用前缀和思想，将求解区间 $[l, r]$ 内满足约束条件的数的数量转换为：在区间 $[1,r]$ 内满足约束的数量 - 在区间 $[1, l-1]$ 内满足约束的数量。其中，左边界取决于题目要求。即，将求解的问题转换为在区间 $[1,x]$ 中满足约束的数量。

第二步，将数字 $x$ 拆分为一个个数位，在代码中表现为将 $x$ 的每一位分解为 10 进制或 2 进制数，用数组 $a$ 存储。

例如，数字 $x=4321$，拆分为数位后，$a[3]=4,a[2]=3,a[1]=2,a[0]=1$。

代码上的实现为：

int len = 0;
while (x > 0) {
    	a[len++] = x % 10;
    	x /= 10;
}

第三步，考虑从高位往低位填数。

使用记忆搜索法，每一次搜索填写一个数。用形参 $pos$ 表示当前要填写的位置：

• $pos$ 是一个 int 型变量，表示当前填数的位置，从高到低。

假设 $x=4132$，用 $?$ 表示尚未填写的数位，则当前状态为 $????$

（1）填写第 $len-1$ 位，即最高位。很明显，此时最高位的值只能填写 $0\sim4$。此时：

• 若最高位大于 4，则不在枚举范围内；
• 若最高位等于 4，那么后续填写的数字仍然受限，下一位显然不能超过 1；
• 若最高位等于 $0 \sim 3$，则后面的数字可以任意填写。

此时，需要记录变量 $limit$ 来判断当前填写的数位是否受到限制：

• $limit$ 是一个 bool 型变量，表示枚举的第 $pos$ 位是否受到限制
  • 若 $limit=true$，则表示当前 $pos$ 位取值不能大于 $a[pos]$。当且仅当 $pos$ 前面第 $i$ 位的数都等于 $a[i]$ 时（$i=pos+1, pos+2,…,len-1$），$limit=true$；
  • 若 $limit=false$，则当前 $pos$ 位的值可以任意选取。

（2）重复上述操作，直到搜索到 $pos=0$。此时所有的数位都填写完毕，即每个 $?$ 都填入了具体数字。此时，到达递归边界，需要返回所填写的所有数位和 $sum$。

第四步，使用动态规划方法减少算法的时间复杂度。上述三步的方法时标准的 DFS 搜索，其时间复杂度过高。因此，我们要使用动态规划减少冗余的重复计算。

记状态 $f[pos][sum]$ （dp 值）表示位置 $pos$ 前的数都已经搜索完毕，且这些数位之和为 $sum$，其值为满足约束条件的所有数的数位和之和。在初始化时，令所有 $f[pos][sum]$ 的值都为 $-1$。

对于 $pos$ 及其右边的数，他们只需要知道 $pos$ 前面的数的数位和即可，而不需要知道前面具体填了哪些数。对于 $x=4321$，当填写状态为 $03??$, $12??$, $21??$, $30??$, $…$ 的时候，我们只需要搜索出 $03??$ 的答案并记录，当搜索到其余相同状况的状态时，只需要查表即可找到答案，避免了多次搜索所带来的额外时间开销。

此时，记忆化搜索的代码为：

int dfs(int pos, bool limit, int sum) {
    // 递归边界
    if (!pos)
        return sum;
    // 若取值没有限制，且 dp 值已经被搜索过
    if (!limit && f[pos][sum] != -1)
        return f[pos][sum];
    
    int upper = limit ? a[pos] : 9;
    int res = 0;
    for (int i = 0; i <= upper; i++)
        // 当且仅当 pos 前面第 i 位的数都等于 a[i] 时，limit=true
        res = (res + dfs(pos-1, limit && i == upper, sum + i));
    
    // 将当前搜索值记录下来
    if (!limit)
        f[pos][sum] = res;
    
    return res;
}

接着，再在 $solve$ 中调用 $dfs$ 即可：

int solve(int x) {
	int len = 0;
    while (x > 0) {
        a[len++] = x % 10;
        x /= 10;
    }
    return dfs(len, true, 0);
}

打赏