【數(shù)位DP】藍(lán)橋云課 - 小藍(lán)的生日禮物 題解1. 題目概述題目名稱小藍(lán)的生日禮物題目大意在區(qū)間[ a , b ] [a, b][a,b]中挑選滿足“相鄰兩位的數(shù)字之差至少為 2”的整數(shù)求滿足條件的數(shù)字個數(shù)。數(shù)據(jù)規(guī)模1 ≤ a ≤ b ≤ 10 9 1 \le a \le b \le 10^91≤a≤b≤1092. 解題思路本題是典型的**數(shù)位 DP數(shù)位動態(tài)規(guī)劃**問題要求統(tǒng)計區(qū)間[ a , b ] [a, b][a,b]內(nèi)滿足特定數(shù)位限制的數(shù)字?jǐn)?shù)量。區(qū)間轉(zhuǎn)換通過前綴和思想求區(qū)間[ a , b ] [a, b][a,b]內(nèi)滿足條件的個數(shù)可以轉(zhuǎn)化為求解solve(b) - solve(a - 1)其中solve(x)表示求[ 0 , x ] [0, x][0,x]范圍內(nèi)符合條件的數(shù)字個數(shù)。DFS 狀態(tài)設(shè)計通過記憶化搜索來實現(xiàn)數(shù)位 DPpos當(dāng)前處理到的數(shù)位從高位向低位。pre前一位填入的數(shù)字用于判斷相鄰差值是否≥ 2 \ge 2≥2。lead前導(dǎo)零標(biāo)記。如果為true說明前面全為 0當(dāng)前位填 0 仍屬于前導(dǎo)零不觸發(fā)相鄰差值的限制。limit最高位限制標(biāo)記。如果為true當(dāng)前位最大只能填到原數(shù)在該位的數(shù)字若為false則可填0~9。狀態(tài)轉(zhuǎn)移與記憶化當(dāng)pos -1時說明成功構(gòu)造了一個合法數(shù)字返回1。當(dāng)!limit !lead時說明當(dāng)前狀態(tài)不受上限限制且已離開前導(dǎo)零階段結(jié)果具有通用性可以保存在dp[pos][pre]中后續(xù)重復(fù)遇到可直接返回。3. C 源碼#includebits/stdc.husingnamespacestd;longlongdp[15][15];vectorintnum;/** * brief 數(shù)位 DP 記憶化搜索 * param pos 當(dāng)前處理的數(shù)位索引從高到低 * param pre 前一位填入的數(shù)字 * param lead 是否包含前導(dǎo)零 * param limit 是否受到最高位限制 */intdfs(intpos,intpre,boollead,boollimit){if(pos-1)return1;// 遞歸基構(gòu)造完成一個數(shù)// 記憶化檢索if(!lead!limitdp[pos][pre]!-1){returndp[pos][pre];}longlongres0;intuplimit?num[pos]:9;// 當(dāng)前可填的最大數(shù)字for(intd0;dup;d){if(lead){if(d0){// 仍處于前導(dǎo)零狀態(tài)resdfs(pos-1,0,true,limit(dup));}else{// 離開前導(dǎo)零狀態(tài)resdfs(pos-1,d,false,limit(dup));}}else{// 正常填數(shù)需滿足相鄰差值 2if(abs(d-pre)2){resdfs(pos-1,d,false,limit(dup));}}}// 狀態(tài)記錄if(!limit!lead){dp[pos][pre]res;}returnres;}/** * brief 計算 [0, x] 范圍內(nèi)滿足條件的數(shù)字個數(shù) */longlongsolve(longlongx){if(x0)return0;num.clear();while(x){num.push_back(x%10);x/10;}if(num.empty())num.push_back(0);returndfs(num.size()-1,0,true,true);}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);memset(dp,-1,sizeof(dp));longlongA,B;if(cinAB){coutsolve(B)-solve(A-1)\n;}return0;}4. 復(fù)雜度分析時間復(fù)雜度最大位數(shù)L ≈ 10 L \approx 10L≈10對于10 9 10^9109級別的數(shù)。狀態(tài)數(shù)為位數(shù) × 前一位數(shù)字 10 × 10 100 \text{位數(shù)} \times \text{前一位數(shù)字} 10 \times 10 100位數(shù)×前一位數(shù)字10×10100種每個狀態(tài)遍歷0 ～ 9 0 \sim 90～9轉(zhuǎn)移運(yùn)行時間不超過 1ms完全滿足時間限制。空間復(fù)雜度O ( L × 10 ) O(L \times 10)O(L×10)使用極少的額外內(nèi)存數(shù)位 DP 數(shù)組僅需15 × 15 15 \times 1515×15。