什么是数位DP
数位dp是与数字相关的一类计数问题。这这类问题中，一般给定一些限制条件，求满足第 \(K\) 小的数是多少，或者求区间 \([L,R]\) 内有多少个满足条件的数。
本文主要讲述如何解决 求区间 \([L,R]\) 内有多少个满足条件的数 这一类问题。
为什么要用数位dp
对于上述问题，如果只使用简单的暴力，时间复杂度为 \(O(n+?)\) 枚举的时间复杂度 + 验证的时间复杂度。
如果采用 \(dfs\) 枚举每一位的方法。则可以通过题目已有条件，进行一部分的剪枝。代码如下
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int num[N];
int dfs(int len, bool limit, bool lead, /*一些参数记录是否符合条件*/) {
//limit表示当前的最高数是否有限制 lead表示前导0
if(len == 0) return sum;
int ans = 0;
int maxx = limit ? num[len]:9;
for (int i = 0; i <= maxx; i++) {
ans += dfs(len-1, limit&&(i==maxx), lead||i, /*一些参数*/);
}
return ans;
}
int work(int x, int i) {
int len = 0;
while (x) {
num[++len] = x%10;
x /= 10;
}
memset(f, -1, sizeof(f));
return dfs(len, 1, 0, i, 0);
}
int main() {
int a, b;
scanf("%d %d", &a, &b);
for (int i = 0; i <= 9; i++) {
printf("%d ", work(b, i) - work(a-1, i));
}
return 0;
}
详解 \(limit\) 和 \(lead\)
\(limit\) 记录当前枚举到当前数位，是否有最高位限制。对于每个数位的最大数不一定为 \(9\) 。举个荔枝 对于区间 \([5,114514]\) ，我们枚举到 \(1?????\) 显然当前数位枚举的最大数不应该为 \(9\) ，要不然我们枚举出的数就会超过区间限制。
\(lead\) 记录当前数位的前一位是否为前导 \(0\) ， 这一项的记录有时候并不是必要的。你需要根据题目来设计你的状态。
可这样时间复杂度仍旧不尽人意。
怎么用数位dp
我们观察到，有很多等价的状态被重复遍历。举个例子 \(114???\) ，和 \(124???\) 两个状态（在他们没有最大数限制的情况下），枚举接下来数位数字的状态树一定是相同的。那还有必要在重复枚举两个相同的子树吗？答案是显然的。所以我们可以通过记忆化来避免多次遍历相同的 \(dfs\) 子树。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int a, b;
int num[N],f[N][N];
int dfs(int len, bool limit, bool lead, /*一些参数记录是否符合条件*/) {
if(len == 0) {
if(!lead) return 0;
return 1;
}
if(!limit&& /*根据题目自定参数*/) return f[][];
int ans = 0;
int maxx = limit ? num[len]:9;
for (int i = 0; i <= maxx; i++) {
ans += dfs(len-1, limit&&(maxx==i), lead||i, /*一些参数记录是否符合条件*/);
}
if(!limit&&lead) f[len][last] = ans;
return ans;
}
int solve(int x) {
memset(f, -1, sizeof(f));
int len = 0;
while (x) {
num[++len] = x%10;
x /= 10;
}
if(len==0) return 0;
return dfs(len, 1, 0, -2);
}
int main() {
scanf("%d %d", &a, &b);
printf("%d", solve(b)-solve(a-1));
return 0;
}