2719. 统计整数数目(2355)

给你两个数字字符串 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，把num1和num2设为上下界，一次dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    int min_sum, max_sum, memo[][], MOD = (int)1e9+7;
    public int count(String num1, String num2, int min_sum, int max_sum) {
        this.min_sum = min_sum;
        this.max_sum = max_sum;
        int n = num2.length();
        memo = new int[n][Math.min(n*9, max_sum)+1];
        for (int row[] : memo) Arrays.fill(row, -1);
        num1 = "0".repeat(n - num1.length()) + num1; // 补前导零，和 num2 对齐
        return dfs(0, 0, true, true, num1.toCharArray(), num2.toCharArray());
    }
    // 这题也可以不需要isNum参数，不需要判断这个数是否存在，反正最后会被min_sum过滤
    public int dfs(int i, int sum, boolean isLimitLow, boolean isLimitHigh, char num1[], char num2[]) {
        if (sum > max_sum) return 0;
        if (i == num1.length) return sum < min_sum ? 0 : 1;
        // 需要判断isLimit，因为（如果下边界是123456，那对于123xxx和321xxx来说，他们的计算过程是不能被复用的，因为123xxx后面的xxx是要受到下边界456的限制，所以要单独计算。而对于321xxx来说，是没有任何限制，321xxx和231xxx的后面xxx的数量是通用的， 所以可以记忆化）
        if (!isLimitLow && !isLimitHigh && memo[i][sum] != -1) return memo[i][sum];
        int lo = isLimitLow ? num1[i]-'0' : 0, hi = isLimitHigh ? num2[i]-'0' : 9, res = 0;
        for (int d = lo; d <= hi; d++) {
            res += dfs(i+1, sum+d, isLimitLow && d == lo, isLimitHigh && d == hi, num1, num2);
            res %= MOD;
        }
        if (!isLimitLow && !isLimitHigh) memo[i][sum] = res;
        return res;
    }
}