数位 DP 详解

定义

数位 DP 是一种用于数字数位统计的 DP，是一种简单的 DP 套路题。（其实一点都不简单……）

详细做法

数位 DP 的原理其实很简单，就是按照从高到低每一位进行分类，比如说 $324$ 这个数，按照数位 DP 的方法就会分成这样：

注意看我标红的部分，是不是很直观的体现了数位 DP 的分类方法。

其中，有一段区间我用很显眼的绿色标识了出来，这是为什么呢？

仔细看这一段区间，是不是与其他的都不一样？这就是为什么我要把它标绿，因为其他区间都是整个范围，而只有最后一段区间有一个上限：$324$。因为我们统计的就只有 $324$ 以内的，如果再算 $300\to 399$，就不满足题意了，于是我们 DP 的第一个其余参数：$limit$（中文意思：限制），出现了！

这个参数是个布尔值，也就是只有两种状态：有限制与无限制。没有限制就可以一直往上走，有了就不行（就像 $300\to 324$ 一样）。

然后我们来看看 DP 数组中的第二个其余参数：$lead$（中文意思：领导）。我们看第一个区间：$000\to 099$，你不觉得奇怪吗？$000$ 是什么东西？$099$ 又是什么东西？问题就出在了这儿：前导 $0$！所以 $lead$ 这个参数也是一个布尔值，就是用来存储有无前导 $0$。

我们之前说过：DP 有两种写法，一种递推，一种记忆化搜索。而对于数位 DP 来讲，最常写也最方便的莫过于记忆化搜索写法，递推不是不可以，就是太难理解了。

为了方便讲解，我们拿一道经典例题讲讲：

洛谷 P2602

题目：给定两个正整数 $a$ 和 $b$，求在 $[a,b]$ 中的所有整数中，每个数码(digit)各出现了多少次。
输入格式：仅包含一行两个整数 $a,b$，含义如上所述。
输出格式：包含一行十个整数，分别表示 $0\sim 9$ 在 $[a,b]$ 中出现了多少次。
数据规模与约定：
对于 $100\%$ 的数据，保证 $1\le a\le b\le 10^{12}$。

对于基础的数位 DP，我们肯定要定义一个 dp[pos]，表示当前在第 $pos$ 位，对于这道题，我们还要多定义一维：$sum$（英文全称 summation，中文意思：总和），表示当前有多少个指定数字，具体意思详见代码或状态转移方程。

然后我们就可以开始写代码了。

有人问：为啥不写状态转移方程。原因：干写太难写了，结合者代码好点。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,now,len,num[16],dp[16][16][2][2];
int dfs(int id,int sum,bool lead,bool limit)
{int ans=0;if(id==0)//到第 0 位了……{return sum;}if(dp[id][sum][lead][limit]!=-1)//经典记忆化搜索{return dp[id][sum][lead][limit];}int n=(limit?num[id]:9);//判断这一位有没有限制，如果有，取出当前这一位的数，也就是这一位能达到的最大的数，否则就是 9for(int i=0;i<=n;i++)//循环当前这一位能取哪些数，记录答案{if(i==0&&lead)//有前导 0（前面有，这一位也是 0）{ans+=dfs(id-1,sum,true,limit&&i==n);//如果这一位有限制且正好循环到上限，那么下一位也会有限制//如 324，如果当前已经到 320（也就是当前这一位最大了），那么接下来的范围就只有 320~324//如果到了310（也就是当前这一位还没到最大），那就没什么}else if(i==now)//算到目标数字了，也没有前导 0{ans+=dfs(id-1,sum+1,false,limit&&i==n);//计数加一}else if(i!=now)//其他情况，没有前导 0{ans+=dfs(id-1,sum,false,limit&&i==n);}}dp[id][sum][lead][limit]=ans;//记忆化搜索return ans;//返回答案
}
int solve(int x)
{memset(dp,-1,sizeof(dp));len=0;while(x)//求数的长度，以确定当前在哪一位{num[++len]=x%10;x/=10;}//为了方便后续写代码，我们一般会在意识里的原数前面多加一位 0，实际上是没有的return dfs(len,0,true,true);//于是就有了前导 0 与限制
}
signed main()
{cin>>a>>b;for(int i=0;i<10;i++)//统计每一个数{now=i;cout<<solve(b)-solve(a-1)<<" ";//一个类似前缀和的做法}return 0;
}

如果你看完代码感觉明白了，那恭喜你，你已经大致掌握了数位 DP 了！其他的题目大致就是把这几个参数改来改去就对了。没理解的同学我也没法再跟你解释了，因为数位 DP 就这样，实在不行多读几遍就懂了。（人生导师上线：当时我初学数位 DP 的时候，我直接被绕晕了，一直没搞懂这个上限、前导 $0$ 的处理，直到翻开书的第三遍，我“不小心”把书翻烂了……不重要，重要的是我学懂了数位 DP。）

例题

洛谷 P2657

题目描述：不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 windy 数。windy 想知道，在 $a$ 和 $b$ 之间，包括 $a$ 和 $b$ ，总共有多少个 windy 数？
输入格式：输入只有一行两个整数，分别表示 $a$ 和 $b$。
输出格式：输出一行一个整数表示答案。
数据规模与约定：对于全部的测试点，保证 $1\le a\le b\le 2\times 10^9$。

跟上面那道例题很像，改一下 $sum$ 的意义就行了。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,len,num[16],dp[16][16][2][2];
int dfs(int id,int last,bool lead,bool limit)
{int ans=0;if(id==0){return 1;}if(dp[id][last][lead][limit]!=-1){return dp[id][last][lead][limit];}int n=(limit?num[id]:9);for(int i=0;i<=n;i++){if(abs(i-last)<2){continue;}else if(i==0&&lead){ans+=dfs(id-1,-2,true,limit&&i==n);}else{ans+=dfs(id-1,i,false,limit&&i==n);}}dp[id][last][lead][limit]=ans;return ans;
}
int solve(int x)
{memset(dp,-1,sizeof(dp));len=0;while(x){num[++len]=x%10;x/=10;}return dfs(len,-2,true,true);
}
signed main()
{cin>>a>>b;cout<<solve(b)-solve(a-1)<<" ";return 0;
}

洛谷 P4124

题目描述：人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素，从号段中选取含有某些特征的号码单独出售。为了便于前期规划，运营商希望开发一个工具来自动统计号段中满足特征的号码数量。
工具需要检测的号码特征有两个：号码中要出现至少 $3$ 个相邻的相同数字；号码中不能同时出现 $8$ 和 $4$。号码必须同时包含两个特征才满足条件。满足条件的号码例如：13000988721、23333333333、14444101000。而不满足条件的号码例如：1015400080、10010012022。
手机号码一定是 $11$ 位数，且不含前导的 $0$。工具接收两个数 $L$ 和 $R$，自动统计出 $[L,R]$ 区间内所有满足条件的号码数量。$L$ 和 $R$ 也是 $11$ 位的手机号码。
输入格式：输入文件内容只有一行，为空格分隔的 $2$ 个正整数 $L,R$。
输出格式：输出文件内容只有一行，为 $1$ 个整数，表示满足条件的手机号数量。
数据范围：$10^{10}\le L\le R<10^{11}$。

参数稍微多亿点，注意没有前导 $0$！

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,len,num[16],dp[16][16][16][2][2][2][2];//这数组……
int dfs(int id,int last,int llast,bool x,bool is4,bool is8,bool limit)
//当前在第几位，上一个是什么数，上上个是什么数，是否有三个连续相同的数，出现 4 没有，出现 8 没有，有没有限制
{int ans=0;if(is4&&is8){return 0;}if(id==0){return x;}if(dp[id][last][llast][x][is4][is8][limit]!=-1){return dp[id][last][llast][x][is4][is8][limit];}int n=(limit?num[id]:9);for(int i=0;i<=n;i++){ans+=dfs(id-1,i,last,x||(i==last&&i==llast),is4||i==4,is8||i==8,limit&&i==n);}dp[id][last][llast][x][is4][is8][limit]=ans;return ans;
}
int solve(int x)
{memset(dp,-1,sizeof(dp));len=0;while(x){num[++len]=x%10;x/=10;}if(len!=11){return 0;}int ans=0;for(int i=1;i<=num[len];i++){ans+=dfs(len-1,i,0,0,i==4,i==8,i==num[len]);}return ans;
}
signed main()
{cin>>a>>b;cout<<solve(b)-solve(a-1)<<" ";return 0;
}