数位dp
应用场所:
大多应用于求解一段很长的区间内,符合条件的数的个数。一般情况是用于计数问题。
先看一个模板题:
令 \(dp_i\) 表示满 \(i\) 位数每个数字的个数。
为什么不用单独讨论不同的数字?
因为对于不考虑前导零而言,满 \(i\) 位数的所有数字中数字 \(j\) 出现的次数是相同的。
转移 \(dp_i=dp_{i-1}\times 10+10^{i-1}\)
证明:
- 递推证明:对于一个数字 \(j\) 以计算 \(dp_2\) 为例。计算 \(dp_2\) 时, \(j\) 在个位上出现了 \(dp_{i-1}\times 10 = dp_1\times 10=10\) 次。因为如果只有一位的话不管是什么数字都只出现了一次。而 \(j\) 在十位上出现了 \(10^{i-1}=10^{2-1}=10\) 次