数位dp
Mizuhara
·
·
个人记录
数位dp
思想
其本质思想是暴力从高位到低位枚举每一个数,用记忆化记录答案。
因为根据题目的要求，这种搜索方式会导致大量的状态重复。
实现
我们用 (pos,status,limit) 表示每一个状态，可见状态数比较少。
如果搜索时发现 (pos,status,limit) 已经搜过，就直接返回。
>举个栗子：数是 $321456$ ，当前枚举到第 $5$ 位，前一位枚举的是 $2$ ，则 $limit = 0 $ ， 下一位可取 $0$ ~ $9$ ，否则 $limit = 1$ ，下一位可取 $0$ ~ $a[pos]$ 。
关于 $status$ 的内容，视题目而定。
几个常用的状态：
>$pre$ 表示取的前一个数是什么；
>$is$_$qian$ 表示之前选的数是否全是 $0$ （防止前导零）；
>$sum$ 表示之前取的所有数的和。
### 例题
**[loj #10163. 「一本通 5.3 例 1」Amount of Degrees](https://loj.ac/problem/10163)**
首先对数 $n$ 进行 $B$ 进制分解。需要记录的状态为当前取了多少为为 $1$ 。然后需要注意的是，这题的问题不具有可减性，有上界也有下界，需同时记录两种 $limit$ 。
**对于下面几题，都可以将 $[l,r]$ 的问题转换成 $[0,r] - [0, l - 1]$**
**[#10164. 「一本通 5.3 例 2」数字游戏](https://loj.ac/problem/10164)**
板子题，需要记录上一位取的数 $pre$ 。
**[#10165. 「一本通 5.3 例 3」Windy 数](https://loj.ac/problem/10165)**
同上，记录上一位 $pre$ ，需注意前导零的处理。
**[#10166. 「一本通 5.3 练习 1」数字游戏](https://loj.ac/problem/10166)**
记录之前选的数的总和 $sum$ 。
**[#10167. 「一本通 5.3 练习 2」不要 62](https://loj.ac/problem/10167)**
记录上一位，同时不选 $4$ 。
**[#10168. 「一本通 5.3 练习 3」恨 7 不成妻](https://loj.ac/problem/10168)**
原理同 $10169$ ，较为复杂，因为要求满足条件的数的平方和，可以用数组记录平方和和一次和用来递推。
**[#10169. 「一本通 5.3 练习 4」数字计数](https://loj.ac/problem/10169)**
需记录是否前导零和当前状态有多少数，用于统计。
比如当前取到 $(pos, limit)$ ，（先不考虑前导零），当前选了 $4$ ，那么这个 $4$ 就被算了 $4 * f[pos - 1][4 == mx $ $&&$ $ limit]$ 次。