预计阅读时间：2 分钟
数位DP
数位 DP 是「统计 $[1, n]$ 内满足某性质的数字个数」这类题的专用咏唱，模板一旦焊死，剩下的只是换性质。本合集收录数位 DP 题目。
模板
leetcode 2376
模板题。用记忆化搜索实现比递推直观得多，状态需要携带四样信息：
i：当前填到第几位；mask：已选数字的集合，避免重复选数；is_limit：前面是否一直顶着上界在填——顶着上界时，当前位的可选范围受 n 对应位限制，否则 0 到 9 随便填；is_num：是否已经开始计数，用来处理前导零。
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
同一套模板，只是集合状态退化了：不需要记完整的 mask，只需要记前一位填的是不是 0，用它保证不出现连续的 1。
未完待续，本合集随训练进度持续补完。
本文由 aboom 原创，转载请注明出处。