题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution:
def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
mod=10**9+7
def calc(s:str)->int:
@cache
def dfs(i:int,cnt:int,limit:int,num:int)->int:
if len(s)==i:
return min_sum<=cnt<=max_sum
res=0
if not num:
res=dfs(i+1,0,0,0)
low=0 if num else 1
up=int(s[i]) if limit else 9
for d in range(low,up+1):
res+=dfs(i+1,cnt+d,limit and d==up,1)
return res
return dfs(0,0,1,0)
num1=int(num1)-1
return (calc(num2)-calc(str(num1)))%mod
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla