今天秤涩，我向大家介紹一種特殊的DP類型——數(shù)位DP帜乞。
數(shù)位DP這類題目一般不會出現(xiàn)在提高組及以下的比賽中（今后出現(xiàn)了當我沒說【滑稽】），更可能出現(xiàn)在省選及更高級別的比賽上筐眷，但是還是挺好理解的一種動態(tài)規(guī)劃類型黎烈。
題目模型
這種動規(guī)問題特殊在哪里呢？數(shù)位DP匀谣，顧名思義照棋，這是一種用于處理“數(shù)字”的DP類型。換句話說武翎，數(shù)位DP的問題模型可以簡化為給出一個下限a烈炭，一個上限b，求[a,b]中滿足題意的數(shù)有幾個宝恶。
解決方法
既然是“數(shù)字”的問題符隙，那解決方法必然也和”數(shù)字“有關(guān)。
1卑惜、我們可以對數(shù)字的每一位進行動規(guī)膏执，枚舉滿足條件的數(shù)字每一位可以是多少。
2露久、判斷當前數(shù)字是否超過上限的對應(yīng)數(shù)字更米。如果沒有的話，那么接下來的數(shù)字可以任意群梁邸征峦；如果等于上限的對應(yīng)數(shù)字，那么接下來的數(shù)字最大只能等于對應(yīng)的數(shù)字消请。這樣栏笆，上限的問題就解決了。
3臊泰、可以采用前綴和的思想蛉加，用[0,b]的答案減去[0,a-1]的答案，這樣下限的問題也解決了。 舉個栗子通過文字來介紹數(shù)位DP针饥，非常抽象厂抽。按照慣例，我們還是通過幾道例題來深入了解一下數(shù)位DP（題目來源洛谷丁眼，侵刪）筷凤。
洛谷P2657
這道題是經(jīng)典的數(shù)位DP類型的題目。
閱讀題目發(fā)現(xiàn)苞七，我們要求在區(qū)間[A, B]上藐守，滿足無前導(dǎo)零且相鄰數(shù)字相差大于等于2的數(shù)字個數(shù)。這符合我們對數(shù)位DP的認知蹂风。我們計算[0, B]的答案卢厂，減去[0, A - 1]的答案，這樣就把下限處理好了硫眨。 接下來足淆，我們思考如何計算[0, B]之間的windy數(shù)。 首先礁阁，我們要先把B拆開存在數(shù)組里巧号，方便后續(xù)對B的每一個數(shù)字的使用。
for (len = 0; x; x /= 10) a[++len] = x % 10;
如果不考慮上限姥闭，我們顯然可以很快求出以i開頭丹鸿，長度為j的數(shù)字中，windy數(shù)的數(shù)量棚品，轉(zhuǎn)移方程如下：
顯然靠欢，位數(shù)小于B的windy數(shù)可以通過f數(shù)組來求出來
for (int i = 1; i < len; ++i)
for (int j = 1; j <= 9; ++j)
sum += s[i][j];
位數(shù)等于B，但是第一個數(shù)字小于B的windy數(shù)也可以通過f來快速求出铜跑。
for (int i = 1; i < a[len]; ++i) sum += s[len][i];
接下來就是數(shù)位DP中最容易繞暈的部分了门怪，因為我們要開始考慮上界對問題的影響了。
由于最高位小于上界的已經(jīng)處理過了锅纺，所以現(xiàn)在我們要處理的數(shù)最高位一定和上界相同掷空。那么是不是轉(zhuǎn)化成一個子問題了呢？
for (int i = len - 1; i >= 1; --i) {
for (int j = 0; j < a[i]; ++j) {
if (abs(j - a[i + 1]) >= 2)
sum += s[i][j];
}
if (abs(a[i] - a[i + 1]) < 2) break;
if (i == 1) sum++;
}
數(shù)位DP的題目大多比較相似囤锉，我就不再多舉例了坦弟。
需要注意的是，處理這類題目的時候官地，要想清楚什么時候會碰到上限酿傍，什么時候可以不考慮上限快速求解，同時還要注意邊界情況驱入。
最后的最后赤炒，動規(guī)題目的精髓在于多看氯析，多練。
【信息學(xué)競賽從入門到巔峰】可霎，一個專注于分享OI/ACM常用算法及知識的公眾號魄鸦。
