数位DP模板详解

已经很长时间没有做过关于数位DP的题目了，现在来写一下自己对于数位DP的理解：

一般这种题目都是问在区间[l,r]内满足某种条件的数有多少，显然我们可以转换为求0~x中满足该条件的数有多少，然后利用前缀和思想，直接用0~r中满足某种条件的数的个数减去0~l-1中满足某种条件的个数即可，这个就不细说了，下面看一下板子：

int a[N]; ll f[N][s];//第一维一般是当前枚举到的位数，第二位表示状态（具体问题具体分析） ll dp(int pos/*当前枚举到的位*/,/*s代表状态*/,bool lead/*前导0，有些题目需要考察前导0*/,bool limit/*当前位是否可以任选*/) { //递归边界 if(pos==0) return /*满足条件？1：0*/; if(!limit&&!lead&&f[pos][s]!=-1) return f[pos][s];//记忆化,在没有前导0且可以任选的情况下如果当前状态的值已经被计算过则可以直接返回 int up=limit?a[pos]:(进制-1);//根据limit判断枚举的上界up,如果前面一直都是取的可以取的最大值，那么当前值最大也是所给数该位的值，反之为要求进制下所能取到的最大值 ll ans=0;//记录答案 for(int i=0;i<=up;i++)//枚举每一位并记录答案 { if() return 0;//这个地方有可能会剪枝 //这个地方有可能会因为前导0的存在而分类讨论 ans+=dp(pos-1,/*状态转移*/,lead&&i==0,limit&&i==a[pos]);//这个仔细想想也比较容易理解 } if(!limit&&!lead) f[pos][s]=ans;//如果当前可以任选且没有前导0那么就把答案记录下来用于记忆化搜索 return ans; } ll solve(ll x) { if(!x) return ;//一般需要单独讨论x取0的情况，否则有可能在数位DP过程中出现一些不可预知的问题 int pos=0; while(x)//把数拆分至a数组中 { a[++pos]=x%进制; x/=进制; } return dp(pos/*从最高位开始枚举*/,/*一系列状态 */,true,true);//刚开始默认为有限制且有前导0 } int main() { ll l,r; memset(f,-1,sizeof f);//初始化 cin>>l>>r; printf("%lld\n",solve(r)-solve(l-1)); return 0; }

对于limit的理解：假如我们当前遍历到第pos位，那么当前位置的取值有两种可能性：

（1）如果pos前面某一位已经小于上限数字对应位置的数字，这一位可以填0~进制数-1

（2）如果pos前面每一位都等于上限数字对应位置的数字，这一位可填充数字范围位0~上限数字对应位置的数字

而limit就是维护前面每一位是否和上限数字一样，就可以得到当前位置数字可填范围，也是可以进行记忆化搜索的条件

那为什么记忆化搜索一定要在可以任选的情况下进行呢？下面看下递归语句

ans+=dfs(pos-1,/*状态转移*/,lead&&i==0,limit&&i==a[pos]);

如果可以任选了，首先有lead=0，这个很显然，都可以任选了，说明前面一定有一位不是上界，而且limit=0，这样在之后的所有可选数上限都会是进制数-1，这样的状态上限是唯一的，而且是容易存储的，所以当这样的结果已经被保存下来就可以直接作为结果返回而不需要再次进行搜索，这就是dp的记忆化搜索部分，也是精髓

下面我来说一下前导0的影响：

有些题目需要考虑前导0，而有些题目不需要考虑前导0（这主要取决于答案的数量是否与0有关）

先说一下什么是前导0，比如x=9999，小于x的数包括一位数，二位数，三位数，四位数，由于我们数位DP是按照位来枚举的，所以一位数3默认为0003，但这属于包含了前导0

需要考虑前导0的题目一般是结果与0有关的，举个例子，假如我们要求[l,r]中有多少个数满足二进制表示中0的个数大于等于1的个数，显然我们记忆化数组中需要记录0的和1的个数，但是这个时候前导0就会对答案产生影响了，因为前导0并不是真实存在的，只是为了我们方便表示一个数来设置的，他不应该被计入当前数的二进制表示中0的个数，所以就需要我们在搜索过程中单独处理一下，当然也有一些题目是不会被前导0影响的，比如不要62，意思就是求[l,r]中满足十进制表示中不包含4和“62”的数有多少，这个显然与0无关，所以他不会受前导0的影响，我们只需要记录当前位前一位即可进行记忆化搜索。

下面我给出这两道题目的链接及代码：

3252 — Round Numbers

代码：

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<queue> using namespace std; typedef long long ll; const int N=35; ll f[N][N][N];//f[i][j][k]表示遍历到第i位有j个0以及k个1的合法方案数 ll a[N]; ll dp(int pos,int num0,int num1,int lead,int limit) { if(!pos) return num0>=num1; if(!lead&&!limit&&f[pos][num0][num1]!=-1) return f[pos][num0][num1]; int up=limit?a[pos]:1; ll ans=0; for(int i=0;i<=up;i++) { if(lead)//有前导0 ans+=dp(pos-1,num0,num1+(i!=0),lead&&(i==0),limit&&i==up); else ans+=dp(pos-1,num0+(i==0),num1+(i!=0),lead,limit&&i==up); } if(!lead&&!limit) f[pos][num0][num1]=ans; return ans; } ll solve(ll x) { int pos=0; if(!x) return 1; while(x) { a[++pos]=x%2; x/=2; } return dp(pos,0,0,1,1); } int main() { ll l,r; memset(f,-1,sizeof f); cin>>l>>r; cout<<solve(r)-solve(l-1); return 0; } 

不要62（杭电进不去了，我就放上题意吧）

题意：

Input

输入的都是整数对n、m（0<n≤m<），如果遇到都是0的整数对，则输入结束。

Output

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

Sample Input

80

代码：

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<queue> using namespace std; const int N=203; typedef long long ll; ll f[N][10],a[N]; ll dp(int pos,int last,int limit) { if(!pos) return 1; if(!limit&&f[pos][last]!=-1) return f[pos][last]; int up=limit?a[pos]:9; ll ans=0; for(int i=0;i<=up;i++) { if(last==6&&i==2) continue;//剪枝 if(i==4) continue;//剪枝 ans+=dp(pos-1,i,limit&&(i==up)); } if(!limit) f[pos][last]=ans; return ans; } ll solve(ll x) { if(!x) return 1; int pos=0; while(x) { a[++pos]=x%10; x/=10; } return dp(pos,0,1); } int main() { ll l,r; memset(f,-1,sizeof f); while(scanf("%lld%lld",&l,&r)&&(l||r)) { printf("%lld\n",solve(r)-solve(l-1)); } return 0; }

通过这道多组输入题我还想给大家说一个技巧，就是一个数是否满足题目中要求的条件是一定的，不会随着查询区间的变化而变化，所以我们在对f数组进行初始化时只需要在最开始初始化一次即可。

这就是我对数位DP的理解了，在之后我还会更新一些有关数位DP的题目，希望能够帮助到大家！