LC 2719. 统计整数数目

还没有接触过这种数位 dp 的算法，我看了一下 讲解，大致思路就是：

  1. 将上限数字转变成为字符串
  2. 从第 0 个数字开始匹配
  3. 如果处于受限状态，那么就最多只能到对应数字上，否则就可以到 9
  4. 主要是针对字符串上的每个位置进行枚举

下面是题主给出的模板

  1. i 表示枚举的位置，从开头进行枚举
  2. sum 表示当前所有累计的数字之和
  3. isNum 表示当前是否得到的是有效数字，因为起始我么允许使用"000" 这样的，所有 isNum 开始就是 true. 这个里面可以省略
  4. isLimit 表示前缀是否被锁定
class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:

        def doCount(num):
            s = str(num)
            from functools import cache
            @cache
            def f(i, sum, isNum, isLimit):
                if sum > max_sum:
                    return 0

                if i == len(s):
                    return sum >= min_sum and isNum

                res = 0
                down = 0 if isNum else 1
                up = int(s[i]) if isLimit else 9
                for d in range(down, up + 1):
                    res += f(i + 1, sum + d, True, isLimit and d == up)
                return res

            return f(0, 0, True, True)

        a = doCount(num2)
        b = doCount(num1)
        c = (min_sum <= sum(map(int, num1)) <= max_sum)
        ans = (a - b) + c
        return ans

题主还给了这个题作为学习 https://leetcode.cn/problems/numbers-with-repeated-digits/

这题里面就需要维护一个 mask. 然后这题里面起始不允许出现前缀 0 这样的答案，所以一开始 isNum = false 

class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        s = str(n)

        from functools import cache
        @cache
        def f(i, mask, isNum, isLimit):
            if i == len(s):
                return isNum

            res = 0
            if not isNum:
                res += f(i + 1, mask, False, False)

            down = 0 if isNum else 1
            up = int(s[i]) if isLimit else 9
            for d in range(down, up + 1):
                if not (mask & (1 << d)):
                    res += f(i + 1, mask | (1 << d), True, isLimit and d == up)
            return res

        a = f(0, 0, False, True)
        ans = n - a
        return ans