预计阅读时间：3 分钟

数位DP

数位 DP 是「统计 $[1, n]$ 内满足某性质的数字个数」这类题的专用咏唱，模板一旦焊死，剩下的只是换性质。本合集收录数位 DP 题目。

模板

leetcode 2376

题意：如果一个正整数的各位数字互不相同，就称它为特殊整数；给定正整数 n，统计 $[1, n]$ 中特殊整数的个数。

模板题。用记忆化搜索实现比递推直观得多，状态需要携带四样信息：

1. i：当前填到第几位；
2. mask：已选数字的集合，避免重复选数；
3. is_limit：前面是否一直顶着上界在填——顶着上界时，当前位的可选范围受 n 对应位限制，否则 0 到 9 随便填；
4. is_num：前面是否已经填过非零数字（数字是否已经开始），用来处理前导零。

还没开始填数时，这一位可以继续空着（跳过）；一旦空着，后面就不可能再顶着上界，所以 is_limit 变成 False。开始填的第一位不能是 0。

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        s = str(n)
        @cache
        def dfs(i, mask, is_limit, is_num):
            if i == len(s):
                return int(is_num)
            res = 0
            if not is_num:
                res = dfs(i + 1, mask, False, False)
            lo = 0 if is_num else 1
            hi = int(s[i]) + 1 if is_limit else 10
            for d in range(lo, hi):
                if mask >> d & 1 == 0:
                    res += dfs(i + 1, mask | (1 << d), is_limit and d == int(s[i]), True)
            return res
        return dfs(0, 0, True, False)

@cache 在 LeetCode 环境里已自动导入，本地单独运行需要先写 from functools import cache。

leetcode 600

同一套模板，但有两处要换。第一，题意是统计 $[0, n]$ 中二进制表示不含连续 1 的整数个数，性质定义在被统计的每个数的二进制上，所以要改在上界 n 的二进制串 bin(n)[2:] 上做，每位只能填 0 或 1。第二，集合状态退化了：不需要记完整的 mask，只需要记前一位是否填了 1，前一位是 1 时这一位只能填 0，以此保证不出现连续的 1。另外本题统计范围含 0，前导零也不会造成连续的 1，所以 is_num 可以去掉。

未完待续，本合集随训练进度持续补完。

本文由 aboom 原创，转载请注明出处。