算法笔记——数位DP

发布于:2024-05-16 ⋅ 阅读:(28) ⋅ 点赞:(0)

一、前置知识

1.DP小知识

D P DP DP 是一种算法思想,用递推方程的方式解决问题。但是使用它要满足如下性质:

  • 最优子结构: 子结构优秀,整个就优秀。
  • 无后效性:当前决策不会影响后面。

2.DP实现方法

众所周知, D P DP DP 可以使用记忆化搜索实现。模板:

int dp[状态];
int dfs(当前状态){
	if (满足退出条件) return 退出返回值;
	if (dp[当前状态]!=-1) return dp[当前状态];
	int ans=0; 辅助变量
	进行状态转移
	return dp[当前状态]=ans;
}memset(dp,-1,sizeof(dp));

二、问题提出

给你一个区间 [ l , r ] [l,r] [l,r] 和一个条件,求区间内满足条件的数的个数。

要求复杂度 O ( l o g 10 n ) O(log_{10}n) O(log10n)

三、解决问题

我们以一个具体问题入手:数页码

看如下树形图:

接下来我们可以设计转移:

int dp[20][210];//dp[i][j]表示i位和为j的数字个数

但是如果改一下:
在这里插入图片描述
我们会发现,有时数位有限制,所以我们要增加一维 l i m lim lim,表示是否有限制。

强调一下: 有的问题会有 前导零的特殊处理方式,则需要加一位 z e ze ze,表示有没有前导零。

四、蓝题解答

windy数

可以增加一维 p r e pre pre,表示上一位去什么数。(本题涉及前导零,请谨慎思考)。

代码(附带模板):

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[20][10][2][2],num[20],tot;
//id pre lim
int dfs(int id,int pre,int lim,int ze){
	//位数,前一位 ,限制,前导零
	//if (id!=tot&&ze)
	if (id==0) return 1-ze;
	if (dp[id][pre][lim][ze]!=-1){
		return dp[id][pre][lim][ze];
	}int ans=0,up=(lim?num[id]:9);
	for (int i=0; i<=up; i++){
		if (abs(pre-i)>=2||ze){
			ans+=dfs(id-1,i,lim&&(i==up),ze&&(i==0));
		}
	}//cout<<id<<" "<<pre<<" "<<lim<<" "<<ze<<" "<<ans<<"\n";
	return dp[id][pre][lim][ze]=ans;
}int solve(int x){
	tot=0; memset(dp,-1,sizeof(dp));
	while (x) num[++tot]=x%10,x/=10;
	//cout<<tot<<"\n";
	return dfs(tot,0,1,1); 
}
signed main(){
	int l,r; cin>>l>>r;
	cout<<solve(r)-solve(l-1);
	//cout<<solve(r)<<" "<<solve(l-1);
}

五、特别说明

今天是母亲节,要特别感谢妈妈!

没有她们的大力支持,就没有我们这些 蒟蒻 OIer。