数位

思想

其本质思想是暴力从高位到低位枚举每一个数,用记忆化记录答案。

因为根据题目的要求，这种搜索方式会导致大量的状态重复。

实现

我们用 表示每一个状态，可见状态数比较少。

如果搜索时发现 已经搜过，就直接返回。

代表当前搜到哪一位， 代表当前位是否有限制。

举个栗子：数是 ，当前枚举到第 位，前一位枚举的是 ，则 ， 下一位可取 ~ ，否则 ，下一位可取 ~ 。

关于 的内容，视题目而定。

几个常用的状态：

表示取的前一个数是什么；

_ 表示之前选的数是否全是 （防止前导零）；

表示之前取的所有数的和。

例题

loj #10163. 「一本通 5.3 例 1」Amount of Degrees

首先对数 进行 进制分解。需要记录的状态为当前取了多少为为 。然后需要注意的是，这题的问题不具有可减性，有上界也有下界，需同时记录两种 。

对于下面几题，都可以将 的问题转换成

#10164. 「一本通 5.3 例 2」数字游戏

板子题，需要记录上一位取的数 。

#10165. 「一本通 5.3 例 3」Windy 数

同上，记录上一位 ，需注意前导零的处理。

#10166. 「一本通 5.3 练习 1」数字游戏

记录之前选的数的总和 。

#10167. 「一本通 5.3 练习 2」不要 62

记录上一位，同时不选 。

#10168. 「一本通 5.3 练习 3」恨 7 不成妻

原理同 ，较为复杂，因为要求满足条件的数的平方和，可以用数组记录平方和和一次和用来递推。

#10169. 「一本通 5.3 练习 4」数字计数

需记录是否前导零和当前状态有多少数，用于统计。

比如当前取到 ，（先不考虑前导零），当前选了 ，那么这个 就被算了 && 次。