本质上是一种基于数位的线性 DP。
通常用于区间统计问题。当暴力枚举会超时，数位 DP 可以对区间的值进行按位求解，有时使用位值原理，把每位上相同的数一起求解，降低时间复杂度，有时会用到高位优先的贪心思想。
实现
Luogu P4124 [CQOI2016] 手机号码
这就是一个区间统计问题。如果暴力枚举肯定会超时，现在考虑优化。
暴力枚举时，我们在判断下一位可能的值时，会检测已经确定的位是否出现了 \(4\) 或 \(8\)，前面有没有连续 \(3\) 个的数字，还需要多少个数字才可能与当前数字组成连续 \(3\) 个的。当然还有一个不要忘记：已确定的位是否达到了上限。到这你可能有思路了：其实只要这些条件完全相同，我们并不关心前缀具体是什么。也就是说，我们可以把数位拆开，以数位位置以及上方一系列信息作为维度，进行线性 DP，这样就能避免很多重复的访问。
开始设计状态：首先我们需要记录已确定了多少位，然后是否出现了 \(4\) 或 \(8\)，前面有没有连续的 \(3\) 个数字，当前正在连续的是什么数字，当前的连续长度，当前的前缀是否已经达到上限。我们发现，高位的状态依赖于低位的状态，因此从低位往高位一次更新即可。
上代码！ （这里有个小提示：像这种状态顺序容易搞混的题推荐写成记忆化搜索）
#include<bits/stdc++.h>
using namespace std;
long long f[12][2][2][11][12][2][2];
bool have[12][2][2][11][12][2][2];
long long dfs (int rtb[], int id, int top, int cmbed, int cmbid, int cmblen, int have4, int have8) {
if (id == 12) return cmbed;
if (have[id][top][cmbed][cmbid][cmblen][have4][have8]) {
long long ans = f[id][top][cmbed][cmbid][cmblen][have4][have8];
return ans;
}
int tdg = top ? rtb[id] : 9;
long long ans = 0;
for (int i = 0;i <= tdg;i++) {
if (id == 1 && i == 0) continue;
if (i == 4 && have8) continue;
if (i == 8 && have4) continue;
int pcmbed = cmbed, pcmbid = cmbid, pcmblen = cmblen;
if (cmbid == i) {
pcmblen++;
if (pcmblen >= 3) pcmbed = true;
}
else {
pcmbid = i;
pcmblen = 1;
}
ans += dfs (rtb, id + 1, top && (i == tdg), pcmbed, pcmbid, pcmblen, have4 || (i == 4), have8 || (i == 8));
}
have[id][top][cmbed][cmbid][cmblen][have4][have8] = true;
return f[id][top][cmbed][cmbid][cmblen][have4][have8] = ans;
}
int main () {
int l[15], r[15];
long long lt, rt;
cin >> lt >> rt;
lt--;
int p = 11;
while (lt) {
l[p--] = lt % 10;
lt /= 10;
}
p = 11;
while (rt) {
r[p--] = rt % 10;
rt /= 10;
}
long long ansr = dfs(r, 1, 1, 0, 10, 0, 0, 0);
memset(have, 0, sizeof(have));
long long ansl = dfs(l, 1, 1, 0, 10, 0, 0, 0);
cout << ansr - ansl << endl;
return 0;
}
可以看到，数位 DP 利用的是数字处理时前缀不影响后面的情况的性质，只有这样按位设置维度并设置状态才不会有后效性。
拓展应用
数位 DP 的用处仅限于数位 DP 本身，因此不做拓展，但数位 DP 本身却有很多奇妙的方法。这里提供一些常用的数位处理方法。
| 问题 | 应对方法 |
|---|---|
| 整个数要整除一个数 | 状态上记录除法的余数，每过一位乘以 \(10\) |
| 所得数要满足条件且字典序最大/小 | 不要暴力整，学会二分 |
| 整个数太大，不能每位枚举 | 利用暴力数据结构，如分块 |
同时，数位 DP 作为一种线性 DP，有时可以结合处理字符串的一些方法。
总结
数位 DP 是一种特殊的基于字符串的线性 DP，处理时可以使用处理字符串的一些方法，和线性 DP 的一些方法，说明它会和其他 DP 类优化进行搭配。数位 DP 通常用于解决区间统计类问题。