题目特征
要求统计满足一定条件的数的数量（即，最终目的为计数，若要结果则只能回溯爆搜得到）；
这些条件经过转化后可以使用「数位」的思想去理解和判断；
输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
上界很大（比如 10^{18}），暴力枚举验证会超时。
思路
从高到低枚举每一位，统计符合target的个数，并记录到dp数组中。枚举完毕之后则得到答案。
因此数位dp的第一个状态都是数位的位置，第二个状态由题意来定
模板
以leetcode1012为例，统计小于等于n的数字中每一位的数字至少重复一次的个数。
模板时灵神的模板。难点主要是mask，isLimit，isNum这几个标识
- mask即dp的第二个状态，这边用到了状态压缩的思想，将0到9选过的状态压缩成一个数字(否则要10个状态)
- isLimit 标识了本次(i)选择的范围，是否受到n的影响。如果不引进这个变量，则需要考虑当前数字的最高位来决定本次的范围(最高位==n的最高位时，本次的范围是[0,s[i]],最高位<n的最高位时，本次的范围是[0,9])。可以发现这个限制是有传递的性质的，因此引入这个变量能简化范围的选择过程。
- isNum 标识了本次(i)之前是否有数字，换句话说本次(i)是否是第一个数字(最高位)。这个标识主要是解决前导0的问题，否则答案里会重复(前导两个0和前导三个0虽然是同个数字，但都会被记入答案)
func numDupDigitsAtMostN(n int) (ans int) {
s := strconv.Itoa(n) // s[0]是最高位
/* 若需要从低到高的顺序，则按如下生成
for ; n > 0; n = n / 10 {
list = append(list, n%10)
}
*/
m := len(s)
dp := make([][1 << 10]int, m)
// 数位dp的第一个状态都是数位的位置，第二个状态由题意来定
// 问题转换为计算没有重复数字的个数，因此第二个状态记录已经选过数字的集合
// i 表示从高到低第i位， j是前面已经选过的数字的集合,最大为[0,9]的子集个数
// 例如集合 {0,2,3} 对应的二进制数为 1101 （集合的思想就是状压）
for i := range dp {
for j := range dp[i] {
dp[i][j] = -1 // -1 表示没有计算过
}
}
var f func(int, int, bool, bool) int
// mask是dp数组中第二个状态
// isLimit表示当前是否受到n的约束，若为true表示当前位最大填s[i]
// 若isLimit为true时填了s[i],则isLimit为true传递到下一位，下一位也受到n的约束
// isNum主要是处理前导零的问题。isNum表示i前面是否填了数字
// 若isNum为true，则i位可以从0开始填；否则，说明i是第一位，i可以不填，或者至少填1(因为不能有前导0)
f = func(i, mask int, isLimit, isNum bool) (res int) {
if i == m { // base case，遍历完毕
if isNum { // 且不是全部跳过不选的
return 1 // 得到了一个合法数字
}
return
}
if !isLimit && isNum {
dv := &dp[i][mask]
if *dv >= 0 {
return *dv // dp匹配直接返回
}
defer func() { *dv = res }() // 未匹配到，则在return之后更新dp数组
}
if !isNum { // 可以跳过当前数位
res += f(i+1, mask, false, false)
}
d := 0
if !isNum {
d = 1 // 如果前面没有填数字，必须从 1 开始（因为不能有前导零）
}
up := 9
if isLimit {
up = int(s[i] - '0') // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
}
for ; d <= up; d++ { // 枚举要填入的数字 d
if mask>>d&1 == 0 { // d 不在 mask 中
res += f(i+1, mask|1<<d, isLimit && d == up, true) // d写入mask， isLimit传递
} // 否则该分支的结果为0
}
return
}
return n - f(0, 0, true, false)
}