title
给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数：
num1 <= x <= num2min_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 <= 10221 <= min_sum <= max_sum <= 400
solution
数位DP, 套用模板即可。is_num其实可省略，因为前导零对数位和无影响（数位和加上 0 不变）
class Solution:
def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
MOD = int(1e9 + 7)
import functools
@functools.lru_cache(None)
def f(i: int, leftsum: int, is_limit: bool, is_num: bool, s: str):
if i == len(s):
# print(leftsum)
# 最后一位了，合法则return 1
if leftsum >= min_sum:
return int(is_num)
return 0
res = 0
if not is_num:
# 此时已经有前缀0了，因此不受限
res += f(i + 1, leftsum, False, False, s)
res %= MOD
# 数位i的上限
up = int(s[i]) if is_limit else 9
# 如果是is_num, 则可以从0开始，否则只能从1开始，毕竟是第一位数字
for d in range(1 - int(is_num), up + 1):
if d + leftsum > max_sum: break
# 没用过该数字
res += f(i + 1, leftsum + d, is_limit and d == up, True, s)
res %= MOD
return res % MOD
b = f(0, 0, True, False, num2)
b %= MOD
# print(b)
a = f(0, 0, True, False, str(int(num1) - 1))
b %= MOD
# print(a)
return (b - a + MOD)%MOD