Hard

题目描述

给你两个数字字符串 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：

输入：num1 = "1", num2 = "12", min_sum = 1, max_sum = 8
输出：11
解释：数位和在 1 到 8 之间的 11 个整数分别是：1,2,3,4,5,6,7,8,10,11, 和 12。因此，我们返回 11。

示例 2：

输入：num1 = "1", num2 = "5", min_sum = 1, max_sum = 5
输出：5
解释：数位和在 1 到 5 之间的 5 个整数分别是：1,2,3,4, 和 5。因此，我们返回 5。

提示：

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

解题思路

这是一道典型的数位动态规划问题。我们需要统计在 [num1, num2] 范围内，数位和在 [min_sum, max_sum] 范围内的数字个数。

核心思路是利用容斥原理：count(num2) - count(num1-1)，其中 count(x) 表示从 1 到 x 中满足数位和条件的数字个数。

数位 DP 状态设计：

  • pos：当前填到第几位
  • sum：当前已填数字的数位和
  • tight：是否受到上界限制
  • started：是否已经开始填非零数字（处理前导零）

状态转移时，我们枚举当前位可以填的数字（0-9），但需要考虑 tight 约束。如果当前位受到上界限制，那么最大只能填到对应位的数字；否则可以填 0-9。

为了处理 num1-1，我们需要实现一个字符串减一的函数。减一操作需要处理借位，类似手工计算减法。

最终答案就是 count(num2, min_sum, max_sum) - count(num1-1, min_sum, max_sum)。

代码实现

class Solution {
private:
    const int MOD = 1e9 + 7;
    string num;
    int minSum, maxSum;
    int memo[25][401][2][2];
    
    int dp(int pos, int sum, int tight, int started) {
        if (pos == num.size()) {
            return (started && sum >= minSum && sum <= maxSum) ? 1 : 0;
        }
        
        if (memo[pos][sum][tight][started] != -1) {
            return memo[pos][sum][tight][started];
        }
        
        int limit = tight ? (num[pos] - '0') : 9;
        int res = 0;
        
        for (int digit = 0; digit <= limit; digit++) {
            int newSum = sum + digit;
            int newTight = tight && (digit == limit);
            int newStarted = started || (digit > 0);
            
            if (newSum <= maxSum) {
                res = (res + dp(pos + 1, newSum, newTight, newStarted)) % MOD;
            }
        }
        
        return memo[pos][sum][tight][started] = res;
    }
    
    string subtract1(string s) {
        int i = s.size() - 1;
        while (i >= 0 && s[i] == '0') {
            s[i] = '9';
            i--;
        }
        if (i >= 0) s[i]--;
        
        int start = 0;
        while (start < s.size() && s[start] == '0') start++;
        return start == s.size() ? "0" : s.substr(start);
    }
    
    int countGood(string n) {
        num = n;
        memset(memo, -1, sizeof(memo));
        return dp(0, 0, 1, 0);
    }
    
public:
    int count(string num1, string num2, int min_sum, int max_sum) {
        minSum = min_sum;
        maxSum = max_sum;
        
        int count2 = countGood(num2);
        string num1Minus1 = subtract1(num1);
        int count1 = (num1Minus1 == "0") ? 0 : countGood(num1Minus1);
        
        return (count2 - count1 + MOD) % MOD;
    }
};

class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        MOD = 10**9 + 7
        
        def subtract1(s):
            s = list(s)
            i = len(s) - 1
            while i >= 0 and s[i] == '0':
                s[i] = '9'
                i -= 1
            if i >= 0:
                s[i] = str(int(s[i]) - 1)
            
            start = 0
            while start < len(s) and s[start] == '0':
                start += 1
            return '0' if start == len(s) else ''.join(s[start:])
        
        def countGood(num):
            n = len(num)
            memo = {}
            
            def dp(pos, sum_digits, tight, started):
                if pos == n:
                    return 1 if started and min_sum <= sum_digits <= max_sum else 0
                
                if (pos, sum_digits, tight, started) in memo:
                    return memo[(pos, sum_digits, tight, started)]
                
                limit = int(num[pos]) if tight else 9
                res = 0
                
                for digit in range(limit + 1):
                    new_sum = sum_digits + digit
                    new_tight = tight and (digit == limit)
                    new_started = started or (digit > 0)
                    
                    if new_sum <= max_sum:
                        res = (res + dp(pos + 1, new_sum, new_tight, new_started)) % MOD
                
                memo[(pos, sum_digits, tight, started)] = res
                return res
            
            return dp(0, 0, True, False)
        
        count2 = countGood(num2)
        num1_minus1 = subtract1(num1)
        count1 = 0 if num1_minus1 == "0" else countGood(num1_minus1)
        
        return (count2 - count1 + MOD) % MOD

public class Solution {
    private const int MOD = 1000000007;
    private string num;
    private int minSum, maxSum;
    private int[,,,] memo;
    
    private int Dp(int pos, int sum, int tight, int started) {
        if (pos == num.Length) {
            return (started == 1 && sum >= minSum && sum <= maxSum) ? 1 : 0;
        }
        
        if (memo[pos, sum, tight, started] != -1) {
            return memo[pos, sum, tight, started];
        }
        
        int limit = tight == 1 ? (num[pos] - '0') : 9;
        int res = 0;
        
        for (int digit = 0; digit <= limit; digit++) {
            int newSum = sum + digit;
            int newTight = (tight == 1 && digit == limit) ? 1 : 0;
            int newStarted = (started == 1 || digit > 0) ? 1 : 0;
            
            if (newSum <= maxSum) {
                res = (res + Dp(pos + 1, newSum, newTight, newStarted)) % MOD;
            }
        }
        
        return memo[pos, sum, tight, started] = res;
    }
    
    private string Subtract1(string s) {
        char[] arr = s.ToCharArray();
        int i = arr.Length - 1;
        
        while (i >= 0 && arr[i] == '0') {
            arr[i] = '9';
            i--;
        }
        if (i >= 0) arr[i]--;
        
        int start = 0;
        while (start < arr.Length && arr[start] == '0') start++;
        return start == arr.Length ? "0" : new string(arr, start, arr.Length - start);
    }
    
    private int CountGood(string n) {
        num = n;
        memo = new int[25, 401, 2, 2];
        for (int i = 0; i < 25; i++) {
            for (int j = 0; j < 401; j++) {
                for (int k = 0; k < 2; k++) {
                    for (int l = 0; l < 2; l++) {
                        memo[i, j, k, l] = -1;
                    }
                }
            }
        }
        return Dp(0, 0, 1, 0);
    }
    
    public int Count(string num1, string num2, int min_sum, int max_sum) {
        minSum = min_sum;
        maxSum = max_sum;
        
        int count2 = CountGood(num2);
        string num1Minus1 = Subtract1(num1);
        int count1 = (num1Minus1 == "0") ? 0 : CountGood(num1Minus1);
        
        return (count2 - count1 + MOD) % MOD;
    }
}

var count = function(num1, num2, min_sum, max_sum) {
    const MOD = 1000000007;
    
    function subtract1(s) {
        let arr = s.split('');
        let i = arr.length - 1;
        
        while (i >= 0 && arr[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n × max_sum × 10)
空间复杂度O(n × max_sum)

其中 n 是数字字符串的长度（最大为 22），max_sum 最大为 400。数位 DP 的状态数为 O(n × max_sum × 2 × 2)，每个状态需要枚举 10 个数字，所以时间复杂度为 O(n × max_sum × 10)。空间复杂度主要来自记忆化数组。

相关题目