首页 > 极客资料 博客日记

【学习笔记】数位DP

2024-09-17 11:30:02极客资料围观22

本篇文章分享【学习笔记】数位DP,对你有帮助的话记得收藏一下,看极客之家收获更多编程知识

数位DP

适用条件

此类题目一般要求在\([l,r]\)区间内满足条件的数的个数,答案一般与数的大小无关,而与数各位的组成有关。题目中给出的数的范围一般较大,往往在\(10^9\)以上因此无法暴力枚举,只能使用动态规划

代码实现

使用记忆化搜索更简单易于理解。
从数的高位向低位搜索,每一位可以为\(0-9\)。但是注意当搜索到第\(i\)位时,如果前\(i-1\)位已经是最大值时,那么当前的数也不能超过最值,即范围为

\[0-a[i] \]

因此记忆化搜索函数需要两个参数。
1.\(cur\)表示当前位于第\(cur\)
2.\(lim\)表示前\(cur-1\)是否已经全部达到最大值。\(lim_{cur+1}==1\),当且仅当

\[lim_{cur}==1,i==max \]

因为题目要求\([l,r]\)区间内满足条件的个数,由于个数满足区间可加性,因此可以用类似前缀和的方法来求。设\(calc(i)\)表示\(0-i\)区间内的个数,那么答案就是\(calc(r)-calc(l-1)\)

\(ACcode\)

\(DFS code\)

int dfs(int x,bool lim){
	if(x<=0)return 1;
	if(!lim&&f[x]!=-1)return f[x];
	int up=lim?a[x]:9;
	int ans=0;
	for(int i=0;i<=up;i++){
		if(i!=4)ans+=dfs(x-1,lim&&(i==up));
	}
	if(!lim)f[x]=ans;
	return ans;
}

初始化+\(calc\ code\)


int calc(int x){
	len=0;
	memset(f,-1,sizeof(f));
	while(x){
		a[++len]=x%10;
		x/=10;
	}
	return dfs(len,1);
}


版权声明:本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!

标签:

相关文章

本站推荐

标签云