2719. Count of Integers

题目 #

You are given two numeric strings num1 and num2 and two integers max_sum and min_sum. We denote an integer x to be good if:

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

Return the number of good integers. Since the answer may be large, return it modulo 109 + 7.

Note that digit_sum(x) denotes the sum of the digits of x.

Example 1:

Input: num1 = "1", num2 = "12", min_num = 1, max_num = 8
Output: 11
Explanation: There are 11 integers whose sum of digits lies between 1 and 8 are 1,2,3,4,5,6,7,8,10,11, and 12. Thus, we return 11.

Example 2:

Input: num1 = "1", num2 = "5", min_num = 1, max_num = 5
Output: 5
Explanation: The 5 integers whose sum of digits lies between 1 and 5 are 1,2,3,4, and 5. Thus, we return 5.

Constraints:

  • $1 <= num1 <= num2 <= 10^{22}$
  • 1 <= min_sum <= max_sum <= 400

思路1 数位dp（记忆化搜索） #

分析 #

  • 直接使用数位dp的记忆化搜索写法，求小于某个数的，所有位加在一起在给定范围的数量总和
  • 小于num2大于num1可以用，小于num2的数量减去小于num1-1的数量得到

代码 # 

 1func count(num1 string, num2 string, min_sum int, max_sum int) int {
 2	var mod int = 1e9 + 7
 3	// 返回小于s的满足条件的数量
 4	getCount := func(s string) int {
 5		// 状态记忆数组，第一维是位数，第二维是状态（当前表示为前面数字的和），value是数量
 6		memo := make([][]int, len(s))
 7		for i := range memo {
 8			memo[i] = make([]int, max_sum+1)
 9			for j := range memo[i] {
10				memo[i][j] = -1
11			}
12		}
13
14		// p为当前要枚举的位，0是最高位，len(s)-1是最低位
15		// sum是前面位数的和
16		// limitUp代表前面的数位是否都到达上界
17		var dfs func(p, sum int, limitUp bool) (res int)
18		dfs = func(p, sum int, limitUp bool) (res int) {
19			if sum > max_sum {
20				return
21			}
22			if p == len(s) {
23				// 到头了，sum必须大于等于最小sum
24				if sum >= min_sum {
25					return 1
26				}
27				return
28			}
29
30			if !limitUp {
31				// 没到上界才能取状态，否则状态是假的
32				tmp := memo[p][sum]
33				if tmp >= 0 {
34					return tmp
35				}
36				defer func() { memo[p][sum] = res }()
37			}
38			up := 9
39			if limitUp {
40				up = int(s[p] - '0')
41			}
42			for d := 0; d <= up; d++ {
43				res = (res + dfs(p+1, sum+d, limitUp && d == int(s[p]-'0'))) % mod
44			}
45			return
46		}
47		return dfs(0, 0, true)
48	}
49
50	ans := getCount(num2) - getCount(num1) + mod
51	// 判断一下num1是否合法，上面直接减去了num1而不是num1-1，少算了num1
52	sumNum1 := 0
53	for _, c := range num1 {
54		sumNum1 += int(c - '0')
55	}
56	if sumNum1 >= min_sum && sumNum1 <= max_sum {
57		ans++
58	}
59	return ans % mod
60}

思路2 数位dp（递推） #

分析 #

  • 从最高位开始构造，记录一个数组保存每一位可以到达的sum对应的数量，不包含上界，因为每一位都可以从0到9，到了上界就不能到9了
  • 单独统计一下上界，假设前面的都到上界，当前位除了到上界的情况都可以统计到数组中
  • 到最后一位时，需要判断最小值，前面不考虑最小值，只考虑最大值

代码 # 

 1func count2(num1 string, num2 string, min_sum int, max_sum int) int {
 2	var mod int = 1e9 + 7
 3
 4	// 返回能取到的最大值
 5	getMax := func(s int) int {
 6		maxNum := 9
 7		if s+maxNum > max_sum {
 8			maxNum = max_sum - s
 9		}
10		return maxNum
11	}
12	getMin := func(s int) int {
13		minNum := min_sum - s
14		if minNum < 0 {
15			minNum = 0
16		}
17		return minNum
18	}
19
20	// 返回小于s的满足条件的数量
21	getCount := func(s string) int {
22		n := len(s)
23		// 最后一位要特殊处理，所以这里要对只有一位的情况单独计算
24		if n == 1 {
25			num := int(s[0] - '0')
26			if num < min_sum {
27				return 0
28			}
29			return num - min_sum + 1
30		}
31		// 记录前一位可以到达某个sum的统计数量，要求下一位可以从0算到9，也就是当前不能到上界
32		preState := make([]int, max_sum+1)
33		limitSum := 0
34		// 遍历到除最后一位，最后一位要判断最小值
35		for _, v := range s[:n-1] {
36			num := int(v - '0')
37			curState := make([]int, max_sum+1)
38			// 到前一位已经得到的sum为st
39			for st, c := range preState {
40				if c == 0 {
41					continue
42				}
43				maxNum := getMax(st)
44				for d := 0; d <= maxNum; d++ {
45					curState[d+st] = (curState[d+st] + c) % mod
46				}
47			}
48			// 算一下上界的情况，当前位除了到达上界，下一位都可以按照0到9算，所以直接加到状态中
49			maxNum := getMax(limitSum)
50			for d := 0; d <= maxNum && d < num; d++ {
51				curState[d+limitSum] = (curState[d+limitSum] + 1) % mod
52			}
53			limitSum += num
54			preState = curState
55		}
56
57		// 遍历最后一位
58		res := 0
59		for st, c := range preState {
60			if c == 0 {
61				continue
62			}
63			minNum := getMin(st)
64			maxNum := getMax(st)
65			for d := minNum; d <= maxNum; d++ {
66				res = (res + c) % mod
67			}
68		}
69		// 算一下上界
70		maxNum := getMax(limitSum)
71		minNum := getMin(limitSum)
72		for d := minNum; d <= maxNum && d <= int(s[n-1]-'0'); d++ {
73			res = (res + 1) % mod
74		}
75		return res
76	}
77
78	ans := getCount(num2) - getCount(num1) + mod
79	// 判断一下num1是否合法，上面直接减去了num1而不是num1-1，少算了num1
80	sumNum1 := 0
81	for _, c := range num1 {
82		sumNum1 += int(c - '0')
83	}
84	if sumNum1 >= min_sum && sumNum1 <= max_sum {
85		ans++
86	}
87	return ans % mod
88}