leecode2719 | 统计整数数目

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

num1 <= x <= num2
min_sum <= digit_sum(x) <= max_sum.
请你返回好整数的数目。答案可能很大，请返回答案对 109 + 7 取余后>的结果。

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

class Solution {
    const int MOD = 1'000'000'007;
    int calc(string& s, int min_sum, int max_sum){
        int n = s.length();
        vector<vector<int>> memo(n, vector<int>(min(9*n, max_sum) + 1, -1));
        function<int(int, int, bool)> dfs = [&](int i, int sum, bool is_limit) -> int{
            if(sum > max_sum){
                return 0;
            }
            if(i == n){
                return sum >= min_sum ? 1 : 0;
            }
            if(! is_limit && memo[i][sum] != -1){
                return memo[i][sum];
            }
            int up = is_limit ? s[i] - '0' : 9;
            int res = 0;
            for(int d = 0; d <= up; d++){
                res = (res + dfs(i + 1, sum + d, is_limit &&d == up))% MOD;
            }
            if(!is_limit){
                memo[i][sum] = res;
            }
            return res;
        };
        
        return dfs(0, 0, true);
    }
public:
    int count(string num1, string num2, int min_sum, int max_sum) {
        int ans = calc(num2, min_sum, max_sum) - calc(num1, min_sum, max_sum) + MOD;
        int sum = 0;
        for(char x : num1){
            sum += x - '0';
        }
        ans += min_sum <= sum && sum <= max_sum;
        return ans % MOD;
    }
};

################################################

//之前写的一个通俗易懂的暴力  结果超时
class Solution {
public:
    int count(string num1, string num2, int min_sum, int max_sum) {
        int min_ = 0, max_ = 0;
        int num1_ = std::atoi(num1.c_str()), num2_ = std::atoi(num2.c_str());
        while(num1_ != 0){
            min_ = min_ *10 + num1_ % 10;
            num1_  /=10;
        }
        while(num2_ != 0){
            max_ = max_ *10 + num2_ % 10;
            num2_ /=10;
        }
        int ans = 0;
        for(int i = min_; i <= max_; ++i){
            int x = 0;
            while(i != 0){
                x += i % 10;
                i /= 10;
            }
            if(x >= min_sum && x <= max_sum){
                ans ++;
            }
        }
        //return (int)(ans%(1e9 + 7));
        return static_cast<int>(fmod(ans, 1e9 + 7));


    }
};

##############################################
后面继续详细分析数位这类题型 以及其核心思想