数位 DP - 知识点梳理

本质上是一种基于数位的线性 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 本身却有很多奇妙的方法。这里提供一些常用的数位处理方法。

同时，数位 DP 作为一种线性 DP，有时可以结合处理字符串的一些方法。
这是一道例题：Luogu P2481 [SDOI2010] 代码拍卖会
我们要求一个长度为 \(n\) 的单调不减序列，且整个序列的位值和能被 \(p\) 整除。
考虑求这个序列的差分序列。差分序列中都为正数，且和都不超过 \(9\)。
然后尝试满足被 \(p\) 整除的条件。利用位值原理，差分序列中每个数对于整个数的模数贡献是该数乘以它会影响到的数的位值和，直接求解即可。
这样这个问题就被转化成了背包问题，枚举每个 \(1\) 放的位置，使用数位 DP 进行优化。（所以为什么要把数位 DP 单独作为一个算法？）

总结

数位 DP 是一种特殊的基于字符串的线性 DP，处理时可以使用处理字符串的一些方法，和线性 DP 的一些方法，说明它会和其他 DP 类优化进行搭配。数位 DP 通常用于解决区间统计类问题。