1. 項(xiàng)目概述從一道國賽真題看數(shù)位DP的實(shí)戰(zhàn)價(jià)值最近在復(fù)盤藍(lán)橋杯國賽真題時(shí)2021年的那道《二進(jìn)制問題》讓我印象尤為深刻。它不像一些純考編碼技巧的題目而是把“數(shù)位DP”這個(gè)聽起來有點(diǎn)玄乎的算法塞進(jìn)了一個(gè)非常具體的場景里給定一個(gè)區(qū)間[L, R]問在這個(gè)區(qū)間內(nèi)有多少個(gè)數(shù)的二進(jìn)制表示中恰好有K個(gè) 1。這題目一出來很多同學(xué)的第一反應(yīng)可能是暴力枚舉——從L到R遍歷每個(gè)數(shù)轉(zhuǎn)二進(jìn)制數(shù)1的個(gè)數(shù)。但一看數(shù)據(jù)范圍L和R可以大到10^18K最大到60暴力法的時(shí)間復(fù)雜度是O((R-L) * logR)直接超時(shí)沒商量。這道題就像一堵墻把只會基礎(chǔ)算法的選手擋在了外面而翻過這堵墻的鑰匙正是數(shù)位DP。數(shù)位DP到底是什么簡單說它是一種用于解決“與數(shù)字的數(shù)位相關(guān)”的計(jì)數(shù)問題的動態(tài)規(guī)劃方法。比如統(tǒng)計(jì)區(qū)間內(nèi)有多少個(gè)“不含4”的數(shù)字有多少個(gè)“各位數(shù)字之和為特定值”的數(shù)字或者像本題一樣統(tǒng)計(jì)二進(jìn)制表示中1的個(gè)數(shù)滿足條件的數(shù)字。它的核心思想是“按位決策”和“記憶化搜索”將一個(gè)大問題分解為對每一位數(shù)字的獨(dú)立決策并通過記錄中間狀態(tài)來避免重復(fù)計(jì)算從而將指數(shù)級復(fù)雜度降為多項(xiàng)式級別。對于這道《二進(jìn)制問題》數(shù)位DP提供了一種優(yōu)雅且高效的解決方案能夠在O(logR * K)的復(fù)雜度內(nèi)解決問題輕松應(yīng)對10^18的數(shù)據(jù)規(guī)模。這篇文章我就以這道藍(lán)橋杯國賽真題為引子帶你徹底搞懂?dāng)?shù)位DP。無論你是正在備賽藍(lán)橋杯的選手還是對算法競賽感興趣的開發(fā)者理解數(shù)位DP都能讓你在面對類似“區(qū)間數(shù)字統(tǒng)計(jì)”問題時(shí)多一份從容和把握。我會從最基礎(chǔ)的思路講起一步步拆解狀態(tài)設(shè)計(jì)、記憶化搜索的實(shí)現(xiàn)并分享我在調(diào)試這類問題時(shí)的獨(dú)家心得和常見“坑點(diǎn)”。2. 核心思路拆解為什么暴力不行數(shù)位DP行2.1 暴力法的瓶頸與數(shù)位DP的切入點(diǎn)我們先直觀感受一下暴力法的不可行性。假設(shè)L1, R10^18我們需要檢查約10^18個(gè)數(shù)。對于每個(gè)數(shù)要將其轉(zhuǎn)換為二進(jìn)制最多60位并統(tǒng)計(jì)其中1的個(gè)數(shù)。這其中的計(jì)算量是天文數(shù)字即使在現(xiàn)代計(jì)算機(jī)上也無法在比賽時(shí)限通常1-2秒內(nèi)完成。問題的根源在于暴力法將每個(gè)數(shù)字視為獨(dú)立的個(gè)體沒有利用數(shù)字之間在數(shù)位結(jié)構(gòu)上的內(nèi)在聯(lián)系。數(shù)位DP的巧妙之處在于它不直接枚舉數(shù)字而是枚舉數(shù)字的每一位。對于一個(gè)上界R我們考慮所有不超過R的數(shù)字。這些數(shù)字的二進(jìn)制表示可以從最高位到最低位逐位確定。在每一位上我們有兩種選擇放置0或放置1。但是為了確保最終構(gòu)成的數(shù)字不超過R我們在某些位上會受到限制——如果R的當(dāng)前位是1那么當(dāng)我們放置的位小于1即放置0時(shí)后續(xù)低位可以任意選擇0或1因?yàn)榇藭r(shí)已經(jīng)確保整個(gè)數(shù)字小于R了如果我們放置了和R當(dāng)前位相同的1那么后續(xù)位的選擇仍然受到R對應(yīng)位的限制。這個(gè)“是否受到限制”的狀態(tài)是數(shù)位DP的第一個(gè)關(guān)鍵維度。第二個(gè)維度就是本題的核心約束二進(jìn)制中1的個(gè)數(shù)。我們需要在逐位決策的過程中記錄到目前為止已經(jīng)放置了多少個(gè)1。當(dāng)決策完所有位時(shí)如果1的個(gè)數(shù)恰好等于K則這是一個(gè)有效的數(shù)字。因此數(shù)位DP解決本題的核心思路可以概括為用一個(gè)DFS深度優(yōu)先搜索函數(shù)自頂向下從二進(jìn)制最高位到最低位遍歷所有可能的數(shù)位組合。在DFS過程中通過參數(shù)記錄兩個(gè)關(guān)鍵狀態(tài)一是當(dāng)前是否受到上界R的限制limit二是當(dāng)前已經(jīng)累計(jì)的1的個(gè)數(shù)cnt。利用記憶化搜索將(位置, cnt, limit)這個(gè)狀態(tài)對應(yīng)的方案數(shù)緩存起來避免對相同狀態(tài)的重復(fù)計(jì)算從而實(shí)現(xiàn)高效計(jì)數(shù)。2.2 狀態(tài)設(shè)計(jì)與記憶化搜索原理基于上述思路我們需要設(shè)計(jì)DFS函數(shù)的參數(shù)和記憶化數(shù)組。參數(shù)設(shè)計(jì)pos: 當(dāng)前正在處理第幾位從最高位向最低位處理。通常我們讓最高位索引為len-1最低位索引為0。cnt: 從最高位到pos1位即已經(jīng)處理完的高位中已經(jīng)放置了cnt個(gè)1。limit: 布爾值表示當(dāng)前位的選擇是否受到上界R的限制。如果limit為true則當(dāng)前位最大只能取R在pos位的值0或1如果為false則當(dāng)前位可以取0或1。記憶化數(shù)組dp我們定義一個(gè)數(shù)組dp[pos][cnt]用于記錄在不受上界限制limitfalse的情況下從pos位開始往低位繼續(xù)填充并且當(dāng)前已累計(jì)cnt個(gè)1時(shí)能夠構(gòu)造出的滿足條件的數(shù)字個(gè)數(shù)。為什么dp數(shù)組不需要記錄limit狀態(tài)這是理解數(shù)位DP記憶化的關(guān)鍵。當(dāng)limittrue時(shí)當(dāng)前位的選擇受限后續(xù)位的構(gòu)造方案依賴于具體的上界R因此這部分狀態(tài)是“不通用”的無法被后續(xù)其他搜索路徑復(fù)用。只有當(dāng)limitfalse時(shí)意味著高位已經(jīng)有一個(gè)位選擇了比R對應(yīng)位小的值從此位開始低位可以自由選擇0或1不再受R的影響。此時(shí)的狀態(tài)(pos, cnt)是“通用的”無論之前的高位具體是什么只要走到這個(gè)狀態(tài)后續(xù)的方案數(shù)都是相同的。因此我們只對limitfalse的狀態(tài)進(jìn)行記憶化。DFS返回值DFS函數(shù)返回一個(gè)數(shù)值在給定的pos,cnt,limit狀態(tài)下能夠構(gòu)造出的、最終1的個(gè)數(shù)恰好為K的數(shù)字個(gè)數(shù)。遞歸邊界與結(jié)果統(tǒng)計(jì)當(dāng)pos -1時(shí)表示所有位都已處理完畢。此時(shí)我們檢查累計(jì)的1的個(gè)數(shù)cnt是否等于目標(biāo)K。如果相等則找到1個(gè)有效數(shù)字返回1否則返回0。在遞歸過程中對于當(dāng)前位pos根據(jù)limit決定可選的數(shù)字集合。遍歷每一個(gè)可選數(shù)字0或1更新新的cnt如果選了1則cnt1和新的limit狀態(tài)如果當(dāng)前位受限且選了與上界相同的值則下一位繼續(xù)受限否則下一位不再受限然后遞歸調(diào)用DFS函數(shù)計(jì)算子問題的方案數(shù)并累加到當(dāng)前結(jié)果中。在返回結(jié)果前如果當(dāng)前處于limitfalse的狀態(tài)則將計(jì)算結(jié)果存入dp[pos][cnt]以便后續(xù)復(fù)用。通過這樣的設(shè)計(jì)我們將一個(gè)龐大的枚舉問題轉(zhuǎn)化為了一個(gè)狀態(tài)數(shù)約為(位數(shù)) * (K1)的動態(tài)規(guī)劃問題。對于本題位數(shù)最多60K最大60狀態(tài)數(shù)最多約3600個(gè)每個(gè)狀態(tài)的計(jì)算是常數(shù)時(shí)間因此效率極高。注意這里有一個(gè)初學(xué)者極易混淆的點(diǎn)。我們最終要求的是區(qū)間[L, R]內(nèi)的個(gè)數(shù)。數(shù)位DP通常解決的是[0, N]范圍內(nèi)滿足條件的個(gè)數(shù)。因此我們需要分別計(jì)算f(R)和f(L-1)那么答案就是f(R) - f(L-1)。這就是所謂的“前綴和”思想在數(shù)位DP中的應(yīng)用。3. 代碼實(shí)現(xiàn)與逐行解析理論清晰后我們來看具體的代碼實(shí)現(xiàn)。我將以C為例進(jìn)行講解其他語言的思路完全一致。3.1 輔助函數(shù)將數(shù)字轉(zhuǎn)換為二進(jìn)制位數(shù)組首先我們需要一個(gè)函數(shù)將上界數(shù)字N轉(zhuǎn)換為二進(jìn)制位數(shù)組并確定最高位。#include bits/stdc.h using namespace std; using ll long long; // 將數(shù)字n的二進(jìn)制位存入數(shù)組a低位對應(yīng)索引0方便循環(huán)但DFS時(shí)我們從高位開始處理。 // 這里我們選擇將最高位放在a[0]方便DFS索引。另一種常見方式是低位在0DFS時(shí)pos從最高位下標(biāo)開始遞減。 vectorint getBits(ll n) { vectorint bits; if (n 0) bits.push_back(0); // 處理0的情況 while (n) { bits.push_back(n 1); // 取出最低位 n 1; // 右移一位 } reverse(bits.begin(), bits.end()); // 反轉(zhuǎn)使得bits[0]是最高位 return bits; }3.2 核心DFS函數(shù)與記憶化搜索接下來是數(shù)位DP的核心。我們定義一個(gè)類或者使用全局變量來存儲狀態(tài)。ll dp[70][70]; // dp[pos][cnt] 60位二進(jìn)制K最大60數(shù)組開70足夠 vectorint bits; // 當(dāng)前上界N的二進(jìn)制表示 int K; // 目標(biāo)1的個(gè)數(shù) ll dfs(int pos, int cnt, bool limit) { // 遞歸邊界所有位都處理完畢 if (pos bits.size()) { return cnt K ? 1 : 0; } // 記憶化只有在不受限制時(shí)當(dāng)前狀態(tài)的結(jié)果才是通用的可以復(fù)用 if (!limit dp[pos][cnt] ! -1) { return dp[pos][cnt]; } ll res 0; // 確定當(dāng)前位可以選擇的數(shù)字上限 int up limit ? bits[pos] : 1; // 二進(jìn)制位最大是1 for (int d 0; d up; d) { int new_cnt cnt (d 1); // 如果當(dāng)前位選1則計(jì)數(shù)加1 // 新的limit狀態(tài)當(dāng)前位受限且選擇了上限值則下一位繼續(xù)受限 bool new_limit limit (d up); res dfs(pos 1, new_cnt, new_limit); } // 記錄不受限狀態(tài)的結(jié)果 if (!limit) { dp[pos][cnt] res; } return res; }逐行解析ll dp[70][70];記憶化數(shù)組。dp[pos][cnt]表示在位置pos已累計(jì)cnt個(gè)1且后續(xù)位不受限制時(shí)能構(gòu)造出的有效數(shù)字個(gè)數(shù)。初始化為-1表示未計(jì)算。dfs(int pos, int cnt, bool limit)深度優(yōu)先搜索函數(shù)。pos當(dāng)前處理位的索引從0開始對應(yīng)最高位。cnt已放置的1的個(gè)數(shù)。limit是否受到上界限制。邊界條件if (pos bits.size())當(dāng)處理完所有位后判斷cnt是否等于K是則返回1找到一個(gè)有效數(shù)否則返回0。記憶化判斷if (!limit dp[pos][cnt] ! -1)這是核心優(yōu)化點(diǎn)。只有當(dāng)前狀態(tài)不受上界限制時(shí)其結(jié)果才是“純凈”的、可被其他路徑復(fù)用的因此直接返回緩存值。int up limit ? bits[pos] : 1;確定當(dāng)前位能選擇的最大數(shù)字。如果受限最大只能取bits[pos]即上界N的該位值如果不受限則可以取到1因?yàn)槎M(jìn)制位只有0和1。循環(huán)for (int d 0; d up; d)枚舉當(dāng)前位所有可能的選擇0或1直到上限up。new_limit limit (d up);計(jì)算傳遞給下一位的limit狀態(tài)。只有當(dāng)前位本身受限limittrue并且當(dāng)前位選擇了最大值d up時(shí)下一位才繼續(xù)受限否則下一位將不再受限。累加子問題結(jié)果res dfs(pos 1, new_cnt, new_limit);。記憶化存儲在返回前如果當(dāng)前狀態(tài)不受限!limit則將結(jié)果res存入dp[pos][cnt]。3.3 主函數(shù)與區(qū)間處理最后我們需要一個(gè)主函數(shù)來計(jì)算f(N)并利用前綴和思想求解[L, R]區(qū)間。ll solve(ll N) { if (N 0) return 0; // 處理負(fù)數(shù)邊界本題L1可省略 bits getBits(N); memset(dp, -1, sizeof(dp)); // 每次計(jì)算新的上界N前必須重置dp數(shù)組 return dfs(0, 0, true); // 從最高位開始當(dāng)前計(jì)數(shù)為0初始狀態(tài)是受限的 } int main() { ll L, R; cin L R K; ll ans_R solve(R); ll ans_L_1 solve(L - 1); // 計(jì)算[0, L-1]范圍內(nèi)的個(gè)數(shù) cout ans_R - ans_L_1 endl; return 0; }關(guān)鍵點(diǎn)說明solve(ll N)函數(shù)計(jì)算[0, N]范圍內(nèi)滿足條件的數(shù)字個(gè)數(shù)。每次調(diào)用solve前必須用memset(dp, -1, sizeof(dp))清空記憶化數(shù)組。因?yàn)閎its數(shù)組即上界N改變了dp數(shù)組緩存的狀態(tài)是基于之前上界的不能混用。最終答案ans f(R) - f(L-1)這就是數(shù)位DP解決區(qū)間問題的標(biāo)準(zhǔn)做法。4. 深度剖析狀態(tài)設(shè)計(jì)與邊界處理的實(shí)戰(zhàn)技巧數(shù)位DP的代碼框架相對固定但魔鬼藏在細(xì)節(jié)里。不同的狀態(tài)設(shè)計(jì)、邊界條件處理會直接影響代碼的正確性和簡潔性。下面分享幾個(gè)我在實(shí)戰(zhàn)中總結(jié)的關(guān)鍵技巧。4.1 記憶化維度的取舍為什么通常不記limit前面提到dp數(shù)組通常不記錄limit狀態(tài)。這是為了最大化記憶化的效益。limittrue的狀態(tài)是“一次性”的與具體的上界數(shù)字強(qiáng)綁定復(fù)用率極低。而limitfalse的狀態(tài)是“通用”的代表了“從此位開始可以自由發(fā)揮”的所有情況復(fù)用率極高。將兩者混在一起記憶化不僅不會提升效率反而可能因?yàn)闋顟B(tài)爆炸多了一倍而增加開銷。因此if (!limit)這個(gè)判斷是數(shù)位DP記憶化搜索的“標(biāo)準(zhǔn)開頭”。4.2 前導(dǎo)零的處理本題的特殊性與通用情況本題《二進(jìn)制問題》有一個(gè)特點(diǎn)它不關(guān)心前導(dǎo)零。二進(jìn)制數(shù)00101十進(jìn)制5和101十進(jìn)制5在本題看來是同一個(gè)數(shù)其1的個(gè)數(shù)都是2。我們的DFS從最高非零位開始處理自然忽略了前導(dǎo)零因此代碼中不需要特殊處理。但是很多數(shù)位DP問題會受到前導(dǎo)零的影響。例如統(tǒng)計(jì)“數(shù)字中不含連續(xù)的1”。對于數(shù)字0101從最高位開始看第一個(gè)0是前導(dǎo)零它和后面的1不構(gòu)成“連續(xù)”。如果我們簡單地逐位判斷就會誤判。處理這類問題通常需要在狀態(tài)中增加一個(gè)lead參數(shù)表示當(dāng)前位之前是否都是前導(dǎo)零。只有當(dāng)leadfalse時(shí)當(dāng)前位的數(shù)字才參與“連續(xù)”等規(guī)則的判斷。這是數(shù)位DP中一個(gè)重要的變體。4.3 遞歸起點(diǎn)與pos的設(shè)定在我的代碼中pos從0開始指向bits數(shù)組的最高位。遞歸的終止條件是pos bits.size()。這是一種常見的寫法。另一種常見寫法是將數(shù)字的二進(jìn)制位存入數(shù)組a[]其中a[0]是最低位。DFS函數(shù)中的pos從最高位索引len-1開始向低位pos-1遞歸終止條件是pos -1。兩種寫法在邏輯上完全等價(jià)選擇哪一種取決于個(gè)人習(xí)慣。關(guān)鍵是要保持位順序、索引移動和邊界條件的一致性。我個(gè)人的偏好是使用從高位向低位遞歸、pos作為當(dāng)前處理位索引、終止于pos len的寫法因?yàn)檫@樣pos的值直觀地表示“已經(jīng)處理了多少位”或“還剩多少位待處理”在思考狀態(tài)轉(zhuǎn)移時(shí)更容易。4.4 復(fù)雜度分析時(shí)間復(fù)雜度狀態(tài)總數(shù)由dp數(shù)組的大小決定為O(位數(shù) * K)。每個(gè)狀態(tài)的計(jì)算需要遍歷當(dāng)前位的可選數(shù)字最多2個(gè)因此每個(gè)狀態(tài)的計(jì)算是O(1)?？倳r(shí)間復(fù)雜度為O(位數(shù) * K)。對于本題最壞情況下約為60 * 60 3600次遞歸調(diào)用效率極高?？臻g復(fù)雜度主要是dp數(shù)組的開銷為O(位數(shù) * K)以及遞歸棧的深度O(位數(shù))。5. 常見問題與調(diào)試心得數(shù)位DP的代碼邏輯比較精妙初次編寫很容易出錯。下面是我在練習(xí)和比賽中遇到的一些典型問題及解決方法。5.1 問題一答案總是偏大或偏小可能原因1dp數(shù)組沒有每次重置。這是最最常見的錯誤solve(N)函數(shù)計(jì)算的是針對特定上界N的方案數(shù)。dp數(shù)組中緩存的狀態(tài)與N的二進(jìn)制表示bits是相關(guān)的。當(dāng)換一個(gè)N計(jì)算時(shí)比如從solve(R)到solve(L-1)必須用memset(dp, -1, sizeof(dp))清空之前的緩存否則會得到錯誤的結(jié)果。可能原因2區(qū)間轉(zhuǎn)換公式用錯。一定要牢記數(shù)位DP的DFS通常計(jì)算的是[0, N]范圍內(nèi)的個(gè)數(shù)。要求[L, R]區(qū)間必須是f(R) - f(L-1)。如果寫成f(R) - f(L)就會漏掉L這個(gè)數(shù)本身如果它滿足條件。可能原因3K值在DFS中作為全局變量被修改。確保K是常量或者在每次調(diào)用solve時(shí)作為參數(shù)傳入DFS不要在其他地方意外修改它。5.2 問題二遞歸深度過大導(dǎo)致棧溢出或超時(shí)可能原因沒有正確進(jìn)行記憶化導(dǎo)致大量重復(fù)計(jì)算。檢查記憶化的條件if (!limit dp[pos][cnt] ! -1)是否寫對。特別是!limit這個(gè)條件不能丟。如果丟了程序會退化到暴力搜索復(fù)雜度是指數(shù)級的對于60位的二進(jìn)制數(shù)遞歸樹節(jié)點(diǎn)數(shù)高達(dá)2^60必然超時(shí)或棧溢出。5.3 問題三處理數(shù)字0的情況場景當(dāng)L0時(shí)我們需要計(jì)算f(L-1)即f(-1)。getBits(-1)可能引發(fā)問題如死循環(huán)且[0, N]區(qū)間本身包含數(shù)字0。處理在solve(N)函數(shù)開始處判斷如果N 0直接返回0。因?yàn)椴淮嬖谛∮?的區(qū)間。數(shù)字0的二進(jìn)制表示通常被視為0它包含0個(gè)1。如果K 0那么0本身也是一個(gè)有效數(shù)字需要被計(jì)入。我們的DFS邏輯bits數(shù)組為[0]從最高位0開始能夠正確處理這種情況當(dāng)K0時(shí)dfs最終會在邊界返回1因?yàn)閏nt0等于K0。5.4 調(diào)試技巧打印遞歸樹與狀態(tài)當(dāng)程序輸出錯誤答案時(shí)最有效的調(diào)試方法是打印關(guān)鍵的遞歸路徑。ll dfs(int pos, int cnt, bool limit, int depth) { // 縮進(jìn)顯示遞歸深度 // for (int i 0; i depth; i) cerr ; // cerr pos pos , cnt cnt , limit limit endl; if (pos bits.size()) { // cerr - return (cnt K ? 1 : 0) endl; return cnt K ? 1 : 0; } if (!limit dp[pos][cnt] ! -1) { // cerr - use dp[ pos ][ cnt ] dp[pos][cnt] endl; return dp[pos][cnt]; } // ... 其余代碼不變 }通過觀察遞歸調(diào)用的順序、參數(shù)變化以及記憶化命中的情況可以快速定位是狀態(tài)設(shè)計(jì)錯誤、記憶化條件錯誤還是邊界條件錯誤。5.5 一個(gè)完整的測試用例與推演假設(shè)L1,R5,K2。二進(jìn)制1(001),2(010),3(011),4(100),5(101)。其中二進(jìn)制含2個(gè)1的數(shù)有3(011),5(101)。所以答案應(yīng)為2。計(jì)算過程ans_R solve(5)。5的二進(jìn)制bits [1,0,1](3位)。DFS會遍歷所有不超過101(二進(jìn)制) 的數(shù)并統(tǒng)計(jì)其中恰有2個(gè)1的數(shù)。這些數(shù)包括011(3),101(5)。solve(5)返回2。ans_L_1 solve(0)。0的二進(jìn)制bits [0]。DFS遍歷不超過0的數(shù)只有0本身。0的二進(jìn)制有0個(gè)1K2所以solve(0)返回0。最終答案ans 2 - 0 2符合預(yù)期。你可以嘗試用調(diào)試輸出跟蹤solve(5)的DFS過程看看它是如何一步步構(gòu)造出3和5并跳過其他數(shù)字的。這能極大地加深你對算法過程的理解。數(shù)位DP的精髓在于“按位決策”和“狀態(tài)復(fù)用”。掌握了這個(gè)框架你就能解決一大類區(qū)間數(shù)字統(tǒng)計(jì)問題。從二進(jìn)制到十進(jìn)制從統(tǒng)計(jì)1的個(gè)數(shù)到判斷數(shù)字屬性萬變不離其宗。希望這篇基于藍(lán)橋杯真題的深度解析能幫你徹底攻克這個(gè)知識點(diǎn)。在算法競賽的路上這類清晰的解題框架就是你最可靠的武器。