原题链接:
https://leetcode.cn/problems/count-special-integers/

数位dp 虽然只要是枚举的过程 但需要考虑的情况比较多 且融合非常多的知识点 非常细致
主要需要注意以下几个点：

  1. 枚举过的数 不能再枚举 可以用一个vis数组 但为了方便可以用二进制的方法 采用一个mask 进行解决
  2. 每个位置枚举的数 会受到前一个位置的限制
    1. 比如说 n=123 那么如果 当前已经枚举的情况位 12_ 那么最后一位只能枚举1 2 3 否则就会超过123 那么生成的数 就不符合答案标准了
  3. 如果前一个数位为0 那么当前位置枚举数可能会存在重复
    1. 比如说 9 09 009 则三个数都会出现重复 需要这种特殊情况进行判读那
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        # 先将这个数转换为字符串 便于后续的操作
        s = str(n)

        """
        参数说明:
        i 当前枚举的位数
        mask 当前所枚举过的数 用二进制集合表示
            mask>>d & 1 是否为1  用于判断 d 是否已经枚举过
            mask>>d | 1 将枚举过的这位进行标记
        is_limit 表示前面所填的数字是否为n对应位上的 如果是 那么当前位所填的数字就要受到数n制约 即最大不能超过n在当前位的数字 否则可以直接枚举0-9  
        is_num 表示前面是否填了数字(是否跳过数字0) 
            如果没有填数字0 则跳过当前位置 或者从1开始计数 
            否则(is_num = true) 可以从0开始给
        """

        @cache
        def f(i: int, mask: int, is_limit: bool, is_num: bool)->int:
            # 枚举的位数 已经达到了 n 的位数 直接返回
            if i == len(s):
                # 如果之前已经填过数字 那么即代表已经成功构造出一个有效答案 否则return 0
                return int(is_num)
            res = 0

            # 如果is_num 为false 即之前还没有填过数
            # 这里先选择直接跳过 因为这里还没有进入枚举环节
            if not is_num:
                # 比如 009 如果 他之前的值并没有枚举过 那么这种情况 就会和 09 9 两种情况重复了 所以选择跳过
                # is_limit 之前都没有填过数 那么当然也不可能填 n 对应位上的数 所以仍位false
                # is_num 之前没有填数字 这位跳过了 那么这位自然也没有填数组
                res = f(i + 1, mask, False, False)

            # 进行枚举 先判断上界
            # 如果之前填过 n相应位置上的数 那么 当前的上界也就只能是 n当前位置上的数 否则可以是0-9
            # 比如 n = 123  上一个枚举的数位已经填 12_ 那么该位置上最多只能填到3 否则就超过n 不符合条件了 否则就能填到0-9
            up = int(s[i]) if is_limit else 9

            # 枚举当前位的数
            # 如果之前位上有填过数 那么当前位就可以从 0 开始 否则就应该从1 开始
            start = 1 - int(is_num)
            # range算法 右边是小于号 所以是 up+1
            for d in range(start, up + 1):
                # 如果 d 并没有被枚举过
                if mask >> d & 1 == 0:
                    """
                    i + 1 : 枚举下一位
                    mask | (1 << d) : 将d 标记  
                                      1<<d :  第d位为1 其他位均为0 或运算即可将mask的相应置成1
                    is_limit and d == up: 前面所有位都1取到 n相应位的数 才对当前位有限制 否则当前仍可以去0-9 
                    True: 当前位置填过数了 那么当前位自然位1
                    """
                    res += f(i + 1, mask | (1 << d), is_limit and d == up, True)
            return res
        # 初始位 0  mask中一个数都没有用过 也为0
        # is_limit为一个特判 要加以限制置为True     is_Num没有取过数自然为False
        return f(0, 0, True, False)

上面的写法使用了python 中内置的cache 但由于别的语言没有cache关键字 且正常记忆化搜索 通常会创建一个数据 用作cache 所以这里附上不使用cache 关键字的做法 更具有代表性一些

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
class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        s = str(n)
		# 这里关于python 二维数组的初始化定义一定要注意下 一定要写成这样 
		# 且第一维决定的是列数 二维决定的是行数 这也为数不多我认为python比较麻烦的地方
        dp = [[-1 for _ in range(0,1<<10)] for _ in range(0, len(s))]
        def f(i: int, mask: int, is_limit: bool, is_num: bool) -> int:
            if i == len(s):
                return int(is_num)
            if not is_limit and is_num and dp[i][mask] >= 0:
                return dp[i][mask]
            res = 0
            if not is_num:
                res = f(i + 1, mask, False, False)

            up = int(s[i]) if is_limit else 9

            for d in range(1 - int(is_num), up + 1):
                if mask >> d & 1 == 0:
                    res += f(i + 1, mask | (1 << d), is_limit and d == up, True)

            if not is_limit and is_num:
                dp[i][mask] = res

            return res

        return f(0, 0, True, False)