统计整数数目-526互联

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

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

请你返回好整数的数目

一. 数位dp

class Solution {
    const int MOD = 1e9 + 7;

    int f(string s, int min_sum, int max_sum) {//因为要求两次，直接封装成函数
        int n = s.length(), memo[n][min(9 * n, max_sum) + 1];//用于减少不受限情况下的重复计算
        memset(memo, -1, sizeof(memo)); // -1 表示没有计算过

        function<int(int, int, bool)> f = [&](int i, int sum, bool is_limit) -> int {
            if (sum > max_sum) return 0; // 非法数字
            if (i == n) return sum >= min_sum;//边界条件
            if (!is_limit && memo[i][sum] != -1) return memo[i][sum]; //对应个数已经存在

            int res = 0; //满足条件的个数
            int up = is_limit ? s[i] - '0' : 9; //受限需要小于等于s[i]，不受限可以取任意值，前面数字相同时，后面数受限
            for (int d = 0; d <= up; ++d) // 枚举要填入的数字 d,因为会影响到后面的数位和，所以不能数学运算，必须递归
                res = (res + f(i + 1, sum + d, is_limit && d == up)) % MOD; //前面数受限，且当前数取最大值，导致后面数受限
            if (!is_limit) memo[i][sum] = res;//不受限的情况只需要计算一次，记录下来
            return res; //返回结果
        };

        return f(0, 0, true);//从第0位开始，当前数位和为0
    }

public:
    int count(string num1, string num2, int min_sum, int max_sum) {
        int ans = f(num2, min_sum, max_sum) - f(num1, min_sum, max_sum) + MOD; // 避免负数，做差直接计算满足条件的个数
        int sum = 0;
        for (char c: num1) sum += c - '0'; //计算nums1数位和
        ans += min_sum <= sum && sum <= max_sum; // x=num1 是合法的，补回来
        return ans % MOD;
    }
};

二. 自己写的

class Solution {
    const int MOD = 1e9 + 7;
    //dp[i][j]表示从第i位开始，当前数位和为j的情况下，后面满足条件数的个数
    int min_; int max_;
    int f(string &s){//封装成函数
        int n =s.size();
        vector<vector<int>> dp (n,vector<int>(min(9*n+1,max_+1),-1));
        return dfs(dp,s,0,0,1);
    }
    int dfs(vector<vector<int>> &dp, string&s,int index,int cursum,bool limit){
        if(cursum>max_) return 0;//边界条件一，超出范围剪枝返回
        if(index==s.size()) return cursum>=min_;//边界条件二，遍历完所有数
        if(!limit&&dp[index][cursum]!=-1) return dp[index][cursum];//保证非上限值，只用计算一次

        int res = 0;
        int up = limit?s[index]-'0':9;//当前位置可选数
        //做选择
        for(int i=0;i<=up;i++)
            res = (res + dfs(dp,s,index+1,cursum+i,limit&&(i==up)))%MOD;
        if(!limit) dp[index][cursum] = res;//记录减少重复计算
        return res;
    }

public:
    int count(string num1, string num2, int min_sum, int max_sum) {
        min_ = min_sum; max_ = max_sum;
        int res = f(num2) - f(num1) + MOD; // 避免负数，做差直接计算满足条件的个数
        int sum = 0;
        for (char c: num1) sum += c - '0'; //计算nums1数位和
        if(min_<= sum && sum <= max_) res++; // x=num1 是合法的，补回来
        return res % MOD;
    }
};