leetcode：6151. 统计特殊整数【数位dp模板】

分析

求符合要求的数字，使用数位dp
i：表示当前位
mask：表示之前选受到的约束
is_limit：表示是否受到n的大小的约束（决定上界）
is_num：表示是否选，即是否有前导0（决定下界）
cache记忆化搜索
退出条件达到长度，如果有选的话返回1即可

模板ac code

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        # 数字的关系：数位dp
        s = str(n)

        # i：从高到低第i位
        # mask：前面的限制
        # is_limit：是否受到n当前位的限制
        # is_num：前面有没有选（不选默认前导0）
        # is_limit 和 is_num锁定上下界限
        # 如果is_limit是True, 只能选到int(s[i])，否则可以选到9
        # 如果is_num是True，可以从0开始选，否则只能从1开始选
        @cache
        def f(i, mask, is_limit, is_num):
            # 到达最后一位，如果是num就可以算一个
            if i == len(s):
                return int(is_num)
            res = 0
            # 如果之前没有选，现在也可以不选
            if not is_num:
                # 现在不选就肯定没有限制
                res += f(i + 1, mask, False, False)
            # 如果之前选了，现在也只能选
            # 确定上下界
            down = 0 if is_num else 1
            up = int(s[i]) if is_limit else 9
            for d in range(down, up + 1):
                # 如果d之前不在mask中
                if (mask >> d) & 1 == 0:
                    res += f(i + 1, mask | (1 << d), is_limit and d == up, True)
            return res

        return f(0, 0, True, False)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

总结

关于数字符合某些规律的考虑数位dp
复杂度：状态个数 * 转移个数 (len(n) * 1024 * 10)
附：力扣上的数位 DP 题目

233. 数字 1 的个数
面试题 17.06. 2出现的次数
600. 不含连续1的非负整数
902. 最大为 N 的数字组合
1012. 至少有 1 位重复的数字
1067. 范围内的数字计数
1397. 找到所有好字符串（可选，需要结合一个知名字符串算法）
1
2
3
4
5
6
7