Leetcode 2024-12-21 题目分享

经典数位DP题目+剪枝操作。

2719. 统计整数数目

给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数：

num1 <= x <= num2
min_sum <= digit_sum(x) <= max_sum.

请你返回好整数的数目。答案可能很大，请返回答案对 10^9 + 7 取余后的结果。

注意，digit_sum(x) 表示 x 各位数字之和。

示例 1：

1
2
3

输入：num1 = "1", num2 = "12", min_num = 1, max_num = 8
输出：11
解释：总共有 11 个整数的数位和在 1 到 8 之间，分别是 1,2,3,4,5,6,7,8,10,11 和 12 。所以我们返回 11 。

示例 2：

1
2
3

输入：num1 = "1", num2 = "5", min_num = 1, max_num = 5
输出：5
解释：数位和在 1 到 5 之间的 5 个整数分别为 1,2,3,4 和 5 。所以我们返回 5 。

提示：

1 <= num1 <= num2 <= 10^22
1 <= min_sum <= max_sum <= 400

思路

针对数位问题，并且给了上界和下界；数据量超大 => 数位DP。
详细解释在代码里。

代码

function count(num1: string, num2: string, min_sum: number, max_sum: number): number {
    let N = 24, T = 401, M = 1e9 + 7;
    // 用数组保存各个数位和，方便dfs使用。
    let val = new Array(N).fill(0);
    // DP数组：当前处理到第 i 位，数位和为 j 时的方案数。
    let dp = new Array(N).fill(0).map(() => new Array(T).fill(-1));
    // 记忆化搜索：当前处理到第 len 位，数位和为 sum，且上界限制为 f 时的方案数。
    let dfs = (len: number, sum: number, f: boolean): number => {
        // 遍历完了，看一下数位和是否满足条件。
        if (len == 0) return sum >= min_sum && sum <= max_sum ? 1 : 0;
        // 记忆化：（不考虑上界限制为true的，因为这种状态只可能有一种）
        if (!f && dp[len][sum] != -1) return dp[len][sum];
        // up是可枚举的数位最大值：如果没有上界限制，可以一直枚举到9。
        let res = 0, up = f ? val[len] : 9;
        for (let i = 0; i <= up; i++) {
            // 剪枝操作：
            // 1. sum已经超过了max，即使后面都选0，最终也是大于max的，不计入答案
            // 2. sum加上后面所有数位都选最大值，仍然小于min，这也不会计入答案
            if (sum + i > max_sum || sum + i + (len - 1) * 9 < min_sum) continue;
            res = (res + dfs(len - 1, sum + i, f && i == up)) % M;
        }
        if (!f) dp[len][sum] = res;
        return res;
    };
    let getCnt = (num: string): number => {
        val.fill(0);
        for (let i = 0, n = num.length; i < n; i++) {
            val[i + 1] = parseInt(num[n - i - 1]);
        }
        return dfs(N - 1, 0, true);
    };
    // 单独检查一下num1是不是满足条件
    // 因为最后dfs结果相减，求的是[num1+1, num2]区间答案。
    let checkNum = (num: string): number => {
        let sum = num.split('').reduce((pre: number, cur: string) => {
            return parseInt(cur) + pre;
        }, 0);
        return sum >= min_sum && sum <= max_sum ? 1 : 0;
    };
    return (getCnt(num2) - getCnt(num1) + checkNum(num1) + M) % M;
};

复杂度分析

时间：O(10 * log num2 * max_sum)。DP数组一共有log num2 * max_sum个状态（数字的位数*各个数位和），而每一个状态需要10次遍历求解（枚举当前数位从0一直到9）。
空间：O(log num2 * max_sum)。