1.三叶的模板

位DP是一种比较抽象和难理解的DP题型,什么时候会用到数位DP去解题?

一般来说,当遇到求 [a,b] 内满足一定条件的数字有多少个时,大概率会用到数位DP

设 f[i] 为 [0,i] 满足条件的数字个数,那么[a, b] 内的符合要求数目就是 f[b]-f[a]

三叶的数位DP方面总结得比较系统,题解也是比较模板化的,建议按照模板来,大致梳理一下模板和思路如下:

将 [0,n] 的数字分为3部分:

1.res1 位数小于n的部分 这部分一般可以通过乘法原理求解

2.res2 位数等于n且最高位小于n部分 这部分也可以用乘法原理进行求解,枚举最高位可用的情形然后利用乘法原理计算

3.res3 位数等于n且最高位等于n部分 这部分是最难的,因为每一位的取值严格被限制了,需要用到DP的思想进行求解

(注意这个res3不一定是n的最高位,是遍历过程中作为状态值动态变化的)

res2与res3一般放在一起求解,套路如下:

高位向低位枚举,假设当前位数字为cur,其中res2部分可以通过乘法原理计算得到

res3部分需要由 当前位的后面位方案数 决定,这里就有了子问题的复现了,原问题与子问题的维度差异就是子问题比原问题少了原来的最高位

以 LC 1012为例

res2 = [0,cur-1]能用的数字数 * 后面剩余位数的排列数

res3相当于固定了当前位为最大值cur,再看后面位总的方案数,通过for循环一直遍历至最后一位(或者是出现重复的一位)

还有一个细节就是别漏了最大数本身也符合要求这种情形

排列数的情形有限,我们可以预处理出来所有排列数来加快计算速度

最后再累加上res1的方案数就是答案

1012. 至少有 1 位重复的数字

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution {
// 预处理排列数 f[i][j]=i*(i+1)*...*(j-1)*j
static int[][] f = new int[11][11];

static {
for (int i = 1; i < 11; i++) {
for (int j = i; j < 11; j++) {
int cur = 1;
for (int k = i; k <= j; k++) {
cur *= k;
}
f[i][j] = cur;
}
}
}

public int numDupDigitsAtMostN(int n) {
/*
数位DP(较难):
本题可以转化为求[1,n]全部数字不相同的数字个数,是典型的数位DP问题
数位DP问题求解的总体思路就是求[0,n]中满足某些条件的数字个数
通常套路就是将[0,n]的数字分为3部分:
1.res1 位数小于n的部分 这部分与 LC357 解法一致,利用乘法原理求解
2.res2 位数等于n的部分且最高位小于n 这部分也可以用乘法原理进行求解,枚举最高位直接计算就可以
3.res3 位数等于n的部分且最高位等于n 这部分是最难的,因为每一位的取值严格被限制了,需要用到DP的思想进行求解
res2与res3一般放在一起求解,套路如下:
从高位向低位枚举,假设当前位为cur,其中res2部分可以通过乘法原理计算得到
res3部分需要由 当前位的后面位方案数 决定
具体的,res2=[0,cur-1]能用的数字数*后面剩余位数的排列数
res3相当于固定了当前位为最大值cur,再看后面位的总的方案数,通过for循环一直遍历至最后一位(或者是出现重复的一位)
排列数的情形有限,我们可以预处理出来加快计算速度
时间复杂度:O(logN) 空间复杂度:O(C)
*/
return n - dp(n) + 1; // 注意排除掉0的情况
}

// dp[x]返回[0,x]中每一位都不同的数字数目
private int dp(int x) {
// 一位数直接返回x+1(因为包含0)
if (x <= 9) return x + 1;
// 将x每一位提出来
List<Integer> list = new ArrayList<>();
while (x != 0) {
list.add(x % 10);
x /= 10;
}
int bitCnt = list.size();
int res = 0;
// 1.计算res1+res2部分
// 其中i为数字x的位索引,i越大表示位数越高(越左)
// p记录当前循环到的位置已经遍历了多少位
// used标记当前遍历过程中已经用了的哪些数字,到时候根据used排除
for (int i = bitCnt - 1, used = 0, p = 1; i >= 0; i--, p++) {
// 首先计算当前位cur能用的数字个数cnt
int cur = list.get(i), cnt = 0;
// 枚举[cur-1,0],再排除掉前面已经用过的
for (int j = cur - 1; j >= 0; j--) {
// 最高位可以用[cur-1,1]
if (i == bitCnt - 1) {
cnt = cur - 1;
break;
}
// 低位可以用[cur-1,0]没用过的任意数
if (((used >> j) & 1) == 0) cnt++;
}
// 计算res2部分
// 合法值 a>=b 其中a为cur后面首位选择数,b为终点(最后一位)的选择数
int a = 10 - p, b = a - (bitCnt - p) + 1;
res += cnt * (i > 0 ? f[b][a] : 1); // 特例为最后一位的时候可以选cnt个
// 已经遇到相同数字,统计完cnt次以后([0,cur-1]的情况)就可以退出
if (((used >> cur) & 1) == 1) break;
if (i == 0) res++; // 当x本身就是合法案例,最后一位加完cnt之后还要再+1
used |= (1 << cur); // 标记使用了cur
}
// 2.计算res3部分(位数小于x的部分)
res += 10; // 先统计一位数的情况
// 统计后面的[2,bitCnt-1]位:9*9 9*9*8 9*9*8*7 ...
for (int i = 2; i < bitCnt; i++) {
res += 9 * f[11 - i][9];
}
return res;
}
}

2.灵佬的模板(推荐)

2376. 统计特殊整数

参考灵神写的记忆化DFS解决数位DP问题的模板,非常好用,几乎可以“秒杀”任何类型的数位DP!

记忆化本质就是减少前面已选状态一致的情况,将1eM的时间复杂度压缩至1<<M,效率非常高

详细参考:数位 DP 通用模板,附题单(Python/Java/C++/Go)

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
59
60
class Solution {
int[][] memo; // memo[i][mask]记录当前选择顺位为i,已选状态为mask时,构造第i位及后面位的合法方案数
char[] s;

public int countSpecialNumbers(int n) {
/*
参考灵神の数位DP记忆化DFS模板:
注意这题与LC1012是一样的,不过这题更直接求每一位都不相同数字
dfs(i, mask, isLimit, hasNum) 代表从左到右选到第i个数字时(i从0开始),前面数字已选状态为mask时的合法方案数
各个参数的含义如下:
i:当前选择的数字位次,从0开始
mask:前面已择数字的状态,是一个10位的二进制数,如:0000000010就代表前面已经选了1
isLimit:boolean类型,代表当前位选择是否被前面位的选择限制了;
如n=1234,前面选了12,选第3位的时候会被限制在0~3,isLimit=true;否则是0~9,isLimit=false
hasNum:表示前面是否已经选择了数字,若选择了就为true(识别直接构造低位的情况)
时间复杂度:O(1024*M*10) 空间复杂度:O(1024*M)
记忆化DFS的时间复杂度=状态数*每一次枚举的情况数
*/
s = String.valueOf(n).toCharArray(); // 转化为字符数组形式
int m = s.length;
memo = new int[m][1 << 10]; // i∈[0,m-1],mask为一个10位二进制数
// 初始化memo为-1代表该顺位下该已选状态还没进行计算
for (int i = 0; i < m; i++) {
Arrays.fill(memo[i], -1);
}
// 注意一开始最高位是有限制的,isLimit=true
return dfs(0, 0, true, false);
}

// dfs(i, mask, isLimit, hasNum) 代表从左到右选第i个数字时,前面已选状态为mask时的合法方案数
private int dfs(int i, int mask, boolean isLimit, boolean hasNum) {
// base case
// i越过最后一位,此时前面选了就算一个,没选的就不算,因为不选后面也没得选了
if (i == s.length) return hasNum ? 1 : 0;
// 已经计算过该状态,并且该状态是有效的,直接返回该状态
// 这一步是降低时间复杂度的关键,使得记忆化dfs的时间复杂度控制得很低
// !isLimit表示没有被限制的才可以直接得出结果,否则还要根据后面的数字进行计算子问题计算
if (!isLimit && hasNum && memo[i][mask] != -1) return memo[i][mask];
int res = 0; // 结果
// 本位可以取0(可直接构造低位数)的情况,此时要加上构造低位数0xxx的方案数
// 将是否选了数字作为分类条件是为了避免出现00010这样有多个0的就不能统计了
if (!hasNum) res = dfs(i + 1, mask, false, false);
// 构造与当前顺位相同位数的数字就要枚举可选的数字进行DFS
// 枚举的起点要视hasNum而定,如果前面选择了数字,那么现在可以选0;否则只能从1开始
// 枚举得终点视isLimit而定,若被限制了只能到s[i],否则可以到9
for (int k = hasNum ? 0 : 1, end = isLimit ? s[i] - '0' : 9; k <= end; k++) {
// 如果该数字k还没有被选中,那猫就可以选该位数字
if (((mask >> k) & 1) == 0) {
// 方案数遵循加法原理
// i:进行下一位的DFS,因此为i+1
// mask:由于该位选中了k,mask掩膜传下去就要更新,已选状态加上k
// isLimit:当且仅当前面的被限制了且该位被限制
// hasNum:该位选了必定为true
res += dfs(i + 1, mask | (1 << k), isLimit && k == end, true);
}
}
if (!isLimit && hasNum) memo[i][mask] = res; // 如果前面没有限制,表明后面都是同质的,可以记录进memo中
return res;
}
}