给你两个数字字符串?
num1?和?num2?，以及两个整数?max_sum?和?min_sum?。如果一个整数?x?满足以下条件，我们称它是一个好整数：
num1 <= x <= num2min_sum <= digit_sum(x) <= max_sum.请你返回好整数的数目。答案可能很大，请返回答案对? 1 0 9 + 7 10^9 + 7 109+7?取余后的结果。
注意，
digit_sum(x)?表示?x?各位数字之和。
- 1 ≤ n u m 1 ≤ n u m 2 ≤ 1 0 22 1 \le num_1 \le num_2 \le 10^{22} 1≤num1?≤num2?≤1022
1 <= min_sum <= max_sum <= 400
最直接的思路就是遍历[num1,num2]的所有整数，判断其数位之和是否满足条件。
for(int i = num1;i <= num2;++i) {
if(digit_sum(i) >= min_sum && digit_sum(i) <= min_sum) {
++res;
}
}
对于一个“困难”题目来说，这个思路无疑太简单了，提交后果然会超时。
那么除此之外还有什么解决方案吗？这就要涉及到数位DP了，所谓数位DP：
数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制。
数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：
- 要求统计满足一定条件的数的数量（即，最终目的为计数）；
- 这些条件经过转化后可以使用「数位」的思想去理解和判断；
- 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
- 上界很大（比如 1 0 18 10^{18} 1018），暴力枚举验证会超时。
数位DP的详细讲解可以参考OI Wiki 数位DP
按照上述特征，本题目明显属于数位DP能够解决的问题：
所以本题目是一种典型的数位DP问题，现在我们可以利用数位DP的方法来解决本题目了。
假设对于一个长度为l的数字num，我们定义f(string num, int i, int j, bool limit)表示构造第i位及其之后数位满足要求的方案数目，另外：
j表示前面选中数字（0到i - 1）的数字和。limit，表示当前是否受到了n的约束，因为选择数字时，数字构成的数不能大于n。比如n为123，如果第2位选择2，此时第3位要受到n的限制，只能选择1、2或者3；而如果第2位选择1，此时第3位是不受到限制的，可以选择0-9中的任意数字那么f(num, 0, 0, true)，也就是第0位及其之后数位满足要求的方案数目，也就是区间[0, num]中所有整数中满足数位和大于等于min_sum，并小于等于max_sum的个数。
那么为了求解区间[num1,num2]中所有满足要求的整数个数，只需要f(num2,0,0,true) - f(num1 -1, 0,0,true)，也就是最终答案。
在计算过程中，对于f(int i, int j, bool limit)：
如果j已经超过了max_sum的限制，表示已经不可能满足要求了，直接返回0。
如果i == l，就是数位0到l-1都已经选定了，也就是已经构造完成，此时j如果满足要求（min_sum <= j <= max_sum），就构成一个方案，返回1.
遍历当前位可能的选择：
对于每一种选择x，可能的方案数是f(i + 1, j + x, limit && x == n[i])，所有可能选择x对应的方案数加起来就是f(i,j,limit)的答案。
为了提升计算效率，我们利用dp[i][j]表示数字填写到第i位，已填的数字位数之和为j时，符合条件的数字个数。
C++代码实现如下：
class Solution {
private:
const int MOD = 1e9 + 7;
int max;
int min;
int dfs(string num, int i, int j, bool limit,vector<vector<int>>& dp) {
if(j > this->max) {
return 0;
}
if(i == num.size()) {
return j >= this->min;
}
if(!limit && dp[i][j] != -1){
return dp[i][j];
}
int res = 0;
int up = limit ? num[i] - '0' : 9;
for(int d = 0;d <= up;++d) {
res = (res + dfs(num, i + 1, j + d, limit && d == up, dp)) % MOD;
}
if(!limit) {
dp[i][j] = res;
}
return res;
}
int get(string num) {
vector<vector<int>> dp = vector<vector<int>>(num.size(), vector<int>(this->max + 1, -1));
return dfs(num, 0, 0, true, dp);
}
// 获取num - 1对应数字
string strNumDes(string num) {
int i = num.size() - 1;
while (num[i] == '0') {
i--;
}
num[i]--;
i++;
while (i < num.size()) {
num[i] = '9';
i++;
}
return num;
}
public:
int count(string num1, string num2, int min_sum, int max_sum) {
this->max = max_sum;
this->min = min_sum;
return (get(num2) - get(strNumDes(num1)) + MOD) % MOD;
}
};
看完代码实现后，读者可能存在一些疑问：
为什么只有在limit为false的情况下才使用缓存dp？
设想一种情况，对于num = 321，min_sum = 0，max_sum = 12的情况：
23时，也就是i = 2, j = 5，limit = false，此时记录了dp[2][5]，32时，此时也是i = 2，j = 5，但是limit = true。这两种情况下，虽然i，j相同，但满足要求的方案数是不同的，前者有8种（230、231、232、233、234、235、236、237），后者受限于数字num，只有2种（320、321）。
因此，只有在limit为false时才使用缓存。
基于上面那个问题，那如果将limit加入到缓存维度中，是否就可以不再特殊考虑limit了？比如dp[2][i][j]，其中dp[0][i][j]表示limit为false的情况，dp[1][i][j]表示limit为true的情况。
这种方案当然可以得到最终答案，但在这么做之前可以先思考一下是否有必要。
limit为true的子问题只会被调用一次，将对这些子问题做缓存并不会提升性能，所以并没有必要这么做。
数位DP相关的题目有很多，但只要了解其中规律，应该还是可以顺利解决的，罗列下面几个数位DP相关题目，供大家训练加强。