2719.统计整数数目

链接：2719.统计整数数目
难度：Hard
标签：数学、字符串、动态规划
简介：请你返回好整数的数目。

题解 1 - python

• 编辑时间：2024-01-16
• 执行用时：232ms
• 内存消耗：18.31MB
• 编程语言：python
• 解法介绍：数位dp。

def digit_dp(n: int, min_num: str, max_num: str, min_sum: int, max_sum: int):
    @cache
    def dfs(i: int, val: int, limit_low: bool, limit_high: bool) -> int:
        if val > max_sum: return 0
        if i == n: return val >= min_sum
        lo = int(min_num[i]) if limit_low else 0
        hi = int(max_num[i]) if limit_high else 9
        return sum(
            dfs(i + 1, val + d, limit_low and lo == d, limit_high and hi == d)
            for d in range(lo, hi + 1)
        )
    return  dfs
    
class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        dfs = digit_dp(len(num2), num1.zfill(len(num2)), num2, min_sum, max_sum)
        return dfs(0, 0, True, True) % (10 ** 9 + 7)