数位 DP 入门与应用

## 数位 DP 简介 在我眼里，数位 DP 也就是一个有小技巧的一个 DP，本质上其实也是 DP，或者说是计数？但是两者都需要考察选手对于数位的理解能力，尤其是“标记”的处理。 对此写了一个与数位 DP 相关的[专栏](https://www.luogu.com.cn/article/vyvrgzea)，欢迎拜访。 ## 计数 不需要什么标记，只需要计数能力，而且几乎没有技巧，可以加深对于 $[0,m]$ 之间计数的理解。 - [P2602](/problem/P2602)，应该是最经典的一道，有两种写法，其中一种就是 “计数” DP。 - [B3883](/problem/B3883)，也许是第二典的一道，稍微推导还可以使用计数方式解决。 ## 记忆化搜索 这就需要考察选手对于标记的理解能力，具体来说就是从高位向低位 DP 的过程中维护一个标记表示“前面有没有卡满原数字”。这种 DP 一般使用记忆化搜索实现。 同样的，一些复杂的题目可能还需要对前导零处理。 但是这个标记在简单问题上是可以直接优化掉的，因为在标记存在的时候后面都是可以随便填写的了。 - [P2657](/problem/P2657)，记忆化搜索带标记典题，可以尝试独立思考，需要前导零标记。 - [P9821](/problem/P9821)，需要同时维护两个数字，本质不难。 - [P10959](/problem/P10959)，枚举一开始不好同时维护的东西使得可以进行数位 DP。弱化版 [P4127](problem/P4127)。加强版可以通过使用枚举 LCP 来优化，当然也可以记忆化搜索。 - [CF1734F](/problem/CF1734F)，比较基础的加法进位练习题，维护进位标记有两种做法，一种是强制进位的个数，另一种是目前进位的个数，通常选择后者，这更符合我们的数学直觉。 - [CF55D](/problem/CF55D)，数位 DP 在很多情况下状态数量都很多，但是实际合法的状态确很少，这时候可以使用哈希表优化。或者预处理状态。同时这个需要结合状态压缩。 - [CF1194G](/problem/CF1194G)，数位 DP 如果在数字较小的情况下也是可以使用乘法的，其进位思路与加法的思路相同。 - [P4067](/problem/P4067)，这种 $\max$ 通常可以拆贡献，变成符合某种条件（这里是 $\ge k$）的数的个数或者总和。 到这里基本就可以处理一些简单的数位 DP 了。 ## 与其他内容的结合 此处并不保证是纯正的数位 DP，但是由于应用可能真的很典型，因此出现在了这个题单中。 - [P8688](/problem/P8688)，数位 DP 也可以应用于 Lucas 定理，将进制设置为模数即可。同时由于状态转移的量很少，直接计算出转移的方案数量即可，而不是枚举数位。 - [P9387](/problem/P9387)，数位 DP 也可以应用与 Nim 游戏等 SG 函数与数位相关的博弈，转化后是一个加法进位练习题。 - [P7717](/problem/P7717)，数位 DP 的状态也可以是一个自动机节点。这是一个和字典树稍微简单的结合。 - [P9129](/problem/P9129)，与正常数位 DP 的标记不同，标记较为复杂，结合部分区间 DP，代码难度较大。 - [P3188](/problem/P3188)，数位背包，其实也可以用数位 DP 的思想理解，这里的 $a$ 也就相当于进位的数量。 - [AT_arc153_d](/problem/AT_arc153_d)，和进位相关的略简单题，但是状态并不一定是标记等信息。 - [P5772](/problem/P5772)，状压、矩阵、数位 DP 的结合。 - [P3791](/problem/P3791)，可以使用类似于数位 DP 的思路进行分析。 - [P12467](/problem/P12467)，比较简单的题，与轮廓线的结合。 ## 总结 总结就是简单题都会做，复杂题就是一堆东西套一堆东西，所以就可以多刷几道练手。 这里的题目没有难的，因为难的题就要涉及到其他更复杂的东西（比如平面几何），也就只是纯数位 DP。 如果本人做到了或是随到了一些好的题目，也会加入其中，也欢迎各路数位 DP 大神推荐好题。