由于算法提高课的数位 DP 的非搜索做法比较难想,所以总结一下数位 DP 的 DFS 写法。
数位 DP 问题一般给定一个区间 $[L,R]$,问区间满足的条件的数有多少个。
可以利用前缀和来求解答案:$\sum \limits _{i=1}^{R} ans_i - \sum \limits_{i=1}^{L - 1} ans_i$
模板:
int dfs(int pos, int pre, int lead, int limit) {
if (!pos) {
边界条件
}
if (!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];
int res = 0, up = limit ? a[pos] : 无限制位;
for (int i = 0; i <= up; i ++) {
if (不合法条件) continue;
res += dfs(pos - 1, 未定参数, lead && !i, limit && i == up);
}
return limit ? res : (lead ? res : dp[pos][sum] = res);
}
int cal(int x) {
memset(dp, -1, sizeof dp);
len = 0;
while (x) a[++ len] = x % 进制, x /= 进制;
return dfs(len, 未定参数, 1, 1);
}
signed main() {
cin >> l >> r;
cout << cal(r) - cal(l - 1) << endl;
}
$\text{cal}$函数(一般情况):
注意每次初始化 DP 数组为 $-1$,长度 $len=0$
基本参数:
$len:$ 数位长度,一般根据这个来确定数组范围
$a_i:$ 每个数位具体数字
返回值 $\text{return}$ 根据题目的初始条件来确定前导 $0$ 以及 $pre$
DFS 函数(一般情况):
变量 $res$ 来记录答案,初始化一般为 $0$
变量 $up$ 表示能枚举的最高位数
采用记忆化搜索的方式:
if (!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];
只有无限制、无前导零才算,不然都是未搜索完的情况。
return limit ? res : dp[pos][pre] = res;
如果最后还有限制,那么返回
res
,否则返回dp[pos][pre]
基本参数:
假设数字 $x$ 位数为 $a_1\cdots a_n$
必填参数:
$pos:$ 表示数字的位数
从末位或第一位开始,要根据题目的数字构造性质来选择顺序,一般选择从 $a_1$ 到 $a_n$ 的顺序。初始从 $len$ 开始的话,边界条件应该是 $pos = 0$,限制位数应该是 $a_{pos}$,DFS 时 $pos-1$;初始从$1$开始的话,边界条件应该是 $pos > len$,限制位数应该是 $a_{len - pos + 1}$,DFS 时 $pos+1$。两种都可以,看个人习惯。
$limit:$ 可以填数的限制(无限制的话 $(limit=0)$ $0\sim 9$ 随便填,否则只能填到 $a_i$)
如果搜索到 $a_1\cdots a_{pos} \cdots a_n$,原数位为 $a_1\cdots a_k \cdots a_n$,那么我们必须对接下来搜索的数加以限制,也就是不能超过区间右端点 $R$,所以要引入 $limit$ 这个参数,如果 $limit=1$,那么最高位数 $up \le a_{pos+1}$,如果没有限制,那么 $up=9$(十进制下)这也就是确定搜索位数上界的语句
limit ? a[pos] : 9;
如果 $limit=1$ 且已经取到了能取到的最高位时 $(a_{pos}=a_k)$,那么下一个 $limit=1$
如果 $limit=1$ 且没有取到能取到的最高位时 $(a_{pos} < a_k)$,那么下一个 $limit=0$
如果 $limit=0$,那么下一个 $limit=0$,因为前一位没有限制后一位必定没有限制。
所以我们可以把这 $3$ 种情况合成一个语句进行下一次搜索:limit && i == up
$(i$为当前枚举的数字$)$
可选参数:
$pre:$ 表示上一个数是多少
有些题目会用到前面的数
$lead:$ 前导零是否存在,$lead=1$ 存在前导零,否则不存在。
一般来说有些题目不加限制前导零会影响数字结构,所以 $lead$ 是一个很重要的参数。
如果 $lead=1$ 且当前位为 $0$,那么说明当前位是前导 $0$,继续搜索 $pos+1$,其他条件不变。
如果 $lead=1$ 且当前位不为 $0$,那么说明当前位是最高位,继续搜索 $pos+1$,条件变动。
如果 $lead=0$,则不需要操作。
$sum:$ 搜索到当前所有数字之和
有些题目会出现数字之和的条件
$cnt:$ 某个数字出现的次数
有些题目会出现某个数字出现次数的条件
参数基本的差不多这些,有些较难题目会用到更多方法或改变$\text{DP}$状态
题目1:不要62
题意: 找到区间 $[L,R]$ 不能出现 $4$ 和 $62$ 的数的个数
分析: 首先此题不需要 $lead$,其次有 $62$ 所以要记前驱 $pre$
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int l, r, dp[N][N], len, a[N];
int dfs(int pos, int pre, int limit) {
if (!pos) return 1;
if (!limit && dp[pos][pre] != -1) return dp[pos][pre];
int res = 0, up = limit ? a[pos] : 9;
for (int i = 0; i <= up; i ++) {
if (i == 4 || (i == 2 && pre == 6)) continue;
res += dfs(pos - 1, i, limit && i == up);
}
return limit ? res : dp[pos][pre] = res;
}
int cal(int x) {
memset(dp, -1, sizeof dp);
len = 0;
while (x) a[++ len] = x % 10, x /= 10;
return dfs(len, 0, 1);
}
signed main() {
while (cin >> l >> r, l || r) {
cout << cal(r) - cal(l - 1) << endl;
}
}
题目2:windy数
题意: 找到区间 $[L,R]$ 相邻数字之差至少为 $2$ 的数的个数
分析: 搜索初始条件第二个参数 $pre$ 必须填一个 $\le -2$ 的数来保证可以搜索下去,不然会出错。此题需要记录前导零,不然忽视前导零的影响会造成最高位数 $-0<2$ 无法继续搜索的情况。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int l, r, a[N], len, dp[N][N];
int dfs(int pos, int pre, int lead, int limit) {
if (!pos) return 1;
if (!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];
int res = 0, up = limit ? a[pos] : 9;
for (int i = 0; i <= up; i ++) {
if (abs(pre - i) < 2) continue;
if (lead && !i) {
res += dfs(pos - 1, -2, lead && !i, limit && i == up);
} else {
res += dfs(pos - 1, i, lead && !i, limit && i == up);
}
}
return limit ? res : (lead ? res : dp[pos][pre] = res);
}
int cal(int x) {
memset(dp, -1, sizeof dp);
len = 0;
while (x) a[++ len] = x % 10, x /= 10;
return dfs(len, -2, 1, 1);
}
signed main() {
cin >> l >> r;
cout << cal(r) - cal(l - 1) << endl;
}
题目3:数字游戏
题意: 找到区间 $[L,R]$ 各位数字非严格单调递增的数的个数
分析: 前导零不影响,所以不需要 $lead$。所以只需要判断枚举的位数是不是非严格递增来判断是否继续搜索。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int l, r, a[N], len, dp[N][N];
int dfs(int pos, int pre, int limit) {
if (!pos) return 1;
if (!limit && dp[pos][pre] != -1) return dp[pos][pre];
int res = 0, up = limit ? a[pos] : 9;
for (int i = 0; i <= up; i ++) {
if (i < pre) continue;
res += dfs(pos - 1, i, limit && i == up);
}
return limit ? res : dp[pos][pre] = res;
}
int cal(int x) {
memset(dp, -1, sizeof dp);
len = 0;
while (x) a[++ len] = x % 10, x /= 10;
return dfs(len, 0, 1);
}
signed main() {
while (cin >> l >> r) {
cout << cal(r) - cal(l - 1) << endl;
}
}
题目4:数字游戏Ⅱ
题意: 找到区间 $[L,R]$ 各位数字之和 $\mod n=0$ 的数的个数
分析: 前导零不影响,所以不需要 $lead$。此题涉及到数字和 ,所以要用到 $sum$,不需要记录前驱 $pre$,所以 $\text{dp}$ 状态变为了 $\text{dp}[pos][sum]$。边界条件为 $sum \bmod n=0$,返回 $1$,否则返回 $0$
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int l, r, p, len, a[N], dp[N][N];
int dfs(int pos, int sum, int limit) {
if (!pos) return sum % p == 0;
if (!limit && dp[pos][sum] != -1) return dp[pos][sum];
int res = 0, up = limit ? a[pos] : 9;
for (int i = 0; i <= up; i ++) {
res += dfs(pos - 1, sum + i, limit && i == up);
}
return limit ? res : dp[pos][sum] = res;
}
int cal(int x) {
memset(dp, -1, sizeof dp);
len = 0;
while (x) a[++ len] = x % 10, x /= 10;
return dfs(len, 0, 1);
}
signed main() {
while (cin >> l >> r >> p) {
cout << cal(r) - cal(l - 1) << endl;
}
}
题目5:度的数量
题意: 找到区间$[L,R]$恰好为$K$个$B$的幂次方之和的数的个数
分析: 前导零不影响,所以不需要$lead$。因为要记录数量,所以要增加变量$cnt$。前驱$pre$不需要记录。判断边界时只要最后数量$cnt=k$,返回$1$,否则返回$0$。同时枚举数字时如果前面系数不为$1$或者没搜索完就已经$K$个了,那么就continue
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int l, r, k, b, a[N], len, dp[N][N];
int dfs(int pos, int cnt, int limit) {
if (!pos) return cnt == k;
if (!limit && dp[pos][cnt] != -1) return dp[pos][cnt];
int res = 0, up = limit ? a[pos] : b - 1;
for (int i = 0; i <= up; i ++) {
if ((i == 1 && cnt == k) || i > 1) continue;
res += dfs(pos - 1, cnt + (i == 1), limit && i == up);
}
return limit ? res : dp[pos][cnt] = res;
}
int cal(int x) {
memset(dp, -1, sizeof dp);
len = 0;
while (x) a[++ len] = x % b, x /= b;
return dfs(len, 0, 1);
}
signed main() {
cin >> l >> r >> k >> b;
cout << cal(r) - cal(l - 1) << endl;
}
题目6:计数问题
题意: 统计区间$[L,R]$出现$0123456789$的各个数字总次数
分析: 需要用到$lead$,需要用到次数总和$sum$,还有哪个数字$num$。基本上可以套模板,注意边界条件。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int l, r, len, a[N], dp[N][N];
int dfs(int pos, int sum, int num, int lead, int limit) {
if (!pos) {
if (lead && !num) return 1;
return sum;
}
if (!limit && !lead && dp[pos][sum] != -1) return dp[pos][sum];
int res = 0, up = limit ? a[pos] : 9;
for (int i = 0; i <= up; i ++) {
int t;
if (i == num) {
if (!num) {
t = sum + (lead == 0);
} else {
t = sum + 1;
}
} else {
t = sum;
}
res += dfs(pos - 1, t, num, lead && i == 0, limit && i == up);
}
return limit ? res : (lead ? res : dp[pos][sum] = res);
}
int cal(int x, int num) {
memset(dp, -1, sizeof dp);
len = 0;
while (x) a[++ len] = x % 10, x /= 10;
return dfs(len, 0, num, 1, 1);
}
signed main() {
while (cin >> l >> r, l || r) {
if (l > r) swap(l, r);
for (int i = 0; i <= 9; i ++) cout << cal(r, i) - cal(l - 1, i) << " ";
cout << endl;
}
}
以上只是模板题用来熟悉数位$\text{DP}$,当然做这些题还远远不够,需要更多练习。
题单:
找到区间$[L,R]$有不超过$3$个非$0$的数的个数
找到区间$[L,R]$各位数字之和能整除原数的数的个数
设 $\text{sum}(i)$ 表示 $i$ 的二进制表示中 $1$ 的个数。给出一个正整数 $N$ ,求 $\prod _{i=1}^{N}\text{sum}(i)$
较难:
HDU 3693 Math teacher’s homework
%%%TQL
不及彩色铅笔大佬
前排!!!!
这里的DP怎么理解?仅仅在无限制下才的准确的等于res的值?
是不取到limit或前导0下的准确值
见鬼,你们都理解DP数组吗
这是我的理解:在limit情况下,后续每一位的最大值是受到限制的,并且limit只需要跑一次递归不需要记忆化。
dp数组感觉只有第一维是表示下标,其他要根据题目来调整。
对不起,我瞎了,我之前没看见DP数组那一段
不,不是这样,你可以看洛谷日报的,这个时候不是不需要记忆化,而是记忆化重合了,会错
一个数字表示一个状态
佬,睡前好好研究一下~
woc这tm,比y总写法好很多啊。。。
从最高位往下依次枚举的时候,你当前位就是你枚举的最高位,如果你当前位上是0并且前面还有0,那么你当前位就是前导0,如果你前面比你高的位次不是0那么无论你是不是0都不是前导0,所以我感觉这里的最高位应该要理解成你枚举时他就是最高位
or2
爱你么么😘
问问大佬 pos == 0 为什么return 1
%%% 太强了
可选参数lead的位置是不是写的有一点错误啊,我看你那里写的是pos+1,但是下面windy数的时候又写了pos-1
dp 不一定要每次 calc 都重新初始化
%%%
跪了%%%
有个疑问,为什么返回的时候要看limit是否为真 return limit ? res : dp[pos][pre] = res; 试了一下好像 直接写成
return dp[pos][pre]也是可以过的
希望来个大佬解释一下
你也可以这么些
问下大佬,为啥
return limit ? res : dp[pos][pre] = res;
这行代码不是写成return limit ? res : dp[pos][pre];
(不是说否则返回dp[pos][pre]吗)dp [pos][res]不是等于-1 吗,不等于-1 一开始不就跳出去了吗
对对,是的诶,人傻了hh
可是dp[pos][pre] = res,不也还是返回res吗,把dp = res, 不管limit = 0 or 1, 返回的都是res把
可是dp[pos][pre] = res,不也还是返回res吗,把dp = res, 不管limit = 0 or 1, 返回的都是res把
%%%%%%%%
单方面宣布为全网最强数位dp解析!!!
明明DFS更好写,为啥y总用递推讲呢
写的太好了,$limit$ 的解释那一行 $limit=1$ 是不是要写成 $limit=0$?
另外推荐两篇文章,也都讲的很详细
【洛谷日报#84】数字组成的奥妙——数位dp
数位dp总结 之 从入门到模板
我觉得也是
最强数位板子