动态规划，是OI中极其重要的一环。
由于它的重要性，解决问题的广泛性，它衍生出了多种多样的DP。
其中，有一种特别搞人的叫做数位DP
思想
数位DP是通过每一位数字去递推，来统计从在 \([0,a]\) 中，有多少个数满足条件或者有多少种满足某一条件的方案数。
由于有一个统计的上界，所以对我们的DP会有所限制：
当你从低位往高位扫，你不一定能确定到了高位它会不会被限制；
当你从高位往低位扫，你不一定能确定到了低位它需不需要限制。
但是，有一类数位DP却是无拘无束：
Luogu P2106 Sam数
虽然它并不是严格意义上的数位DP（比如Luogu就没有给它数位DP的Tag），但是，它对我们做数位DP是很有启发意义的
为什么这道看着是数位DP的题目这么简单？
因为它题目说的是：
他将一个 k 位 Sam 数称之为 k 阶 Sam 数
一行一个整数 ans，表示 k 阶的 Sam 数的个数
因为它只要求了位数，或者说它要求的区间是 \([10^{k-1},10^k)\) 。
我们的唯一限制是位数是定下来的，每一位是0还是9我们并不关心（当然除了前导0蛤），并没有在每一位上面有什么好纠结的。
这时候我们就想了，既然只对位数有要求，或者只对首位有要求的都比较好求解，那我们是不是可以考虑把我们的问题拆分成若干个这样子的问题呢？
显然是可以的。
核心
对于 \(A=\overline{a_na_{n-1}\dots a_2a_1}\) 我们要统计 \([0,A]\) 中满足条件的数的个数，我们可以把它划分成若干个问题
\([0,A]=[0,a_n*10^{n-1})\cup[\overline{a_n0\dots00},\overline{a_na_{n-1}0\dots00})\cup\dots\cup[\overline{a_na_{n-1}\dots a_20},\overline{a_na_{n-1}\dots a_2a_1})\cup\{\overline{a_na_{n-1}\dots a_2a_1}\}\)
这是它数学的拆分，或者我们把它理解成这样：
前几位锁定了，中间某一位可以从 \(0\) 到 \(a_k\) 选择，后面几位任意选
那么，前几位对于要求的影响是可以提前处理掉的，而且在接着往后处理的时候可以直接继承。
只需要枚举中间的一位，可以用数学或者其他的方法知道有多少可行的数字。
在这里讲道理只能知道思想，重点还是要去看题目。