四大dp系列--数位dp

数位dp

(本文参考于 大佬博客)

数位dp是一种高速求解给定区间内符合一定条件的数的个数的算法。其基本思想为记忆化搜索。

数位dp一般应用于:

  1. 求出在给定区间[A,B]内,符合条件P(i)的数i的个数.

  2. 条件P(i)一般与数的大小无关,而与 数的组成 有关

求解的基本步骤如下:

  1. 当我们求 [ 0 , 100000 ] 和 [ 100001 , 200000 ]中符合条件的数的个数时,我们只需要求出前一个区间符合条件的数的个数,后面的区间只需要使用前面计算出来的值就可以了。

  2. 以下面的 不含49 为例,当我们在求[ 49001 , 50000 ]符合条件的数的个数时,会有不符合条件的情况存在,因此我们需要对其值进行判断,即将这一部分的值省略掉,当把这部分去掉之后,我们再求出来[ 0 , 100000 ]中符合条件的数的个数。

  3. 如果 b 为 123456 ,如果我们仍然求解[100001,200000]的话就会出错,我们只能先求解[100000,120000],然后再求解[120001,123000],因此,我们还需要判断当前是否是数的上限。

不含49

求[ a , b ]中不包含49的数的个数。

1<=a<=b<=1e9

代码如下:

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a,b;
int num[20];//储存每一位的值
int dp[20][2];//储存长度为length时符合条件的数的数量,两个数组分别表示 是4时 和 不是4时 的数量

int dfs(int length,bool is_4,bool is_max){
//如果计算到最后一位,那么直接返回
if(length==-1) return 1;

//如果不是数的上限并且之前计算过,这步就是记忆化最关键的一步
if(!is_max && dp[length][is_4]) return dp[length][is_4];

int cnt=0,maxx=(is_max ? num[length]:9);//判断是否是上限,即判断当前位所能取到的值的范围
for(int i=0;i<=maxx;i++){
if(is_4 && i==9) continue;//上一位是4,这一位是9,那么就直接跳过
cnt+=dfs(length-1,i==4,is_max && i==maxx);
}

//如果是上限,那么不能保存,因为dp保存的是[100000,200000]这样的值,并不能储存[100000,120000]的值
return is_max?cnt:dp[length][is_4]=cnt;
}

int solve(int x){
memset(num,0,sizeof(num));
int length=0;
while(x){
num[length++]=x%10;
x/=10;
}
return dfs(length-1,false,true);
}
int main()
{
scanf("%d %d",&a,&b);
printf("%d\n",solve(b)-solve(a-1));
return 0;
}

这是数位dp最基本的模板。

不要62

不要62

题意很简单,求区间内不含 4 和 62 的数的个数。

这个代码和上面的代码几乎一样,只是中间加了一步判断 4 的步骤

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
#include<bits/stdc++.h>
using namespace std;
int a[20];
int dp[20][2];
int dfs(int length,int is_6,bool is_max){
if(length==-1) return 1;
if(!is_max && dp[length][is_6]) return dp[length][is_6];

int cnt=0;
int maxx=is_max?a[length]:9;

for(int i=0;i<=maxx;i++){
if(is_6 && i==2) continue;//不要62
if(i==4) continue; //不要4

cnt+=dfs(length-1,i==6,is_max && i==maxx);
}
if(!is_max) dp[length][is_6]=cnt;
return cnt;
}
int solve(int x){
int length=0;
while(x){
a[length++]=x%10;
x/=10;
}
return dfs(length-1,0,true);
}
int main()
{
int a,b;
while(~scanf("%d %d",&a,&b) && a+b){
printf("%d\n",solve(b)-solve(a-1));
}
return 0;
}

只要13

找出1~n范围内含有13并且能被13整除的数字的个数.

这个题目条件比前两个复杂一点,我们需要计算出这个数字是否是13的倍数,并且是否包含13,所以,我们需要用两个变量来判断。

一个变量用来判断是否是13的倍数;另一个变量用来判断是否包含13。而判断13时有三种情况:

  1. 上一位不是 1
  2. 上一位是 1 但这一位不是 3
  3. 上一位是 1 且这一位是 3

因此不能用 bool 类型数据判断是否包含13。

代码如下:

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
#include<bits/stdc++.h>
using namespace std;
int a[100];
int dp[20][20][10];//三维表示:长度为 length ,模数为 mod , 是否包含 13
int dfs(int length,int mod,int have_13,bool limit){
if(length==-1) return mod==0 && have_13==2;// 是 13 的倍数并且包含 13
if(!limit && dp[length][mod][have_13]) return dp[length][mod][have_13];

int cnt=0;
int maxx=limit?a[length]:9;
for(int i=0;i<=maxx;i++){
int next=have_13;
//这是为了寻找数是否包含13,当have_13==2,即找到13后,就不会进行下列判断
if(have_13!=2 && i!=1) next=0;//没有特殊情况(尾数不是 1 或 13 )
if(have_13!=2 && i==1) next=1;//尾数为1
if(have_13==1 && i==3) next=2;//后两位尾数为13

cnt+=dfs(length-1,(mod*10+i)%13,next,limit&i==maxx);
}
if(!limit) dp[length][mod][have_13]=cnt;
return cnt;
}
void solve(int n){
int length=0;
while(n){
a[length++]=n%10;
n/=10;
}
printf("%d\n",dfs(length-1,0,0,true));
}
int main()
{
int n;
while(~scanf("%d",&n)){
solve(n);
}
return 0;
}

从上面几个例题我们就可以看出,求解基本的数位dp的核心就是处理所需要判断的条件,上面三个代码大体框架都一样,只是在判断是否继续向下求解时有所不同,因此我们只要处理好需要判断的条件就能够做简单的数位dp问题。

部分数位dp题目以及题解:

Mountain Number

Seven Segment Display

感谢您的支持
-------------本文结束感谢您的阅读-------------