數位dp

應用場所：

大多應用于求解一段很長的區間內，符合條件的數的個數。一般情況是用于計數問題。

先看一個模板題：

令 \(dp_i\) 表示滿 \(i\) 位數每個數字的個數。
為什么不用單獨討論不同的數字？
因為對于不考慮前導零而言，滿 \(i\) 位數的所有數字中數字 \(j\) 出現的次數是相同的。
轉移 \(dp_i=dp_{i-1}\times 10+10^{i-1}\)

證明：

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\) 次