学习笔记：数位 dp

参考文献

算法学习笔记(22)：数位DP（数位动态规划）

前置知识

1. 动态规划

引入

现有一个问题，要求在一个区间范围内解决满足某种约束的数字的和、积、异或和等，且该区间范围极大。

要解决这类问题，常规的动态规划显然会因为最低线性的时间复杂度，导致无法满足时间复杂度需求。

因此，我们可以考虑从数位入手，将线性处理的角度转为 $\log$。

思路

数位 dp 有个通用的套路，就是先采用前缀和思想，将求解“$[l,r]$ 这个区间内的满足约束的数的数量”，转化为“$[1,r]$ 满足约束的数量减去 $[1,l-1]$ 区间满足约束的数量“

所以我们最终要求解的问题通通转化为：$[1,x]$ 中满足约束的数量，或者 $[0,x]$ 中的满足约束的数量（左边界取决于题目）

然后将数字 $x$ 拆分为一个个数位，dp 求解

解决方法

迭代法：

使用传统 dp 的方法，但是每道题都要重新设计 dp，常数也相对较大，故不推荐使用

记忆化搜索法：

每层搜索填写一个数，从高位往低位填

用 $p$ 进制表示 $x$，设 $x=\sum_{i=1}^{len}a_ip^{i-1}$，其中 $len$ 是 $x$ 在 $p$ 进制下的位数

在搜索的过程中，我们用 $pos$ 表示当前枚举到的位数

例：

洛谷P4999 烦人的数学作业

求解区间 $[l,r]$ 中所有数的数位和之和

共 $1\leq T\leq 20$ 组数据，其中 $1\leq L\leq R\leq 10^{18}$

首先将问题转换成求解区间 $[0,x]$ 内所有数的数位和之和

假设 $x=4132$，我们用 $?$ 来表示还没有填的数位，则初始状态为 $????$

第一步填写最高位，显然只能填写 $0\sim4$

• 若填写的数大于 $4$，得出的 $????$ 不可能处在 $[0,4132]$ 的范围内
• 若填写的数为 $1\sim3$，后面几位可以随意填写，无论如何都在 $[0,4132]$ 范围内
• 若填写的数刚好为 $4$，则后面几位仍要受到限制

所以我们记录一个变量 $lim$，表示当前位是否还受限制

所以每次可填写的数字上限为

$$\begin{cases} x_i,&\text{if }lim=1\\ 9,&\text{otherwise} \end{cases}$$

显然当我们搜索到 $pos=0$ 时，所有的数位都被填写完毕

为了计算总和，我们增加一个传入的参数 $sum$，表示 [$pos+1，len]$ 的数位和 ，当 $pos=0$ 时就返回传入的 $sum$

现在上述部分可以用简单的深搜解决，但其递归结构形似满二叉树，最坏时间复杂度达 $1e18$，显然无法接受

因此我们采用记忆化搜索，设计状态 $f[pos][sum]$ 表示位置 $[pos+1,len]$ 都已经填写完毕，且数位和为 $sum$ 时，数位 $[1,pos]$ 任意填写时满足约束的所有数的数位和

因此对于形同 $13??,12??,04??,30??$ 这一类共同的状态时，我们可以直接查表返回答案，只需要计算一次，减少大量冗余运算。

因而可以写出大致的代码

int dfs(int pos , int sum , bool lim)
{
	if(!pos) return sum;
    if(!lim && ~f[pos][sum]) return f[pos][sum];
    int up = lim ? a[pos] : 9;
    long long res = 0;
    for(int i = 0 ; i <= up ; i++) (res += dfs(pos - 1 , lim && i == up , sum + i)) %= mod;
    if(!lim) f[pos][sum] = res; return res;
}

然后只需要在 solve 函数中调用即可

void solve(int x)
{
    int len = 0;
	while(x) a[++len] = a % 10 , x /= 10;
    return dfs(len , 0 , 1);
}

复杂度证明

考虑 $f$ 的状态数，$pos$ 的值不超过 $19$，$sum$ 的值不超过 $18*9+1=163$，因而状态数最大为 $163*19=3097$，处在一个相当小的数量级，而每个状态计算值的时候最多访问 $10$ 个状态，因而该部分时间复杂度不超过 $30970$

搜索方面，若 $lim$ 为 $0$，则显然复杂度与上述一致，且 $lim$ 为 $1$ 的节点数量是很少的

因此最终的复杂度为 $O(len\times sum\times p)$