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 位重复的数字
class Solution {
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) {
return n - dp(n) + 1;
}
private int dp(int x) {
if (x <= 9) return x + 1;
List<Integer> list = new ArrayList<>();
while (x != 0) {
list.add(x % 10);
x /= 10;
}
int bitCnt = list.size();
int res = 0;
for (int i = bitCnt - 1, used = 0, p = 1; i >= 0; i--, p++) {
int cur = list.get(i), cnt = 0;
for (int j = cur - 1; j >= 0; j--) {
if (i == bitCnt - 1) {
cnt = cur - 1;
break;
}
if (((used >> j) & 1) == 0) cnt++;
}
int a = 10 - p, b = a - (bitCnt - p) + 1;
res += cnt * (i > 0 ? f[b][a] : 1);
if (((used >> cur) & 1) == 1) break;
if (i == 0) res++;
used |= (1 << cur);
}
res += 10;
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）
class Solution {
int[][] memo;
char[] s;
public int countSpecialNumbers(int n) {
s = String.valueOf(n).toCharArray();
int m = s.length;
memo = new int[m][1 << 10];
for (int i = 0; i < m; i++) {
Arrays.fill(memo[i], -1);
}
return dfs(0, 0, true, false);
}
private int dfs(int i, int mask, boolean isLimit, boolean hasNum) {
if (i == s.length) return hasNum ? 1 : 0;
if (!isLimit && hasNum && memo[i][mask] != -1) return memo[i][mask];
int res = 0;
if (!hasNum) res = dfs(i + 1, mask, false, false);
for (int k = hasNum ? 0 : 1, end = isLimit ? s[i] - '0' : 9; k <= end; k++) {
if (((mask >> k) & 1) == 0) {
res += dfs(i + 1, mask | (1 << k), isLimit && k == end, true);
}
}
if (!isLimit && hasNum) memo[i][mask] = res;
return res;
}
}
|
