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