手机端网站建站手册,dedecms网站,跨境电商主要平台有哪些,个人网站备案名称填写的注意事项2719. 统计整数数目
给你两个数字字符串 num1 和 num2 #xff0c;以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件#xff0c;我们称它是一个好整数#xff1a;
num1 x num2 min_sum digit_sum(x) max_sum. 请你返回好整数的数目。答…2719. 统计整数数目
给你两个数字字符串 num1 和 num2 以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件我们称它是一个好整数
num1 x num2 min_sum digit_sum(x) max_sum. 请你返回好整数的数目。答案可能很大请返回答案对 109 7 取余后的结果。
注意digit_sum(x) 表示 x 各位数字之和。
示例 1
输入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 。 示例 2
输入num1 “1”, num2 “5”, min_num 1, max_num 5 输出5 解释数位和在 1 到 5 之间的 5 个整数分别为 1,2,3,4 和 5 。所以我们返回 5 。
提示
1 num1 num2 1022 1 min_sum max_sum 400
数位DP根本不会背了板子都写错了还得靠灵神
class Solution {
public:int count(string num1, string num2, int min_sum, int max_sum) {int n num2.length();num1 string(n - num1.length(), 0) num1; // 补前导零和 num2 对齐vectorvectorint memo(n, vectorint(min(9 * n, max_sum) 1, -1));functionint(int, int, bool, bool) dfs [](int i, int sum, bool limit_low, bool limit_high) - int {if (sum max_sum) { // 非法return 0;}if (i n) {return sum min_sum;}if (!limit_low !limit_high memo[i][sum] ! -1) {return memo[i][sum];}int lo limit_low ? num1[i] - 0 : 0;int hi limit_high ? num2[i] - 0 : 9;int res 0;for (int d lo; d hi; d) { // 枚举当前数位填 dres (res dfs(i 1, sum d, limit_low d lo, limit_high d hi)) % 1000000007;}if (!limit_low !limit_high) {memo[i][sum] res;}return res;};return dfs(0, 0, true, true);}
};
这里指路灵神题解两种数位 DP 模板
