统计整数数目
给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数：
num1 <= x <= num2-
min_sum <= digit_sum(x) <= max_sum.
请你返回好整数的数目。答案可能很大，请返回答案对 109 + 7 取余后的结果。
注意，digit_sum(x) 表示 x 各位数字之和。
示例一
输入：num1 = "1", num2 = "12", min_num = 1, max_num = 8 输出：11 解释：总共有 11 个整数的数位和在 1 到 8 之间，分别是 1,2,3,4,5,6,7,8,10,11 和 12 。所以我们返回 11 。
1 <= num1 <= num2 <= 10221 <= min_sum <= max_sum <= 400
思路：
题目要求求解数值范围在 nums1到 nums2之间，并且数位和在 min_sum到 max_sum之间的整数个数，其中nums1和 nums2以字符串形式给出。
定义函数 get(num)，用于求解 1∼num1范围内有多少整数数位和介于 min_sum∼max_sum之间，那么原问题就转换为求解 get(num2)−get(num1−1)
设 num 共有n 位，我们从最高位（即第 n−1 位）开始遍历，目前聚焦于第 i 位，前面第 n−1 位到第 i+1 位的数位和为 sum，现在需要考虑第 i 位填充的数字 x。通常 x 可以取 0∼9 中的任意一个数字，但当第 n−1 位到第 i+1 位放置的数字都与 num 一样时，x 的取值范围缩小至 0∼num[i]，在代码中，当 limit 为 true 时，表示这一特殊情况发生。
试想，如果 limit 标识为false，x 取值范围为 0∼9，那么后续的第 i−1 到第 0 位的取值范围都是 0∼9。这样一来，子问题就与 num 的值无关。我们定义状态 d[i][j] 表示还剩第 i 位到第 0 位的数字未填，而已填的数字位数之和为 j 时，符合条件的数字个数有多少个。在求解时，子问题与 n 的值无关，也与 num 无关，因此只有当limit 为 false 可以使用或更新 d[i][j]。
当然，limit 这一维度也可以加入到状态中，但 limit 为 true 的子问题只会被调用一次，将答案记忆化存储毫无意义，并且每次重新调用 get 时都需要重新计算所有状态答案，得不偿失。因此定义函数 dfs(i,j,limit) 用于问题求解，在 limit 为 false 时借助 d[i][j] 防止重复计算，加快执行速度。
细节：
我们采用记忆化搜索的方式实现数位动态规划，将所有d[i][j] 的初始值设置为 −1。递归过程：
若 limit 为 true 时，在 0∼num[i] 范围内遍历 x，并递归调用 dfs(i−1,j+x,limit&&x==nums[i])，统计所有返回值的和作为答案。
若 limit 为 false 时，若 d[i][j] ！= −1，则直接返回 d[i][j]，否则在 0∼9 范围内遍历 x，并递归调用 dfs(i−1,j+x,false)，统计所有返回值的和并更新 d[i][j]。
若 j 已经大于 max_sum，可以剪枝，直接返回 0。当 i 等于 −1 时，递归结束，此时若 j≥min_sum 则返回 1，否则返回 0。需要注意的是，由于上文中第 n−1 位表示数字的最高位，第 0 位表示数字的最低位（即个位），因此需要将题目中输入的数字翻转。文章来源：https://www.toymoban.com/news/detail-794528.html
另外在计算最终结果时一定记得num2和num1-1的结果相减后，加上一个模后再取一次模，因为取模前提下后者不一定小于前者，最终答案肯定不能是负数。文章来源地址https://www.toymoban.com/news/detail-794528.html
class Solution {
static constexpr int N = 23;
static constexpr int M = 401;
static constexpr int MOD = 1e9 + 7;
int d[N][M];
string num;
int min_sum;
int max_sum;
int dfs(int i,int j,bool limit)
{
if(j>max_sum)
{
return 0;
}
if(i == -1)
{
return j >=min_sum;//当 i 等于−1时，递归结束，此时若 j≥min_sum则返回 1，否则返回0
}
if(!limit && d[i][j] != -1)
{
return d[i][j];
}
int res = 0;
int up = limit ? num[i] - '0' : 9;
for (int x = 0; x <= up; x++)
{
res = (res + dfs(i - 1, j + x, limit && x==up)) % MOD;
}
if(!limit)
{
d[i][j] = res;
}
return res;
}
int get(string num)
{
reverse(num.begin(),num.end());// 反转字符串
this->num = num;// 将反转后的字符串保存到成员变量中
return dfs(num.size() - 1, 0 ,true);// 调用dfs函数进行递归计算
}
//求解 num - 1，先把最后一个非 0 字符减去 1，再把后面的 0 字符变为 9
string sub(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) {
memset(d,-1,sizeof d);
this->min_sum = min_sum;
this->max_sum = max_sum;
return (get(num2) - get((sub(num1))) + MOD) % MOD;//一定记得num2和num1-1的结果相减后，加上一个模后再取一次模，因为取模前提下后者不一定小于前者，最终答案肯定不能是负数。
}
};
到了这里，关于力扣刷题第二天 统计整数数目（每天一题）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
