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