Readme

3490.Count-Beautiful-Numbers

常见的数位DP或者递归搜索。本质我们需要设计一个函数count(T)来记录0-T之间所有符合条件的数。

因为beautiful number最多只有10位，每个位置最多只有0-9共十种填法，我们可以逐位搜索。搜索过程中，第pos个位置上的可选决策受到两个先前状态的制约：

1. 该位置是否贴近上限T。如果pos之前的选择都是贴着上限T，那么在第pos位上，我们的选择上限也只能是T[pos]，否则上限可以是9.
2. 该位置是否是先导零。如果pos之前的选择全部都是0，那么在pos位置之前记录的乘积应该强制认作是1。这么做是为了处理这样一种情况：pos之前都是0，并且pos位也想取零。如果没有这条规则，那么递归到后面的乘积就永远是零了。

由此，我们一旦做出了pos位置上的决策，在往后递归的时候，也需要相应更新isTight和isLeadingZero这两个状态。

递归需要记忆化的支持。本题记忆化的状态就是递归函数的参数：pos, sum, product, isTight, isLeadingZero。我们可以用tuple作为key，加上有序map来存储访问过的状态。

有人会问product的个数会不会很大？事实上9个digit想乘，可以得到的不同的乘积并不大。

st = {1}  # 空集的乘积（乘法单位元）
for _ in range(9):  # 9 个数相乘
    st = set(x * d for x in st for d in range(10))  # 每个数从 0 到 9
print(len(st))  # 3026

总的记忆化状态数目最多9*81*3000*2*2=8748000，恰好可以接受。