数位DP
数位：把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制。
数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：
- 要求统计满足一定条件的数的数量（即，最终目的为计数）；
- 这些条件经过转化后可以使用「数位」的思想去理解和判断；
- 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
- 上界很大（比如 ），暴力枚举验证会超时。
比如统计[a,b] 之间的满足某个条件的数，这个b可能是1e15这样。 注定无法枚举。此类就可以数位DP， 然后a到b形式也可以变成f(b) -f(a)差分来统一处理。记得a这个本身单个可能要额外减去。
模板
- 记忆化搜索
- 关键参数: 数位i, 用过数字mask, is_limit是否是受限，is_num前面是否填了数字.后面两个参数可适用于其它数位 DP 题目。
该模板对应视频
题目: 2376. 统计特殊整数
如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个 正 整数
n，请你返回区间[1, n]之间特殊整数的数目。
class Solution:
def countSpecialNumbers(self, n: int) -> int:
# 数位dp
import functools
'''
记忆化搜索，i表示计算数位i, mark表示用过的数字
返回从数位i开始填数字，前面填数字的集合为mask, 能构造出整数的数量
is_limit表示是否前i-1位是s对应位上的，即最大受限值max了，如果是则当前数字上线是s[i]，而不是'9'
is_num表示前面是否填了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为
1；若为真，则要填入的数字可以从 0 开始。
s表示上限的字符串,恒定不变。比如"13413431431414"
'''
@functools.lru_cache(None)
def f(i: int, mask: int, is_limit: bool, is_num: bool, upper_s: str):
if i == len(upper_s):
# 最后一位了，合法则return 1
return int(is_num)
res = 0
#数位i的下限
low = 0
# 数位i的上限
up = int(upper_s[i]) if is_limit else 9
# When is_num is False: 还没前缀，单独统计
if not is_num:
# 此时已经有前缀0了，因此不受限
res += f(i + 1, mask, False, False, upper_s)
# 如果是is_num, 则可以从0开始，否则只能从1开始，毕竟是第一位数字。 此时下限只能从1开始
low = 1
for d in range(low, up + 1):
if (mask >> d) & 1 == 0:
# 没用过该数字
res += f(i + 1, mask | (1 << d), is_limit and d == up, True, upper_s)
return res
# 最开始一定是受限的，因此is_limit = True
return f(0, 0, True, False, str(n))
如果是统计[a,b]的。则可以
b = f(0, 0, True, False, num2)
a = f(0, 0, True, False, str(int(num1) - 1))
return b - a
由于每个状态只会计算一次，因此动态规划的时间复杂度 == 状态个数 ×× 单个状态的计算时间。
时间复杂度为 函数内部复杂度(基本不超过10 毕竟枚举0-9) * 数位数量* mask枚举数量 * 2 * 2. 后面两个是is_limit和is_num，常数可忽略
这里字符串长度为O(logn)， log的base为10.
应用
902. 最大为 N 的数字组合 求1-N的使用了digits里数字的数量，没有0， f(i: int, is_limit: bool, is_num: bool)
233. 数字 1 的个数 给定一个整数
n，计算所有小于等于n的非负整数中数字1出现的个数。def f(i: int, ones: int, is_limit: bool, is_num: bool): ones是当前已用ones的数量。面试题 17.06. 2出现的次数 和数字1的个数类似。
600. 不含连续1的非负整数 给定一个正整数
n，返回范围在[0, n]都非负整数中，其二进制表示不包含 连续的 1 的个数。def f(i: int, last_is_one: bool, is_limit: bool)1012. 至少有 1 位重复的数字 等价为n-完全不重复个数
给你两个长度为 n 的字符串 s1 和 s2 ，以及一个字符串 evil 。请你返回 好字符串 的数目。好字符串 的定义为：它的长度为 n ，字典序大于等于 s1 ，字典序小于等于 s2 ，且不包含 evil 为子字符串。 难点在于要动态维护kmp，先求evil的next数组，然后把匹配j当dp参数传递下去。
参考
https://leetcode.cn/problems/count-special-integers/solution/shu-wei-dp-mo-ban-by-endlesscheng-xtgx/