数位dp题集汇总
前置芝士
「数位 DP」属于会就不难，不会就巨难！！本篇文章就来好好详细的总结一下「数位 DP」吧吧吧！！
相信各位小伙伴在学习数位dp过程中，都会感到特别难。但其实数位dp是很简单的，都是有套路的，都可以使用记忆化搜索来求解。在记忆化搜索中，可以使用变量limit来表示是否有限制，而且有限制的一般都是最右侧的那一种分支。对于前导0问题，使用变量lead来表示是否有前导0，一般都是最左侧的那一种分支。从高位枚举到低位，使用变量pos来记录当前枚举到哪一位。
一般使用记忆化搜索的代码：dfs(int pos, bool lead, bool limit)
具体问题具体分析，将需要定义的变量加入到dfs中，lead不是必须的，但是pos和limit都是必要的。
通过前三道题，你就可以大体摸清楚数位dp的套路了，代码模板几乎不变。下面的这些题目就是笔者做过的数位dp习题集，请读者认真阅读，放心食用，从此不怕数位dp的题目。
本文参考博客：传送门
AcWing1085 不要62
题目描述
AcWing1085 不要62
算法思路
记忆化递归在求解时把中间结果记录下来，若某一项的值已经有解，则直接返回，不需要重新计算，从而大大减少计算量。记忆化递归和动态规划（查表法）有异曲同工之妙。
本题考虑另一种枚举方式，从最高位开始往下枚举，在必要时控制上界。
例如，枚举[0, 386]区间的所有数时，首先从百位开始枚举，百位可能是0、1、2、3。枚举时不超过386即可。
百位0： 十位可以是0～9，个位也可以是0～9，枚举没有限制， 因为百位是0时，后面的位数无论是多少，都不可能超过386，相当于枚举000～099。百位1： 十位可以是0～9，个位也可以是0～9，枚举没有限制，枚举100~199。百位2： 十位可以是0～9，个位也可以是0～9，枚举没有限制，枚举200~299。百位3： 十位只可以是0～8，否则超过386，此时是有上界限制的。当十位是0～7时，个位可以是0~9，因为379还是不会超过386。但当十位是8时，个位只可以是0～6，此时有上界限制，相当于枚举300～379、380～386。
我们需要关注以下几个问题。
记忆化。枚举[0, 386]区间的所有数，当百位是0～2时，十位和个位枚举没有限制，都是一样的，采用记忆化递归，只需计算一次并将结果存储起来，下次判断若已赋值，则直接返回该值即可。百位是3时，十位限制在0～8；十位是0～7时，个位无限制；十位是8时，个位限制在0～6。有限制时，不可以采用记忆化递归，需要继续根据限制枚举。上界限制。当高位枚举刚好达到上界时，紧接着的下一位枚举就有上界限制了。可以设置一个变量limit来控制上界限制。高位枚举0。为什么高位需要枚举0？这是因为百位枚举0相当于此时枚举的这个数最多是两位数（即0xx这种显然是两位数），若十位继续枚举0，则枚举的是一位数（即00x这种显然是一位数）。枚举小于或等于386的数，一位数、两位数当然也比它小，所以高位要枚举0。前导0。有时会有前导0的问题，可以设置一个lead变量表示有前导0。例如统计数字里面0出现的次数。若有前导0，例如008，数字8不包含0，则不应该统计8前面的两个0。若没有前导0，例如108，则应该统计8前面的1个0。
记忆化搜索： 若没有限制且已求解，则直接返回，无须递归。采用记忆化递归方法求解时的算法设计如下。
状态表示
f
[
p
o
s
[
s
t
a
]
f[pos[sta]
f[pos[sta]表示当前第pos位在sta状态满足条件的元素个数，sta表示前一位是否是6，只有0和1两种状态。
状态转移方程
if (sta && i == 2) continue;
if (i == 4 ) continue;
ans += dfs(pos - 1, i == 6, limit && i == up);
边界条件
若pos=0，则返回1。
在初始化时，一般limit都初始化为true，表示有限制，sta初始化为false。
示例1： 计算[0, 24]区间不包含4也不包含62的数有多少个，过程如下。
数字分解：nums[1]=4，nums[2]=2。从高位开始，当前位是2，前面一位不是6，有限制up=nums[2]=2，枚举i=0…2，递归求解。
i=0：以0开头的一位数，无限制，up=9，枚举i =0…9，包含00 ～09，除去04，
f
[
1
]
[
0
]
=
9
f[1][0]=9
f[1][0]=9i=1：以1开头的一位数，无限制且
f
[
1
]
[
0
]
f[1][0]
f[1][0]已赋值，直接返回 9。i=2：以2开头的一位数，有限制，up=num[1]=4，执行i=0…4，包含20～24，除去24，共有4个数满足条件。 累加结果，返回[0, 24]区间不包含4也不包含62的22个数， 求解过程如下图所示。
示例2：请尝试计算[0, 386]区间不包含4也不包含62的数有多少个？
图中无填充色的节点均已有解，直接读取结果，无须再递归求解， 这正是记忆化递归的妙处。这种方式大大提高了算法效率。
算法实现
#include
#include
#include
using namespace std;
// nums存储数位
int nums[10], f[10][2];
// f[pos][sta]表示枚举到第pos位，它前面一个位的状态用sta表示，如果前面一个位是6，则sta为true
// limit表示是否有限制 true表示有限制 比如386 那么对于3xx这种就肯定有限制
int dfs(int pos, bool sta, bool limit)
{
// pos为0表示枚举完了所有数位 这里返回答案1（该返回0还是返回1，根据测试结果来决定）
if (!pos) return 1;
// 当前位没有限制 并且 以及被计算过了 那么直接返回答案
if (!limit && ~f[pos][sta] ) return f[pos][sta];
// limit为true 表明存在限制该位只能等于0~nums[pos] 否则该位可以等于0~9；
int up = limit ? nums[pos] : 9, ans = 0;
// 有up个分支，可以填的数是0~up
for (int i = 0; i <= up; i ++ )
{
// 前面一个位是6且当前位是2 不符合题意
if (sta && i == 2) continue;
// 数字4不符合题意
if (i == 4 ) continue;
// 当前这位数字满足条件继续向下搜索
// 通过 i==6来更新sta的状态
// 只有最右侧的分支才会有限制 因此可以通过limit && i == up来更新limit的值
ans += dfs(pos - 1, i == 6, limit && i == up);
}
// 如果没有限制 那么记录一下f[pos][sta]的答案
// 如果有限制 那么不能直接记录答案 因为它会把之前 没有限制时得到的答案覆盖掉
if (!limit ) f[pos][sta] = ans;
return ans;
}
// 求解[0,x]区间内满足条件的个数
int solve(int x)
{
memset(f, -1, sizeof f);
int n = 0;
while (x) // 数位分解
{
nums[ ++ n] = x % 10;
x /= 10;
}
return dfs(n, false, true); // 若不包括0，则此处再减去1即可
}
int main()
{
int l, r;
while (cin >> l >> r, l || r) {
cout << solve(r) - solve(l - 1) << endl;
}
return 0;
}
hdu3355 定时炸弹
题目描述
hdu3355 定时炸弹
题意：求解[1,x]中49的出现次数。
比如[1,500]区间包括“49”的数是49、149、249、349、449、 490、491、492、493、494、495、496、497、498、499，所以答案是15。
算法思路
这题可以用两种方法来求解：直接求包含49的元素个数，或者求不包含49的元素个数ans（不包括0），然后输出n-ans即可。第二种方法在上一题已讲解，这里不再赘述。本节介绍第一种方法。
状态表示
f
[
p
o
s
]
[
s
t
a
]
f[pos][sta]
f[pos][sta]表示当前第pos位在sta状态下满足条件的个数，sta表示前一位是否是4，只有0和1两种状态。
状态转移方程
dfs(int pos, bool sta, bool limit)：pos表示枚举到当前位；sta表示前一位是否是4，若前一位是4，则sta=true，否则sta=false。
if (sta && i == 9)
ans += limit ? n % p[pos - 1] + 1 : p[pos - 1];
其中p[pos]表示
1
0
p
o
s
10^{pos}
10pos。若无限制，则49后面有多少位，就累加p[pos-1]的个数。例如[1, 500]区间，枚举时49后面还有一个位（可填0~9）， 则累加10个包含49的数，分别为490～499。若有限制，则求出49后面的数字再加1。例如[1, 496]区间，枚举时49后面的数位是6，则累加6+1个包含49的数，即490～496。
边界条件
当pos=0时，返回0。
记忆化搜索： 若没有限制且已赋值，则直接返回该值，无须再递归求解。
示例：计算[1, 500]区间有多少个数包含“49”，过程如下。
数字分解：nums[1]=0，nums[2]=0，nums[3]=5。从高位开始，当前位是第三位，前面一位不是4，有限制。up=nums[3]=5，枚举i=0…5。
i=0：以0开头的两位数，无限制，up=9，枚举i=0…9，只有一个数包含“49”，即049，故
f
[
2
]
[
0
]
=
1
f[2][0]=1
f[2][0]=1。i=1：以1开头的两位数，无限制且
f
[
2
]
[
0
]
f[2][0]
f[2][0]已赋值，返回该值，即149。i=2：以2开头的两位数，无限制且
f
[
2
]
[
0
]
f[2][0]
f[2][0]已赋值，返回该值，即249。i=3：以3开头的两位数，无限制且
f
[
2
]
[
0
]
f[2][0]
f[2][0]已赋值，返回该值，即349。i=4：以4开头的两位数，无限制，up=9，枚举i=0…9。i=4 时，向下找到一个解49，即449；i =9时，累加10个解，即490～499，故
f
[
2
]
[
1
]
=
11
f[2][1]=11
f[2][1]=11。i=5：以5开头的两位数，有限制，up=nums[2]=0，执行i=0， 递归求解。pos=0时，返回0。 累加结果，返回[1, 500]区间包含“49”的数15个，求解过程如下图所示。
示例2：计算[1, 496]区间有多少个数包含“49”？求解过程如下图所示。
算法实现
思路一
#include
#include
#include
using namespace std;
const int N = 30;
typedef long long LL;
// nums存储数位
int nums[N];
LL f[N][2], p[N];
LL x;
LL dfs(int pos, bool sta, bool limit)
{
if (!pos) return 0;
if (!limit && ~f[pos][sta] ) return f[pos][sta];
int up = limit ? nums[pos] : 9;
LL ans = 0;
for (int i = 0; i <= up; i ++ )
{
if (sta && i == 9) ans += limit ? x % p[pos - 1] + 1 : p[pos - 1];
else ans += dfs(pos - 1, i == 4, limit & i == up);
}
if (!limit ) f[pos][sta] = ans;
return ans;
}
LL solve(LL x)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[ ++ n] = x % 10;
x /= 10;
}
return dfs(n, false, true);
}
int main()
{
p[0] = 1;
for (int i = 1; i < N; i ++ ) p[i] = p[i - 1] * 10;
int T;
cin >> T;
while (T -- )
{
cin >> x;
cout << solve(x) << endl;
}
return 0;
}
思路二
#include
#include
#include
using namespace std;
const int N = 30;
typedef long long LL;
// nums存储数位
int nums[N];
LL f[N][2], p[N];
LL x;
// 求解[0, x]之间不包含49的个数
LL dfs(int pos, bool sta, bool limit)
{
// 注意是返回1
if (!pos) return 1;
if (!limit && ~f[pos][sta] ) return f[pos][sta];
int up = limit ? nums[pos] : 9;
LL ans = 0;
for (int i = 0; i <= up; i ++ )
{
if (sta && i == 9) continue;
ans += dfs(pos - 1, i == 4, limit && i == up);
}
if (!limit ) f[pos][sta] = ans;
return ans;
}
// 求解[1, x]之间不包含49的个数
LL solve(LL x)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[ ++ n] = x % 10;
x /= 10;
}
// dfs求出的是[0,x]中不包含49的个数 但我们需要计算的是[1,x]中不包含49的个数
// 因此需要刨去0这一个数
return dfs(n, false, true) - 1;
}
int main()
{
p[0] = 1;
for (int i = 1; i < N; i ++ ) p[i] = p[i - 1] * 10;
int T;
cin >> T;
while (T -- )
{
cin >> x;
// [1,x]中不包含49的个数为solve(x) 那么[1,x]中包含49的个数就是x - solve(x)
cout << x - solve(x) << endl;
}
return 0;
}
POJ3252 Round Numbers
题目描述
POJ3252 Round Numbers
题意：本题求[start, finish]区间Round Numbers的个数，其中Round Numbers是指二进制表示下0的个数大于或等于1的个数，是典型的数位DP问题。
算法思路
状态表示
f
[
p
o
s
]
[
x
0
]
[
x
1
]
f[pos][x_0][x_1]
f[pos][x0][x1]表示当前数位为pos时Round Numbers的个数，其中pos表示当前数位，
x
0
x_0
x0为二进制中0的个数，
x
1
x_1
x1为二进制中1的个数。可采用记忆化递归求解。
初始化一般设置含有前导0，即lead为true，并且有限制，即limit为true。
完美图解
计算[0, 5]区间Round Numbers的个数。
将5转换为二进制数101，nums[0]=1，nums[1]=0，nums[2]=1。首先从高位开始，当前位为第二位（下标为2），有前导零；有数位限制，枚举i=0…1。
i=0：有前导0，无限制，包含000、001、010、011四个数，去掉前导零后为0、1、10、11，其中0和10为Round Numbers（0的个数大于或等于1的个数），故
f
[
1
]
[
0
]
[
0
]
=
2
f[1][0][0]=2
f[1][0][0]=2i=1：无前导0，有限制，包含100、101两个数，其中100为Round Numbers，故
f
[
1
]
[
0
]
[
1
]
=
1
f[1][0][1]=1
f[1][0][1]=1 返回
f
[
2
]
[
0
]
[
0
]
=
f
[
1
]
[
0
]
[
0
]
+
f
[
1
]
[
0
]
[
1
]
=
2
+
1
=
3
f[2][0][0]=f[1][0][0]+f[1][0][1]=2+1=3
f[2][0][0]=f[1][0][0]+f[1][0][1]=2+1=3，表示[0, 5] 区间满足条件的数一共有3个：0、10、100。
求解过程如下图所示。
算法实现
#include
#include
using namespace std;
int f[40][40][40];
int nums[40];
/*求一个区间内Round Numbers（二进制0的个数不小于1的个数）的个数。
状态f[pos][num0][num1]；
pos为当前数位，num0为二进制中0的个数，num1为二进制中1的个数；
lead表示前导零；
limit表示数位限制。
*/
int dfs(int pos, int x0, int x1, bool lead, bool limit)
{
if (pos == -1) return x0 >= x1;
if (!limit && ~f[pos][x0][x1]) return f[pos][x0][x1];
int up = limit ? nums[pos] : 1, ans = 0;
for (int i = 0; i <= up; i ++ )
{
// 前导0，前面没有1
if (lead && !i ) ans += dfs(pos - 1, 0, 0, true, limit && i == up);
// 非前导0，即前面已有1
else ans += dfs(pos - 1, x0 + (i == 0), x1 + (i == 1), false, limit && i == up);
}
if (!limit ) f[pos][x0][x1] = ans;
return ans;
}
int solve(int x)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[n ++ ] = x % 2;
x /= 2;
}
return dfs(n - 1, 0, 0, true, true);
}
int main()
{
int l, r;
while (~scanf("%d%d", &l, &r)) {
printf("%d\n", solve(r) - solve(l - 1));
}
return 0;
}
AcWing338 计数问题
POJ2282
AcWing338 计数问题
题意：本题求[a , b]区间每个数字（0～9）的出现次数，为典型的数位DP问题。
算法思路
状态表示
f
[
p
o
s
]
[
x
]
[
c
n
t
]
f[pos][x][cnt]
f[pos][x][cnt]，pos为当前数位，x为当前统计的数字，cnt为当前已统计的x的出现次数。
可采用记忆化递归求解，dfs(int pos, int x, int cnt, bool lead, bool limit)，lead表示前导零；limit表示上界限制。
示例1：统计[1, 35]区间数字0的出现次数，过程如下。
数字分解：nums[1]=5，nums[2]=3。
统计数字0的出现次数。从高位开始，当前位为第二位（下标为2），有前导零，有限制，up=nums[2]=3，枚举i =0…3。
i=0：有前导零，无限制，枚举i=0…9，包含00～09，去掉前导零后为1～9，数字0出现0次。i=1：无前导零，无限制，枚举i=0…9，包含10～19，数字0出现1次，故
f
[
1
]
[
0
]
[
0
]
f[1][0][0]
f[1][0][0]。i=2：无前导零，无限制且
f
[
1
]
[
0
]
[
0
]
f[1][0][0]
f[1][0][0]已赋值，直接返回该值1。i=3：无前导零，有限制，up=nums[1]=5，枚举i =0…5，包含30 ～35，数字0出现1次。 累加结果，返回
f
[
2
]
[
0
]
[
0
]
=
3
f[2][0][0]=3
f[2][0][0]=3，表示[1, 35]区间数字0出现 3次：10、20、30。
求解过程如下图所示。
注意： 只有无前导零、无限制且
f
[
]
[
]
[
]
f[][][]
f[][][]已赋值时，才可以直接返回；只有无前导零且无限制时才可以对dp[][][]赋值；否则在执行完第2层第1个节点dfs(1, 0, 0, 1, 0)后，
f
[
1
]
[
0
]
[
0
]
f[1][0][0]
f[1][0][0]已赋值，到第2层 第2个节点dfs(1, 0, 0, 0, 0)时就直接返回了，这显然不对，因为0的出现次数不同。所以执行完第2层第1个节点dfs(1, 0, 0, 1, 0)后，
f
[
1
]
[
0
]
[
0
]
f[1][0][0]
f[1][0][0]不赋值，只累加结果，执行完第2层第2个节点dfs(1, 0,0, 0, 0)后，无前导零且无限制，直接赋值
f
[
1
]
[
0
]
[
0
]
=
1
f[1][0][0]=1
f[1][0][0]=1，到第2层第 3个节点dfs(1, 0, 0, 0, 0)时，无前导零、无限制且已赋值
f
[
]
[
]
[
]
f[][][]
f[][][]，直接返回该值，不需要重新计算。
示例2：统计[1, 35]区间数字3的出现次数，过程如下。
数字分解：nums[1]=5，nums[2]=3。
采用记忆化递归求解，当前位为第二位（下标为2），当前统计数字为3，有前导零，有限制up=nums[2]=3，枚举i=0…3。
i=0：有前导零，无限制，up=9，执行i=0…9，包含00～09， 数字3出现1次。i=1：无前导零，无限制，up=9，执行i =0…9，包含10～19， 数字3出现1次。无前导零且无限制，所以
f
[
1
]
[
3
]
[
0
]
=
1
f[1][3][0]=1
f[1][3][0]=1。i=2：无前导零，无限制且
f
[
1
]
[
3
]
[
0
]
f[1][3][0]
f[1][3][0]已赋值，直接返回该值1。i=3：无前导零，有限制，up=nums[1]=5，枚举i =0…5，包含 30～35，数字3的个数为7个。 累加结果，
f
[
2
]
[
3
]
[
0
]
=
10
f[2][3][0]=10
f[2][3][0]=10，表示[1, 35]区间数字3出现10 次：3、13、23、30、31、32、33、34、35。
求解过程如下图所示。
算法实现
写法一
#include
#include
#include
using namespace std;
typedef long long LL;
int nums[40];
LL f[15][10][15], res[2][10];
int dfs(int pos, int x, int cnt, bool lead, bool limit)
{
if (!pos) return cnt;
if (!limit && !lead && ~f[pos][x][cnt] ) return f[pos][x][cnt];
int up = limit ? nums[pos] : 9, t = 0;
LL ans = 0;
for (int i = 0; i <= up; i ++ )
{
if (x != i ) t = cnt;
else
{
if (lead && !x ) t = 0;
else t = cnt + 1;
}
ans += dfs(pos - 1, x, t, lead && i == 0, limit && i == up);
}
if (!limit && !lead) f[pos][x][cnt] = ans;
return ans;
}
void solve(LL x, int idx)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[ ++ n ] = x % 10;
x /= 10;
}
for (int i = 0; i < 10; i ++ )
res[idx][i] = dfs(n, i, 0, true, true);
}
int main()
{
LL l, r;
while (cin >> l >> r, l || r)
{
if (l > r) swap(l, r);
memset(res, 0, sizeof res);
solve(l - 1, 0);
solve(r, 1);
for (int i = 0; i < 10; i ++ ) cout << res[1][i] - res[0][i] << " ";
puts("");
}
return 0;
}
写法二
#include
#include
#include
using namespace std;
const int N = 15;
int nums[N], f[N][N];
int dfs(int pos, int cnt, int x, bool lead, bool limit)
{
if (!pos)
{
if (lead && !x) return 1;
return cnt;
}
if (!limit && !lead && ~f[pos][cnt]) return f[pos][cnt];
int up = limit ? nums[pos] : 9, ans = 0;
for (int i = 0; i <= up; i ++)
{
int t;
if (x != i ) t = cnt;
else
{
if (!x ) t = cnt + (lead == 0);
else t = cnt + 1;
}
ans += dfs(pos - 1, t, x, lead && i == 0, limit && i == up);
}
if (!limit && !lead) f[pos][cnt] = ans;
return ans;
}
int solve(int x, int num)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[++ n] = x % 10;
x /= 10;
}
return dfs(n, 0, num, true, true);
}
int main()
{
int l, r;
while (cin >> l >> r, l || r)
{
if (l > r) swap(l, r);
for (int i = 0; i <= 9; i ++) cout << solve(r, i) - solve(l - 1, i) << " ";
puts("");
}
}
P2657 Windy数
题目描述
P2657 Windy数
算法思路
此题思路大体和 POJ3252 Round Numbers 类似。
状态表示
f
[
p
o
s
]
[
p
r
e
]
f[pos][pre]
f[pos][pre]表示枚举到第pos位，其前面一位的数字是pre，最终不含前导0的方案数。
我们考虑限制条件：相邻两位绝对值大于等于2。如果前一位是前导0，那么我们不需要考虑这位与0的绝对值，也就是说0和1也是可以取到的，所以我们可以在处理下一位时把这位当做−2处理。
由于我们初始化lead=true，即存在前导0， 搜索初始条件第二个参数pre必须填一个≤-2的数来保证可以搜索下去，不然会出错，这里要初始化传入pre=-2。
算法实现
写法一（代码大体同POJ3252的代码）：
#include
#include
#include
using namespace std;
typedef long long LL;
int nums[15];
LL f[15][15];
// pos当前位置,pre前一位数,lead判断前面是否全是0,limit最高位限制
int dfs(int pos, int pre, bool lead, bool limit)
{
if (!pos) return 1;
// 可以写成!limit && !lead && ~f[pos][pre]
if (!limit && ~f[pos][pre] ) return f[pos][pre];
int up = limit ? nums[pos] : 9;
LL ans = 0;
for (int i = 0; i <= up; i ++ )
{
// 不合题意
if (abs(i - pre) < 2) continue;
// 如果有前导0，下一位随意
if (lead && !i ) ans += dfs(pos - 1, -2, true, limit && i == up);
// 如果没有前导0，继续按部就班地搜
else ans += dfs(pos - 1, i, false, limit && i == up);
}
// 可以写成 !limit && !lead
if (!limit ) f[pos][pre] = ans;
return ans;
}
int solve(LL x)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[ ++ n] = x % 10;
x /= 10;
}
return dfs(n, -2, true, true);
}
int main()
{
LL l, r;
cin >> l >> r;
cout << solve(r) - solve(l - 1) << endl;
return 0;
}
AcWing1081 度的数量
题目描述
AcWing1081 度的数量
算法思路
K个互不相等的B的整数次幂之和等价于求数字n在B进制表示下是否由K个1且其他位为0组成。这题最关键的就是要发现这个性质！
为什么会得出这个结论呢？看分析：
比如K=2，B=2：
(
15
)
10
=
(
01111
)
2
(15)_{10}={(01111)}_2
(15)10=(01111)2
(
16
)
10
=
(
10000
)
2
(16)_{10}={(10000)}_2
(16)10=(10000)2
(
17
)
10
=
(
10001
)
2
(17)_{10}=(10001)_2
(17)10=(10001)2，
17
=
2
0
+
2
4
17=2^0+2^4
17=20+24
(
18
)
10
=
(
10010
)
2
(18)_{10}=(10010)_2
(18)10=(10010)2，
18
=
2
1
+
2
4
18=2^1+2^4
18=21+24
(
19
)
10
=
(
10011
)
2
(19)_{10}=(10011)_2
(19)10=(10011)2
(
20
)
10
=
(
10100
)
2
(20)_{10}=(10100)_2
(20)10=(10100)2，
20
=
2
2
+
2
4
20=2^2+2^4
20=22+24
从中可以看出，17和18和20是符合要求的，而且从它们的B进制(二进制)可以看出，都有k个1，其他位全为0组成。
再比如K=2，B=4：
(
4
)
10
=
(
0010
)
4
(4)_{10}=(0010)_4
(4)10=(0010)4
(
5
)
10
=
(
0011
)
4
(5)_{10}=(0011)_4
(5)10=(0011)4，
5
=
4
0
+
4
1
5=4^0+4^1
5=40+41
(
6
)
10
=
(
0012
)
4
(6)_{10}=(0012)_4
(6)10=(0012)4
(
7
)
10
=
(
0013
)
4
(7)_{10}=(0013)_4
(7)10=(0013)4
(
8
)
10
=
(
0020
)
4
(8)_{10}=(0020)_4
(8)10=(0020)4
(
17
)
10
=
(
0101
)
4
(17)_{10}=(0101)_4
(17)10=(0101)4，
17
=
4
0
+
4
2
17=4^0+4^2
17=40+42
(
18
)
10
=
(
0102
)
4
(18)_{10}=(0102)_4
(18)10=(0102)4
(
19
)
10
=
(
0103
)
4
(19)_{10}=(0103)_4
(19)10=(0103)4
(
20
)
10
=
(
0110
)
4
(20)_{10}=(0110)_4
(20)10=(0110)4，
20
=
4
1
+
4
2
20=4^1+4^2
20=41+42
(
21
)
10
=
(
0111
)
4
(21)_{10}=(0111)_4
(21)10=(0111)4
从中可以看出，5和17和20是符合要求的，而且从它们的B进制(四进制)可以看出，都有k个1，其他位全为0组成。
也就是说，我们只关心B进制下的0和1，其他数字都是干扰项，对答案并没有任何贡献。
我们来分析一下：前导零不影响，所以不需要lead变量。因为要记录数量，所以要增加计数变量cnt表示已经用了多少个1。不需要记录前驱，因此不用设置pre变量。判断边界时只要最后数量cnt==k，若相等，则返回1，否则就返回0。同时枚举数字时如果前面系数不为1或者或者没搜索完就已经k个了，那么就直接continue。
算法实现
#include
#include
#include
using namespace std;
const int N = 35;
int nums[N], f[N][N];
int B, K;
int dfs(int pos, int cnt, bool limit)
{
if (!pos) return cnt == K;
if (!limit && ~f[pos][cnt] ) return f[pos][cnt];
int up = limit ? nums[pos] : B - 1, ans = 0;
for (int i = 0; i <= up; i ++ )
{
if (i > 1 || (i == 1 && cnt == K)) continue;
ans += dfs(pos - 1, cnt + (i == 1), limit && i == up);
}
if (!limit ) f[pos][cnt] = ans;
return ans;
}
int solve(int x)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[ ++ n] = x % B;
x /= B;
}
return dfs(n, 0, true);
}
int main()
{
int l, r;
scanf("%d%d%d%d", &l, &r, &K, &B);
printf("%d\n", solve(r) - solve(l - 1));
return 0;
}
AcWing1082 数字游戏
题目描述
AcWing1082 数字游戏
算法思路
分析：前导零不影响，所以不需要变量lead，只需要判断枚举的位数是不是非严格递增来判断是否继续搜索。由于我们想要知道前后两个位之间的大小关系，因此需要设置pre变量表示前一个位上的数是啥。
算法实现
#include
#include
#include
using namespace std;
const int N = 15;
int nums[N], f[N][N];
int dfs(int pos, int pre, bool limit)
{
if (!pos) return 1;
if (!limit && ~f[pos][pre]) return f[pos][pre];
int up = limit ? nums[pos] : 9, ans = 0;
for (int i = 0; i <= up; i ++ )
{
if (i < pre) continue;
ans += dfs(pos - 1, i, limit && i == up);
}
if (!limit ) f[pos][pre] = ans;
return ans;
}
int solve(int x)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[ ++ n] = x % 10;
x /= 10;
}
return dfs(n, 0, true);
}
int main()
{
int l, r;
while (~scanf("%d%d", &l, &r)) {
printf("%d\n", solve(r) - solve(l - 1));
}
return 0;
}
AcWing1084 数字游戏II
题目描述
AcWing1084 数字游戏 II
算法思路
分析：前导零不影响，所以不需要变量lead。此题涉及到数字和 ，所以要用到变量sum来记录数位和。不需要记录前驱pre。故可以定义状态
f
[
p
o
s
]
[
s
u
m
]
f[pos][sum]
f[pos][sum]。边界条件就是sum % n == 0，如果是则返回1，否则返回0。
算法实现
#include
#include
#include
using namespace std;
const int N = 1010;
int nums[N], f[N][N];
int l, r, p;
int dfs(int pos, int sum, bool limit)
{
if (!pos) return sum % p == 0;
if (!limit && ~f[pos][sum] ) return f[pos][sum];
int up = limit ? nums[pos] : 9, ans = 0;
for (int i = 0; i <= up; i ++ )
{
ans += dfs(pos - 1, sum + i, limit && i == up);
}
if (!limit ) f[pos][sum] == ans;
return ans;
}
int solve(int x)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[ ++ n] = x % 10;
x /= 10;
}
return dfs(n, 0, true);
}
int main()
{
while (~scanf("%d%d%d", &l, &r, &p)) {
printf("%d\n", solve(r) - solve(l - 1));
}
return 0;
}
LC233 数字1的个数
题目描述
传送门
算法思路
定义记忆化搜索函数：int dfs(int pos,int cnt,int limit)，本题前导0对答案没有影响，所以不需要lead。
pos是当前位，cnt是从最高位到pos-1位中1的个数，limit表示当前位的数大小是否有限制
算法实现
class Solution {
public:
int nums[12], f[12][12];
// pos是当前位，cnt是从最高位到pos-1位中1的个数，limit表示当前位的数大小是否有限制
int dfs(int pos,int cnt,int limit){
if (!pos) return cnt;
if (!limit && ~f[pos][cnt]) return f[pos][cnt];
int up = limit ? nums[pos] : 9, ans = 0;
for (int i = 0; i <= up; i ++ ) {
ans += dfs(pos - 1, cnt + (i == 1), limit && i == up);
}
if(!limit) f[pos][cnt] = ans;
return ans;
}
int solve(int x)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[ ++ n] = x % 10;
x /= 10;
}
return dfs(n, 0, true);
}
int countDigitOne(int n) {
return solve(n);
}
};
LC2376 统计特殊整数
题目描述
LC2376 统计特殊整数
算法思路
本题要求的这个特殊正整数中每个数位都是不相同的，那么我们就需要知道前面的位中已经填了哪些数，这样后面的位才能知道该怎么填数。这里需要定义变量mask表示前面选过的数字集合。
在本题中，要求「至少有 1 位重复的数字」，此时 0001 和 1 就不等价了，0001 是一个满足要求的数字，而 1 是不满足要求的数字，而在 [0, n] 中，0001 其实是非法的，所以会出现错误，故需要变量lead。有限制，因此需要定义变量limit。
所以记忆化搜索就是：dfs(int pos, int mask, bool lead, bool limit)。
算法实现
class Solution {
public:
int nums[11], f[11][1 << 11];
// 求出[0, x]中满足题意的个数
int dfs(int pos, int mask, bool lead, bool limit)
{
if (pos == 0) return 1;
if (!lead && !limit && ~f[pos][mask]) return f[pos][mask];
int up = limit ? nums[pos] : 9, ans = 0;
for (int i = 0; i <= up; i ++ )
{
if (mask >> i & 1) continue;
if (lead && !i ) ans += dfs(pos - 1, mask, true, limit && i == up) ;
else ans += dfs(pos - 1, mask | 1 << i, false, limit && i == up);
}
if (!limit && !lead) f[pos][mask] = ans;
return ans;
}
// 求出[1, x]中满足题意的个数
int solve(int x)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[ ++ n] = x % 10;
x /= 10;
}
return dfs(n, 0, true, true) - 1; // 不能把0计算在内 故需要减去一个
}
int countSpecialNumbers(int n) {
return solve(n);
}
};
LC600 不包含连续1的非负整数
题目描述
传送门
算法思路
分析：对于本题来说，前导0对于答案并无影响，因此不需要定义lead变量。由于是求不含连续的1，因此对于当前位pos，我们应该要知道它前面那位填啥，因此需要定义变量pre，其值是0或1。因此，记忆化搜索：int dfs(int pos, int pre, bool limit)。
在状态转移时，如果pre为1并且当前位也是1，那么就直接continue。否则就说明pre为0，那么判断i==1即可。
算法实现
class Solution {
public:
int nums[40], f[40][2];
int dfs(int pos, int pre, bool limit)
{
if (!pos) return 1;
if (!limit && ~f[pos][pre] ) return f[pos][pre];
int up = limit ? nums[pos] : 1, ans = 0;
for (int i = 0; i <= up; i ++ )
{
if (pre && i == 1) continue;
ans += dfs(pos - 1, i == 1, limit && i == up);
}
if (!limit ) f[pos][pre] = ans;
return ans;
}
int solve(int x)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[ ++ n] = x % 2;
x /= 2;
}
return dfs(n, 0, true);
}
int findIntegers(int n) {
return solve(n);
}
};
LC902 最大为N的数字组合
题目描述
传送门
算法思路
将数字x转成int数组nums[]，其中nums[1]是最低位，nums[n]是最高位。
设置记忆化搜索函数dfs(int pos, bool lead, bool limit)，答案就是dfs(n, true, true)。
其中：
pos表示数字的位数，从末位或者第一位开始，一般根据题目的数字构造性质来选择顺序。对于本题，我们选择从高位开始，因此，pos的初始值为n；lead表示当前数字中是否包含前导零，如果包含，则为true，否则为false；初始化为true；limit表示可填的数字的限制，如果无限制，那么可以选择
[
0
,
⋯
,
9
]
[0,\cdots, 9]
[0,⋯,9]。否则，只能选择0到nums[pos]。如果limit为true且已经取到了能取到的最大值，那么下一个limit同样为 true；如果limit为true但是还没有取到最大值，或者limit为false，那么下一个limit为false。
算法实现
class Solution {
public:
int nums[12];
int f[12];
unordered_set
int dfs(int pos, int lead, bool limit) {
if (!pos)
{
// 等价于这种写法：return lead ^ 1; 或者 return lead ? 0 : 1;
if (lead) return 0;
return 1;
}
if (!limit && !lead && ~f[pos]) return f[pos];
int up = limit ? nums[pos] : 9, ans = 0;
for (int i = 0; i <= up; ++i)
{
if (lead && !i ) ans += dfs(pos - 1, true, limit && i == up);
else if (S.count(i)) {
ans += dfs(pos - 1, false, limit && i == up);
}
}
if (!limit && !lead) f[pos] = ans;
return ans;
}
int solve(int x)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[ ++ n] = x % 10;
x /= 10;
}
return dfs(n, true, true);
}
int atMostNGivenDigitSet(vector
for (auto& d : digits) S.insert(stoi(d));
return solve(n);
}
};
LC1012 至少有1位重复的数字
题目描述
传送门
算法思路
这题其实是LC2376的对偶问题。LC2376是求
[
1
,
n
]
[1,n]
[1,n]中不含重复数的个数，而这题是求
[
1
,
n
]
[1,n]
[1,n]中含重复数的个数。我们可以利用LC2376的代码，然后用n减去不含重复数的个数就可以得到
[
1
,
n
]
[1,n]
[1,n]中含重复数的个数了。
在本题中，要求「至少有 1 位重复的数字」，此时 0001 和 1 就不等价了，0001 是一个满足要求的数字，而 1 是不满足要求的数字，而在 [0, n] 中，0001 其实是非法的，所以会出现错误，故需要变量lead。
算法实现
class Solution {
public:
int nums[11], f[11][1 << 11];
// 求出[0, x]中无重复数字的个数
int dfs(int pos, int mask, bool lead, bool limit)
{
if (pos == 0) return 1;
if (!lead && !limit && ~f[pos][mask]) return f[pos][mask];
int up = limit ? nums[pos] : 9, ans = 0;
for (int i = 0; i <= up; i ++ )
{
if (mask >> i & 1) continue;
if (lead && !i ) ans += dfs(pos - 1, mask, true, limit && i == up) ;
else ans += dfs(pos - 1, mask | 1 << i, false, limit && i == up);
}
if (!limit && !lead) f[pos][mask] = ans;
return ans;
}
// 求出[1, x]中无重复数字的个数
int solve(int x)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[ ++ n] = x % 10;
x /= 10;
}
return dfs(n, 0, true, true) - 1; // 不能把0计算在内 故需要减去一个
}
int numDupDigitsAtMostN(int n) {
// n个数减去无重复的个数，那么就得到重复数的个数
return n - solve(n);
}
};
LC788 旋转数字
题目描述
传送门
算法思路
根据题意，好数中不能含有3,4,7，且至少包含2,4,5,6,9中的一个。我们定义一个数组diffs：
int diffs[10] = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1}; # 0123456789
分别对应0到9中的每个数，其中数字0,1,8其旋转后仍然是它自身，我们设为0。将数字3,4,7设为-1。将数字2,4,5,6,9设为1。
我们定义变量hasDiff表示前面填的数字是否包含2,4,5,6,9中的一个。对于本题来说，前导0并不会影响答案，所以不用lead变量。
算法实现
class Solution {
public:
int diffs[10] = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
int nums[11], f[11][2];
int dfs(int pos, bool hasDiff, bool limit)
{
if (!pos) return hasDiff;
if (!limit && ~f[pos][hasDiff]) return f[pos][hasDiff];
int up = limit ? nums[pos] : 9, ans = 0;
for (int i = 0; i <= up; i ++ )
if (~diffs[i])
ans += dfs(pos - 1, hasDiff || diffs[i], limit && i == up);
if (!limit ) f[pos][hasDiff] = ans;
return ans;
}
int solve(int x)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[ ++ n] = x % 10;
x /= 10;
}
return dfs(n, false, true);
}
int rotatedDigits(int n) {
return solve(n);
}
};
LC357 统计各位数字都不同的数字个数
题目描述
传送门
算法思路
此题思路大体同 LC2376。唯一需要做的就是注释掉两段代码，见算法实现部分。
算法实现
class Solution {
public:
int nums[12], f[12][12];
int dfs(int pos, int mask, bool lead, bool limit)
{
if (!pos) return 1;
//if (!limit && !lead && ~f[pos][mask]) return f[pos][mask];
int up = limit ? nums[pos] : 9, ans = 0;
for (int i = 0; i <= up; i ++ )
{
if (mask >> i & 1) continue;
if (lead && !i ) ans += dfs(pos - 1, mask, true, limit && i == up);
else ans += dfs(pos - 1, mask | 1 << i, false, limit && i == up);
}
//if (!limit && !lead) f[pos][mask] = ans;
return ans;
}
int solve(int x)
{
memset(f, -1, sizeof f);
int n = 0;
while (x)
{
nums[ ++ n] = x % 10;
x /= 10;
}
return dfs(n, 0, true, true);
}
int countNumbersWithUniqueDigits(int n) {
int x = 1;
for (int i = 0; i < n; i ++ ) x *= 10;
return solve(x - 1);
}
};
以上就是一些数位dp习题汇总，相信你做完这些题目后，帮记忆化搜索的模板背熟，以后碰到数位dp的题脑海里就有大体框架了，再根据不同题意去求解即可。