笔记汇总

数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：

• 要求统计满足一定条件的数的数量（即，最终目的为计数）

• 这些条件经过转化后可以使用「数位」的思想去理解和判断

• 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制

• 上界很大（比如 $10^9$），暴力枚举验证会超时

核心思想：按数位枚举 统计区间内符合要求的数。

统计答案

本文采用 记忆化搜索 的方式解决 数位 DP

• 从高往低枚举：确定上限，不重不漏地统计所有不超过上限的答案。

*