英语+数位DP

记了1个list单词

数位DP：基于数字的每一位进行状态转移和递推

数位DP（Digit DP），通过拆分一个数的每一位来进行状态转移，从而解决涉及数字限制（如范围内的数字，满足某些条件的数字等）的计数问题。

1.数字的拆解：通常将数字从高位到低位拆解成每一位，这样就可以对每一位进行状态转移，逐步构建答案。

2.状态定义：由当前处理到的位置、是否还受到限制以及其他需要记录的条件构成。

3.递推与记忆化：对于每一位数字，根据当前状态递推下一个状态。为了避免重复计算，通常使用记忆化搜索存储已经计算过的状态。

4.边界条件与初始化：递归的边界条件是处理完所有的数字位或者符合要求的数字已经被找到了。

一般求某些 \([a,b]\) 区间内的某些性质的数量，看是否满足区间减法。满足即可将求解 \(f[a,b]\)转化为求解 \(f[0,b]-f[0,a-1]\) 。

• 预处理 \(f\) 数组。
• \(f[i,st]\) 代表 位数为 \(i\) （可能允许前导0，如0001），状态为 \(st\) 的方案数。
• 如 \(i=4,f[i][st]\) 也就是 \(0000~9999\) 的符合条件的数的个数
• 决策第 \(i\) 位是多少
• \[f[i,st]=f[i,st]+f[i-1,st^{']}\]

Hdu2089 不要62

题意：给定区间 \([n,m]\)，求在 \(n\) 到 \(m\) 中没有 “62” 或 “4” 的数的个数。

题解：\(f[i,j]\) 代表开头是 \(j\) 的 \(i\) 位数中不含 “62” 或 “4” 的数有几个。