数位 DP
本页面将简要介绍数位 DP．
引入
数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字．如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制．
数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：
- 要求统计满足一定条件的数的数量（即，最终目的为计数）；
- 这些条件经过转化后可以使用「数位」的思想去理解和判断；
- 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
- 上界很大（比如 10181018
），暴力枚举验证会超时．
数位 DP 的基本原理：
考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一．但我们发现对于位数比较多的数，这样的过程中有许多重复的部分．例如，从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里．此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移．
数位 DP 中通常会利用常规计数问题技巧，比如把一个区间内的答案拆成两部分相减（即 ans[𝑙,𝑟] =ans[0,𝑟] −ans[0,𝑙−1]ans[l,r]=ans[0,r]−ans[0,l−1]）
那么有了通用答案数组，接下来就是统计答案．统计答案可以选择记忆化搜索，也可以选择循环迭代递推．为了不重不漏地统计所有不超过上限的答案，要从高到低枚举每一位，再考虑每一位都可以填哪些数字，最后利用通用答案数组统计答案．
接下来我们具体看几道题目．
例题一
例 1 Luogu P2602 数字计数
题目大意：给定两个正整数 𝑎,𝑏a,b，求在 [𝑎,𝑏][a,b] 中的所有整数中，每个数码（digit）各出现了多少次．
方法一
解释
发现对于满 ii 位的数，所有数字出现的次数都是相同的，故设数组 dp𝑖dpi 为满 𝑖i 位的数中每个数字出现的次数，此时暂时不处理前导零．则有 dp𝑖 =10 ×dp𝑖−1 +10𝑖−1dpi=10×dpi−1+10i−1，这两部分前一个是来自前 𝑖 −1i−1 位数字的贡献，后一个是来自第 𝑖i 位的数字的贡献．
有了 dpdp 数组，我们来考虑如何统计答案．将上界按位分开，从高到低枚举，不贴着上界时，后面可以随便取值．贴着上界时，后面就只能取 00 到上界，分两部分分别计算贡献．最后考虑下前导零，第 𝑖i 位为前导 00 时，此时 11 到 i−1i−1 位也都是 00，也就是多算了将 𝑖 −1i−1 位填满的答案，需要额外减去．
实现
参考代码
---|---
### 方法二
#### 解释
此题也可以使用记忆化搜索．dp𝑖dpi 表示不贴上限、无前导零时，位数为 𝑖i 的答案．
详见代码注释
#### 过程
参考代码
---|---
例题二
例 2 HDU 2089 不要 62
题面大意：统计一个区间内数位上不能有 4 也不能有连续的 62 的数有多少．
解释
没有 4 的话在枚举的时候判断一下，不枚举 4 就可以保证状态合法了，所以这个约束没有记忆化的必要，而对于 62 的话，涉及到两位，当前一位是 6 或者不是 6 这两种不同情况计数是不相同的，所以要用状态来记录不同的方案数．dppos,stadppos,sta 表示当前第 pospos 位，前一位是否是 6 的状态，这里 stasta 只需要取 0 和 1 两种状态就可以了，不是 6 的情况可视为同种，不会影响计数．
实现
参考代码
---|---
## 例题三
例 3 [SCOI2009 windy 数](https://loj.ac/problem/10165)
题目大意：给定一个区间 [𝑙,𝑟][l,r]，求其中满足条件 **不含前导 00 且相邻两个数字相差至少为 22** 的数字个数．
### 解释
首先我们将问题转化成更加简单的形式．设 ans𝑖ansi 表示在区间 [1,𝑖][1,i] 中满足条件的数的数量，那么所求的答案就是 ans𝑟 −ans𝑙−1ansr−ansl−1．
对于一个小于 𝑛n 的数，它从高到低肯定出现某一位，使得这一位上的数值小于 𝑛n 这一位上对应的数值．而之前的所有位都和 𝑛n 上的位相等．
有了这个性质，我们可以定义 𝑓(𝑖,𝑠𝑡,𝑜𝑝)f(i,st,op) 表示当前将要考虑的是从高到低的第 𝑖i 位，当前该前缀的状态为 𝑠𝑡st 且前缀和当前求解的数字的大小关系是 𝑜𝑝op（𝑜𝑝 =1op=1 表示等于，𝑜𝑝 =0op=0 表示小于）时的数字个数．在本题中，这个前缀的状态就是上一位的值，因为当前将要确定的位不能取哪些数只和上一位有关．在其他题目中，这个值可以是：前缀的数字和，前缀所有数字的 gcdgcd，该前缀取模某个数的余数，也有两种或多种合用的情况．
写出 **状态转移方程** ：𝑓(𝑖,𝑠𝑡,𝑜𝑝) =∑maxx𝑘=1𝑓(𝑖 +1,𝑘,𝑜𝑝 =1 and 𝑘 =maxx) (|st −𝑘| ≥2)f(i,st,op)=∑k=1maxxf(i+1,k,op=1 and k=maxx)(|st−k|≥2)
这里的 𝑘k 就是当前枚举的下一位的值，而 maxxmaxx 就是当前能取到的最高位．因为如果 op =1op=1，那么你在这一位上取的值一定不能大于求解的数字上该位的值，否则则没有限制．
我们发现，尽管前缀所选择的状态不同，而 𝑓f 的三个参数相同，答案就是一样的．为了防止这个答案被计算多次，可以使用 [记忆化搜索](../memo/) 的方式实现．
### 实现
参考代码
---|---
例题四
例 4.SPOJMYQ10
题面大意：假如手写下 [𝑛,𝑚][n,m] 之间所有整数，会有多少数看起来和在镜子里看起来一模一样？（𝑛,𝑚 <1044,𝑇 <105n,m<1044,T<105）
解释
注：由于这里考虑到的镜像，只有 0,1,80,1,8 的镜像是自己本身．所以，这里的「一模一样」并不是传统意义上的回文串，而是只含有 0,1,80,1,8 的回文串．
首先，在数位 DP 过程中，显然只有 0,1,80,1,8 能被选中．
其次，由于数值超过 long long 范围，所以 [𝑛,𝑚] =[1,𝑚] −[1,𝑛 −1][n,m]=[1,m]−[1,n−1] 不再适用（高精度比较繁琐），而是需要对 𝑛n 是否合法进行判断，得出：[𝑛,𝑚] =[1,𝑚] −[1,𝑛] +check(𝑛)[n,m]=[1,m]−[1,n]+check(n)．
镜像解决了，如何判断回文？
我们需要用一个小数组记录一下之前的值．在未超过一半的长度时，只要不超上限就行；在超过一半的长度时，还需要判断是否和与之「镜面对称」的位相等．
需要额外注意的是，这道题的记忆化部分，不能用 memset，否则会导致超时．
实现
参考代码
---|---
## 例题五
例 5.[P3311 数数](https://www.luogu.com.cn/problem/P3311)
题面：我们称一个正整数 𝑥x 是幸运数，当且仅当它的十进制表示中不包含数字串集合 𝑆S 中任意一个元素作为其子串．例如当 𝑆 ={22,333,0233}S={22,333,0233} 时，233233233233 是幸运数，2333233323332333、20233202332023320233、3223322332233223 不是幸运数．给定 𝑛n 和 𝑆S，计算不大于 𝑛n 的幸运数个数．答案对 109 +7109+7 取模．
1 ≤𝑛 <101201，1 ≤𝑚 ≤100，1 ≤∑𝑚𝑖=1|𝑠𝑖| ≤1500，min𝑚𝑖=1|𝑠𝑖| ≥11≤n<101201，1≤m≤100，1≤∑i=1m|si|≤1500，mini=1m|si|≥1，其中 |𝑠𝑖||si| 表示字符串 𝑠𝑖si 的长度．𝑛n 没有前导 00，但是 𝑠𝑖si 可能有前导 00．
### 解释
阅读题面发现，如果将数字看成字符串，那么这就是需要完成一个多模匹配，自然而然就想到 AC 自动机．普通数位 DP 中，先从高到低枚举数位，再枚举每一位都填什么，在这道题中，我们也就自然地转化为枚举已经填好的位数，再枚举此时停在 AC 自动机上的哪个节点，然后从当前节点转移到它在 AC 自动机上的子节点．
设 𝑓(𝑖,𝑗,0/1)f(i,j,0/1) 表示当前从高到低已经填了 𝑖i 位（即在 AC 自动机上走过了 𝑖i 条边），此时停在标号为 𝑗j 的节点上，当前是否正好贴着上界．
至于题目中的「不包含」条件，只需在 AC 自动机上给每个模式串的结尾节点都打上标记，DP 过程中一旦遇上这些结尾节点就跳过即可．
转移很好想，详见代码主函数部分．
### 实现
参考代码
---|---
此题可以很好地帮助理解数位 DP 的原理．
习题
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Ir1d, Tiphereth-A, greyqz, hsfzLZH1, c-forrest, Early0v0, Henry-ZHR, ksyx, Marcythm, ouuan, StudyingFather, Xeonacid, alphagocc, Alphnia, billchenchina, ChungZH, Enter-tainer, GavinZhengOI, H-J-Granger, iamtwz, isdanni, NachtgeistW, Promise2679, r-value, SamZhangQingChuan, sshwy, thredreams 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用