数位 DP

解决的是求一段区间中满足一定条件的数的数量,形式固定

# 数位 DP 模板

int num[100],dp[100][...];
int dfs(int pos,int ...,bool limit) {
	if(pos==0) return ;
	if(!limit && dp[pos][...]!=-1) return dp[pos][...];
	int up=limit?num[pos]:9;
	int sum=0;
	for(int i=0; i<=up; i++) {
		if(...) sum+=dfs(pos-1,...,limit && (i==up));
	}
	if(!limit) dp[pos][...]=sum;
	return sum;
}
//ps 如果有前导 0 就可以加一个 lead, 一开始传 1,然后后面就传 lead&&(i==0) 就可以了
int work(int x) {
	int len=0;
	while(x) {
		num[++len]=x%10;
		x=x/10;
	}
	return dfs(len,...,1); // 第一位直接上限位
}

以一道例题讲解算法

# 不要 62

求 [L,R] 内所有没出现 4、62 的数字数量,比如 662、458 这些都不满足条件。

首先转化为算 1~R 满足条件数字的问题,然后用 fun (R)-fun (L-1) 就是答案,数位 DP 就是对数位进行记忆化搜索,保存可以利用的信息,从而进行剪枝优化时间。核心在于 dp [][] 数组去保存信息,第一维表示当前的位数,第二维表示前一位的状态,记录的是这一维没有限制时符合条件的数量,也就是当前这一位是 0~9 时的数量,因为这个状态重复的最多且计算量大

这就是这道题目的代码

// 当前的数位,前一位是否为 6,前一位是否有限制
int dfs(int pos,bool state,bool limit){
    // 到最后一位返回 1,表示有一个数满足要求
	if(pos==0) return 1;
    // 前一位没有限制表示当前可以取得数字是 0~9,看一下是否可以记忆化剪枝
    // 注意这里 dp 为 0 也可以返回,因为 dp 记录的是这种状态的答案数量,可能为 0
	if(!limit && dp[pos][state]!=-1) return dp[pos][state];
    // 当前最高计算到多少位
	int up=limit?num[pos]:9;
    // 计算这个状态的答案 sum
	int sum=0;
	for(int i=0;i<=up;i++){
		if(state && i==2) continue;	//62 跳过
		if(i==4) continue;	//4 跳过
		sum+=dfs(pos-1,i==6,limit&&num[pos]==i); // 深搜累加答案
	}
	if(!limit) dp[pos][state]=sum; // 保存状态
	return sum;	// 记得返回答案
}
int work(int x){
	cnt=0;
	while(x){
		num[++cnt]=x%10;	// 保存数位
		x/=10;
	}
	return dfs(cnt,0,1);
}

# Round Numbers

统计区间中二进制 0 的个数不小于 1 的个数的所有数字。

这里比不要 62 多了一个参数,表示是否有前导零。

写法 1:

三维 dp,第三维表示总位数,这个地方我刚开始写错了,没考虑到这个,只记录了 0 的数量,其实 1 的数量也要考虑进去,否则 1 个 0,1 个 1 和 1 个 0,2 个 1 就会被记录成一个状态,导致答案错误,这里我这么写主要为了使用 ksm 剪枝,更快求出答案。

int dfs(int pos,int js,bool limit,bool lead){
	if(pos==0) return js>=(res-js);
	if(!limit && !lead && js>=(res-js)) dp[pos][js][res]=ksm(2,pos);
	if(!limit && !lead && dp[pos][js][res]!=-1) return dp[pos][js][res];
	int up=limit?num[pos]:1;
	int sum=0;
	for(int i=0;i<=up;i++){
		if(i==0 && lead){
			res--;
			sum+=dfs(pos-1,js,limit&&num[pos]==i,1);
			res++;
		}
		else sum+=dfs(pos-1,i==0?js+1:js,limit&&num[pos]==i,0);
	}
	if(!limit && !lead) dp[pos][js][res]=sum;
	return sum;
}
int work(int x){
	cnt=0;
	while(x){
		num[++cnt]=x%2;
		x/=2;
	}
	res=cnt;
	return dfs(cnt,0,1,1);
}

写法 2:

当前位是 0 就加,是 1 就减,直接包含了所有状态,省空间且写法简单,需要学习,初始值为 32 因为不能减到负数,因为还要作为数组下标存储状态

int dfs(int pos,int js,bool limit,bool lead){
	if(pos==0) return js>=32;
	if(!limit && !lead && dp[pos][js]!=-1) return dp[pos][js];
	int up=limit?num[pos]:1;
	int sum=0;
	for(int i=0;i<=up;i++){
		if(i==0 && lead) sum+=dfs(pos-1,js,limit&&num[pos]==i,1);
		else sum+=dfs(pos-1,i==0?js+1:js-1,limit&&num[pos]==i,0);
	}
	if(!limit && !lead) dp[pos][js]=sum;
	return sum;
}
int work(int x){
	cnt=0;
	while(x){
		num[++cnt]=x%2;
		x/=2;
	}
	res=cnt;
	return dfs(cnt,32,1,1);
}
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝