思路: 数位 dp
函数 f(n)
求 [0, n]
符合题意的整数个数;
那么求 [num1, num2]
就是求 f(num2) - f(num1-1)
代码实现:
class Solution:
def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
MOD = 10 ** 9 + 7
@cache
def dfs(i: int, s: str, is_num: bool, is_limit: bool, sum: int) -> int:
if i == len(s):
return int(sum >= min_sum)
res = 0
if not is_num:
res = dfs(i + 1, s, False, False, 0)
up = int(s[i]) if is_limit else 9
down = 0 if is_num else 1
for d in range(down, up + 1):
if sum + d <= max_sum:
res += dfs(i + 1, s, True, is_limit and up == d, sum + d)
return res
d1 = dfs(0, num2, False, True, 0)
d2 = dfs(0, str(int(num1) - 1), False, True, 0)
# print(d1)
# print(d2)
return (d1 - d2) % MOD