详解

传送门

这里 limit 是一个状态，记忆化时，只需记忆非 limit 的状态，其他记忆情况按题目要求即可

例题

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-of-integers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

数位DP

代码

#define ll long long
class Solution {
public:
    int p = 1e9 + 7;
    ll mp[25][405];
    int mn, mx;
    ll get(vector<int>& all, int cur, bool limit, int sum) {

        if (cur < 0) {
            if (mn <= sum && sum <= mx) return 1;
            return 0;
        }

        if (!limit && mp[cur][sum] != -1) return mp[cur][sum];

        int up = limit ? all[cur] : 9;

        ll ans = 0;

        for (int i = 0; i <= up; ++ i) {
            ans = (ans + get(all, cur - 1, (i == up) && limit, sum + i)) % p;
        }

        if (!limit) mp[cur][sum] = ans;

        return ans;

    };
    int count(string num1, string num2, int min_sum, int max_sum) {
        mn = min_sum, mx = max_sum;
        vector<int> a1, a2;
        for (int i = num2.size() - 1; i >= 0; -- i) {
            a2.push_back(num2[i] - '0');
        }
        for (int i = num1.size() - 1; i >= 0; -- i) {
            a1.push_back(num1[i] - '0');
        }

        int t = 1;
        for (int i = 0; i < a1.size(); ++ i) {
            if (a1[i] < t) {
                a1[i] = a1[i] - t + 10;
                t = 1;
            }else {
                a1[i] -= t;
                t = 0;
            }
        }
        while (a1.size() > 1 && a1.back() == 0) a1.pop_back();

        memset(mp, -1, sizeof mp);
        ll a2t = get(a2, a2.size() - 1, 1, 0);

        memset(mp, -1, sizeof mp);
        ll a1t = get(a1, a1.size() - 1, 1, 0);

        ll ans = (a2t - a1t + p) % p;

        return ans;

    }
};