動(dòng)態(tài)規(guī)劃——數(shù)位DP 學(xué)習(xí)筆記
定義
引入
數(shù)位 DP 往往都是這樣的題型：給定一個(gè)區(qū)間 \([l, r]\)，求這個(gè)區(qū)間中滿足某種條件的數(shù)的總數(shù)。
簡(jiǎn)單的暴力代碼如下：
int ans = 0;
for(int i = l; i <= r; ++i)
if(check(i)) ++ans;
而當(dāng)數(shù)據(jù)規(guī)模過大，暴力枚舉就 \(\mathbb T\) 飛了，因此引入數(shù)位 DP：
概念
數(shù)位（digit）：對(duì)于十進(jìn)制，即把一個(gè)數(shù)字按照個(gè)位、十位、百位等，一位一位地拆開，它每一位上的數(shù)字，也就是 \(0 \sim 9\)；其他進(jìn)制可類比十進(jìn)制。
數(shù)位 DP：一種按照數(shù)位暴力枚舉的方式，用來解決一類特定問題；這種問題比較好辨認(rèn)，一般具有這幾個(gè)特征：
- 提供一個(gè)數(shù)字區(qū)間（有時(shí)也只提供上界）來作為統(tǒng)計(jì)的限制；
- 統(tǒng)計(jì)滿足某種條件的數(shù)的數(shù)量，有時(shí)也有統(tǒng)計(jì)總和、平方和等的；
- 上界很大，甚至?xí)?\(10^{18}\) 這么大，暴力枚舉驗(yàn)證會(huì)超時(shí)；
- 這些條件經(jīng)過轉(zhuǎn)化后可以使用「數(shù)位」的思想去理解和判斷。
原理
例如，當(dāng)我們?cè)跀?shù)數(shù)的過程中，\(100 \sim 199\) 和 \(200 \sim 299\) 這兩部分，后兩位是完全相同的，這種重復(fù)計(jì)算可以通過 DP 的方式進(jìn)行優(yōu)化。
實(shí)現(xiàn)
計(jì)數(shù)原理
數(shù)位 DP 中通常會(huì)利用常規(guī)計(jì)數(shù)問題技巧，比如把一個(gè)區(qū)間內(nèi)的答案拆成兩部分相減，即查分的思路：
一般根據(jù)是否計(jì)入 \(0\) 的貢獻(xiàn)，將 \(s_k\) 定義為：\(\sum[0, k]\) 或 \(\sum[1, k]\).
數(shù)的存儲(chǔ)
一般將數(shù)字中較低位存在數(shù)組的低位之中，即：
typedef long long ll;
ll solve(ll x) {
int len = 0;
while (x) a[++len] = x % 10, x /= 10;
return dfs(...); //記憶化搜索
}
常用形參
統(tǒng)計(jì)答案可以選擇記憶化搜索，也可以選擇循環(huán)迭代遞推；因?yàn)閿?shù)位 DP 的預(yù)處理一般比較變態(tài)，所有我一般使用記憶化搜索。
常用的形式參數(shù)如下：
-
pos（int）：表示當(dāng)前枚舉的位置，一般從 \(\mathrm{len}\) 開始，到 \(0\) 為止。 -
limit（bool）：表示當(dāng)前枚舉到的位置，可以填的數(shù)是否收到限制；若為 true，則該位最大填 \(a_{pos}\)；否則最大填 \(R-1\)，其中 \(R\) 表示枚舉的進(jìn)制數(shù)。 -
sum（int）：表示從 \(\mathrm{len}\) 到 \(pos + 1\) 位的貢獻(xiàn)，常用的有求和等。 -
last（int）：表示上一位填的數(shù)，當(dāng)題目限制連續(xù)的兩個(gè)（或多個(gè)）數(shù)位有條件限制的話常用。 -
lead0（bool）：表示從 \(\mathrm{len}\) 到 \(pos + 1\) 是否都為 \(0\)（前導(dǎo)零）。 -
r（int）：表示從 \(\mathrm{len}\) 到 \(pos + 1\) 這個(gè)前綴模一個(gè)數(shù) \(\bmod\) 的結(jié)果，也可以表示數(shù)位和取模的結(jié)果。 -
st（bool）：常用與狀態(tài)壓縮，其二進(jìn)制表示某一位是否滿足某一條件等。
如何復(fù)用結(jié)果
簡(jiǎn)單分析可知，一定是已經(jīng)求解過中，狀態(tài)與當(dāng)前狀態(tài)相同的，可以復(fù)用，如 pos、sum、last 相同等；特殊的，當(dāng) limit == 1 或 lead0 == 1 時(shí)，即當(dāng)前位受到限制時(shí)，無需記錄狀態(tài)，因?yàn)檫@一狀態(tài)不會(huì)頻繁的復(fù)用，這種空間換時(shí)間價(jià)值不大。
即：
typedef long long ll;
ll f[N][M]; // DP 數(shù)組，第一維表示枚舉到的數(shù)位，第二維表示當(dāng)前的狀態(tài)；默認(rèn)為 -1
ll dfs(int pos, bool limit, int sum) {
if (!pos) return sum;
if (!limit && f[pos][sum] != -1) return f[pos][sum];
int up = limit ? a[pos] : 9;
ll res = 0; for (int i = 0; i <= up; ++i)
res = (res + dfs(pos - 1, limit && i == up, sum + i)) % MOD;
if (!limit) f[pos][sum] = res;
return res;
}
習(xí)題
見：https://www.luogu.com.cn/training/384691文章來源：http://www.zghlxwxcb.cn/news/detail-710446.html
Reference
[1] https://oi-wiki.org/dp/number/
[2] https://blog.csdn.net/hzf0701/article/details/116717851
[3] https://blog.csdn.net/m0_63726942/article/details/127060217文章來源地址http://www.zghlxwxcb.cn/news/detail-710446.html
到了這里，關(guān)于動(dòng)態(tài)規(guī)劃——數(shù)位DP 學(xué)習(xí)筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
