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
| 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)
}
|