数位DP
leetcode 2376
模板题，用记忆化搜索实现会更加直观，需要知道的信息有：
1. 当前到第几位
2. 已选集合，避免重复
3. 是否到上限，到不到上限在同一位上可选范围是不一样的
4. 是否开始计数（考虑前导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)
leetcode 600
状态位只需要考虑前一位是不是0