1. 从一道“数数”题说起为什么我们需要数位DP如果你刷过一些算法题尤其是像POJ、蓝桥杯这类竞赛题大概率遇到过这样一类问题给你一个区间[L, R]让你统计在这个区间内所有数字的十进制或二进制表示中某个特定数字比如‘6’出现了多少次或者满足某种特殊性质的数字有多少个。比如POJ2282 “The Counting Problem” 就是让你统计0-9每个数字在给定区间内出现的总次数。第一次遇到这种题你可能会想“这还不简单从L到R遍历每个数拆开每一位数一下不就行了”然后你兴冲冲地写了个循环一提交——Time Limit Exceeded超时。为什么因为L和R的范围可能非常大比如1 L R 2,000,000,000。20亿次的循环和数位拆分对于计算机来说也是沉重的负担。这时你就需要一个更“聪明”的算法它不需要遍历每一个数而是通过分析数字的结构直接“计算”出结果。这就是数位动态规划Digit DP的核心价值所在。数位DP解决的是一类与数字的“位数”和“位值”相关的计数问题。它把一个大范围的、看似需要暴力枚举的问题转化成了一个基于数位位置和状态记忆的、高效的计算过程。理解并掌握数位DP不仅能让你轻松解决POJ2282、POJ3208寻找第N个包含“666”的数字这类经典题目更是应对蓝桥杯等竞赛中计数问题的利器。今天我们就以这几个经典问题为脉络彻底拆解数位DP的思维框架和实现细节。2. 数位DP的核心思想与通用“记忆化搜索”模板数位DP之所以高效是因为它利用了数字的一个关键特性前缀无关性。举个例子当我们统计1到54321之间有多少个包含连续“666”的数时对于前两位是“54”的所有五位数即54000到54999它们后续三位百位、十位、个位中“666”的出现情况只取决于当前是否已经出现了“666”以及最后几位是什么而和前面的“54”具体是多少没有直接关系只要不超过上界。这就产生了大量重复的子问题。数位DP最经典、也最易于理解的实现方式是记忆化搜索DFS with Memoization。我们用一个DFS函数来“构造”数字从最高位向最低位递归在递归过程中记录关键状态并利用记忆化数组避免重复计算。下面给出一个解决“统计区间[0, x]内满足条件P的数字个数”的通用模板。我们通常先实现一个函数solve(int x)它返回[0, x]内满足条件的数的个数那么区间[L, R]的答案就是solve(R) - solve(L-1)。#include bits/stdc.h using namespace std; using ll long long; // 将数字x的每一位分解到数组a中低位在前方便递归长度len int a[20]; ll dp[20][state]; // 状态数组维度根据具体问题定义 ll dfs(int pos, int state, bool lead, bool limit) { // pos: 当前处理到第几位从0开始即最低位 // state: 当前的状态记录之前位的信息如前缀中特定数字的个数、是否已出现特定模式等 // lead: 前导零标志。true表示前面的位都是0即我们构造的数字目前有效部分还没开始 // limit: 上限标志。true表示当前位能填的数字受原始数字x对应位的限制 // 递归边界所有位都处理完毕 if (pos -1) { return check(state) ? 1 : 0; // 根据最终状态判断是否计入答案 } // 记忆化只有在无前导零且无上限限制时才能直接使用之前计算的结果 // 因为前导零和上限限制会影响后续选择使得子问题不通用 if (!lead !limit dp[pos][state] ! -1) { return dp[pos][state]; } int up limit ? a[pos] : 9; // 当前位能填的最大数字 ll ans 0; for (int i 0; i up; i) { // 计算下一位的状态 int next_state get_next_state(state, i, lead); // 核心递归下一位更新状态更新前导零和上限标志 ans dfs(pos - 1, next_state, lead i 0, limit i up); } // 记录状态同样只在无限制时记录 if (!lead !limit) { dp[pos][state] ans; } return ans; } ll solve(ll x) { if (x 0) return 0; // 根据题意有时0需要特殊处理 int len 0; while (x) { a[len] x % 10; x / 10; } memset(dp, -1, sizeof(dp)); // 初始化DP数组为-1未计算 // 从最高位开始递归初始状态通常为0有前导零受上限限制 return dfs(len - 1, 0, true, true); }这个模板中有四个关键参数理解它们至关重要pos(位置)表示当前正在处理数字的第几位。递归深度。state(状态)这是数位DP的灵魂用于记录从最高位到当前pos位不含为止我们所关心的所有信息。不同的题目state的定义完全不同。例如统计数字‘d’出现次数state可以是一个整数记录到目前为止‘d’出现了几次。寻找包含“666”的数state可以记录当前末尾连续‘6’的个数0, 1, 2或者用一个状态码表示是否已经出现了“666”。二进制问题统计1的个数state可以记录当前1的个数。lead(前导零)这是一个非常容易出错的点。前导零是指我们构造的数字中高位连续的0。例如数字0054前两个0就是前导零。为什么需要它影响状态计算对于统计数字‘0’出现次数的问题前导零的‘0’不应该被计入。lead为true时当前位的‘0’是前导零不计入状态。影响记忆化状态(pos, state)只有在lead为false即已经开始了有效数字时才是通用的可以记忆化。否则state可能是在前导零背景下计算出来的不适用于非前导零的情况。limit(上限限制)表示当前位填的数字是否受到原始数字x对应位的限制。例如x543当前处理百位pos2如果前面所有位都填的和x一样即目前构造的前缀等于x的前缀那么当前位最多只能填5limittrue。如果前面有任何一位填的比x对应位小比如十位我们填了3而x的十位是4那么从这一位开始后面所有位都可以填0-9limitfalse。它同样影响记忆化。只有limitfalse时后续位的选择才是完全自由的0-9子问题才是通用的才能被记忆化。一个核心技巧我们通常把数字分解成低位在数组前。这样pos从len-1递归到0更符合我们从高位向低位思考的习惯。dfs函数中的pos表示“还剩多少位待处理”当pos -1时表示所有位都处理完了。3. 实战拆解一POJ2282 The Counting Problem统计数字出现次数问题描述给定两个整数a和b0 a, b 1e8对于每个数字d (0-9)统计在[a, b]包含区间内所有整数的十进制表示中数字d出现的总次数。思路分析这是最经典的数位DP入门题。我们可以对每个数字d (0-9)分别计算。定义state为从最高位到当前位数字d已经出现的次数cnt。状态设计dp[pos][cnt]表示处理到第pos位时数字d已经出现了cnt次在无前导零、无上限限制的条件下从这一位往后能构造出多少个数这些数最终都会被计入答案但我们需要在递归边界根据最终的cnt来加权计算总次数。但是注意我们最终要的是出现次数的总和而不是数字的个数。如果只在边界返回1或0我们只能算出有多少个数字包含d而不是d出现的总次数。解决方案修改DFS的返回值。让DFS返回一个pairll, ll第一个值cnt表示满足条件的数字个数第二个值sum表示这些数字中数字d出现的总次数。递归过程从下一位DFS获取结果(next_cnt, next_sum)。当前位如果填的是数字d则对总次数的贡献是next_cnt因为当前位的这个d会在next_cnt个数字的每一位都出现一次加上next_sum来自后续位的贡献。当前位如果填的不是数字d则贡献只有next_sum。细节处理对于数字0需要特别小心前导零。只有当lead为false时当前位的0才被视为有效数字0并可能被统计。核心代码片段pairll, ll dfs(int pos, int cnt, bool lead, bool limit, int digit) { if (pos -1) { return {1, cnt}; // 一个数字贡献了cnt次 } if (!lead !limit dp[pos][cnt].first ! -1) { return dp[pos][cnt]; } int up limit ? a[pos] : 9; pairll, ll ans {0, 0}; for (int i 0; i up; i) { bool is_lead lead (i 0); int next_cnt cnt; if (!is_lead i digit) { // 非前导零且是目标数字 next_cnt; } auto res dfs(pos - 1, next_cnt, is_lead, limit i up, digit); ans.first res.first; // 数字个数累加 ans.second res.second ( (!is_lead i digit) ? res.first : 0 ); // 次数累加后续位的总次数 当前位的贡献如果当前位是d } if (!lead !limit) { dp[pos][cnt] ans; } return ans; }避坑点状态定义与返回值这是本题的关键。如果只返回数字个数无法直接求出总次数。必须让DFS携带“贡献值”信息。前导零与数字0这是最容易WA错误答案的地方。必须明确只有非前导零状态的0才是数字0才需要被统计。在判断i digit时一定要结合lead标志。记忆化维度dp数组的第二维cnt大小是多少最坏情况下一个8位数1e8每个位都是dcnt最大为8。但安全起见可以设为当前剩余位数pos1或者一个稍大的常数如20。通过分别对0-9每个数字调用一次solve函数内部调用DFS我们就能得到每个数字在区间内的总出现次数。时间复杂度为O(10 * 位数 * 状态数 * 10)对于题目范围绰绰有余。4. 实战拆解二POJ3208 启示录寻找第N个包含“666”的数问题描述寻找第N个N可达5e7包含连续三个“6”即“666”的正整数。例如第一个是666第二个是1666第三个是2666第四个是3666第五个是4666第六个是5666第七个是6660注意这里6660中的666是连续的。思路分析这不是一个区间计数问题而是一个“按序查找”问题。一种方法是二分答案数位DP检验。即二分一个数字mid用数位DP计算[1, mid]之间有多少个包含“666”的数如果个数N则答案在右边否则在左边。直到找到最小的mid使得[1, mid]内的个数N。因此核心还是实现一个数位DP函数count(long long x)返回[1, x]内包含“666”的数的个数。状态设计我们需要记录一个状态来表示当前末尾连续‘6’的个数以及是否已经出现了“666”。 一个经典的设计是state 0: 当前末尾没有连续的6。state 1: 当前末尾有1个连续的6。state 2: 当前末尾有2个连续的6。state 3: 已经出现了“666”无论末尾是什么。状态转移如果当前state 0或1或2当前位填6state增加1如果state已经是2则变为3。当前位填其他数字state重置为0。如果当前state 3无论当前位填什么state都保持为3已经满足条件。递归边界当pos -1时如果state 3返回1否则返回0。核心代码片段ll dp[20][4]; // dp[pos][state] ll dfs(int pos, int state, bool lead, bool limit) { if (pos -1) { return state 3 ? 1 : 0; } if (!lead !limit dp[pos][state] ! -1) { return dp[pos][state]; } int up limit ? a[pos] : 9; ll ans 0; for (int i 0; i up; i) { int next_state state; if (state 3) { if (i 6) { next_state state 1; if (next_state 3) next_state 3; } else { next_state 0; } } // 如果state已经是3next_state保持为3 ans dfs(pos - 1, next_state, lead i 0, limit i up); } if (!lead !limit) { dp[pos][state] ans; } return ans; }二分查找实现long long findNth(int N) { long long left 1, right 1e18; // 一个足够大的上界 long long ans right; while (left right) { long long mid left (right - left) / 2; if (count(mid) N) { // count(mid)返回[1,mid]中满足条件的数的个数 ans mid; right mid - 1; } else { left mid 1; } } return ans; }避坑点状态3的设计一旦进入状态3已出现“666”就必须永远保持为3无论后面填什么数字。这确保了只要前缀满足了条件整个数就被计入。前导零的处理在这个问题中前导零不影响“666”模式的识别。因为前导零不是‘6’。所以lead标志主要用来控制记忆化的条件在状态转移中当lead为true且i0时next_state应该保持为0因为前导零不是有效数字不参与连续‘6’的计数。二分边界N可以很大5e7第N个包含“666”的数会非常大二分的右边界right必须设得足够大。1e18是一个比较安全的选择。二分时注意是寻找下界第一个使count(mid) N的mid。这个方法将“查找第N个”的问题转化为了O(log(MAX))次“计数问题”每次计数是数位DP的O(位数*状态数*10)效率非常高。5. 实战拆解三第十二届蓝桥杯国赛CB组H题——二进制问题统计1的个数为K的数问题描述给定一个区间[L, R]L, R可达1e18和一个整数K0 K 60统计该区间内有多少个整数的二进制表示中恰好有K个‘1’。思路分析这是数位DP从十进制向二进制的一个直接迁移。数位DP的本质是与进制无关的它处理的是“按位计数”。我们只需要把模板中的十进制位0-9换成二进制位0-1把up从9换成1即可。状态设计state可以直接定义为当前已经放置的‘1’的个数cnt。DP数组dp[pos][cnt]表示处理到第pos位时已经使用了cnt个‘1’在无前导零、无上限限制的情况下能构造出多少个数。这里前导零在二进制中同样重要因为高位的‘0’不影响‘1’的计数但影响数字的有效性不过对于统计‘1’的个数前导零的‘0’显然不计为‘1’。递归边界当pos -1时所有位处理完毕判断cnt K相等则返回1否则返回0。核心代码片段ll dp[70][70]; // pos最大约为60因为1e18 2^60cnt最大为K ll dfs(int pos, int cnt, bool lead, bool limit) { if (pos -1) { return cnt K ? 1 : 0; } if (!lead !limit dp[pos][cnt] ! -1) { return dp[pos][cnt]; } int up limit ? a[pos] : 1; // 二进制位最大为1 ll ans 0; for (int i 0; i up; i) { bool is_lead lead (i 0); int next_cnt cnt; if (i 1) { next_cnt; } // 剪枝如果next_cnt已经超过K后续无论怎么填都不可能满足条件可以跳过 // 但在这个简单循环中剪枝效果不明显可写可不写 ans dfs(pos - 1, next_cnt, is_lead, limit i up); } if (!lead !limit) { dp[pos][cnt] ans; } return ans; }二进制数位分解ll solve(ll x) { if (x 0) return 0; int len 0; while (x) { a[len] x 1; // 取二进制最低位 x 1; } // 注意如果x0len为0需要特殊处理因为0的二进制表示中‘1’的个数为0 if (len 0) { // 即x0 a[0] 0; len 1; } memset(dp, -1, sizeof(dp)); return dfs(len - 1, 0, true, true); }避坑点与优化0的处理solve(0)需要单独处理。因为我们的数位分解循环while(x)在x0时不会执行导致len0。而dfs(len-1, ...)会访问非法索引。可以在solve开始判断如果x0直接返回K0 ? 1 : 0。或者在分解后如果len0手动设置len1, a[0]0。前导零在二进制中前导零同样不贡献‘1’。所以lead标志的逻辑和十进制完全一致。状态压缩与剪枝dp[pos][cnt]的第二维大小是K1。由于K60pos60内存是足够的。可以进行一个有效的剪枝在递归中如果cnt K可以直接返回0因为后面无论怎么填‘1’的个数只会增加不可能再等于K了。与组合数学的联系这个问题实际上可以用组合数直接求解在无上限限制时。数位DP相当于自动化、通用化地处理了“上限限制”这个麻烦。理解这一点有助于加深对DP状态的理解。6. 数位DP的难点精析与调试技巧经过上面三个例题你应该对模板和常见状态设计有了了解。但在实战中还有几个难点和易错点需要特别注意。难点一状态设计的抽象与简化状态state是数位DP最难的部分。它需要精确描述“前缀信息对后续决策的影响”。好的状态应该包含足够信息能唯一确定后续的计数情况。尽可能小状态空间太大比如把整个前缀作为状态会导致记忆化失效或超内存。 对于“包含特定子串”类问题如“666”常用的技巧是使用自动机状态如0,1,2,3或KMP的next数组思想来记录匹配进度。对于更复杂的数字性质如“能被某个数整除”状态可能需要记录前缀模某个数的余数。难点二前导零lead的正确处理前导零的处理是数位DP错误的主要来源。必须想清楚前导零是否影响状态例如统计数字‘0’时前导零的‘0’不算统计数字‘1’时前导零无影响。前导零是否影响数字的合法性例如有些题目要求数字不能有前导零即数字是正数且没有多余的0开头这时在递归边界如果lead仍然为true说明构造的数字是0可能需要根据题意判断是否合法。记忆化与lead的关系记忆化数组dp[pos][state]默认是在leadfalse即已经开始了有效数字的前提下定义的。leadtrue意味着前面的位都是0此时即使state相同后续的计数也可能和leadfalse时完全不同比如对数字0的统计。所以只有当!lead !limit时才能使用记忆化的结果。难点三上限限制limit的理解limit标志决定了当前位的选择范围。它是保证我们计算的是[0, x]区间而不是所有位数的全排列的关键。在limittrue时当前位的选择受限于原数x的对应位并且递归下去的子问题也可能受限于更低位。只有limitfalse时当前位及其所有低位都可以自由选择0-9或0-1此时子问题是“通用的”可以被记忆化。常见错误在记忆化判断或存储时忽略了limit条件导致计算结果错误通常偏大。调试技巧小数据暴力对拍写一个朴素的暴力算法for循环遍历区间逐个判断用于验证数位DP程序在小数据范围如1到10000内的正确性。这是最有效的调试手段。打印递归树在DFS函数开头打印pos, state, lead, limit等参数观察递归过程。特别关注limit从true变为false的时刻以及lead的变化。关注边界条件重点测试L0,L1,R0,R9,R10,R99等边界情况以及LR的情况。状态值验证在记忆化存储和读取时可以打印dp数组的值看是否和预期一致。对于state设计复杂的问题可以手动计算几个小例子验证状态转移的正确性。7. 举一反三数位DP的常见变体与扩展思路掌握了基础模型我们可以看看数位DP还能解决哪些变体问题这有助于你应对竞赛中的新题。变体一统计“数位和”或“数位积”满足条件的数问题示例统计区间内各位数字之和为S或之积为P的数字个数。状态设计state直接记录到当前位的和或积。注意“积”可能很大需要观察范围。有时积可以转化为“质因子分解”的状态或者如果P很小可以直接记录。技巧数位和的范围是有限的最大为9*位数适合直接作为状态。数位积则可能需要离散化或特殊处理。变体二统计“回文数”、“单调数”等具有整体性质的数问题示例统计区间内的回文数个数。状态设计这通常需要同时从高位和低位向中间构造。状态可能需要记录已经匹配的前缀或后缀或者记录当前构造到中间的位置。这类问题状态设计更灵活有时需要结合其他算法思想。变体三与数论结合如“能被M整除的数”问题示例统计区间内能被M整除的数字个数。状态设计state记录当前前缀模M的余数r。那么从当前位继续构造新的余数就是(r * 10 i) % M。递归边界时判断余数是否为0。技巧这是数位DP与模运算结合的经典应用。状态大小是O(M)。变体四求满足条件的第K小数扩展POJ3208解法二分答案数位DP检验。这是非常通用的方法。先二分一个答案mid用数位DP计算[1, mid]内满足条件的数的个数cnt。如果cnt K说明答案比mid大否则答案小于等于mid。不断二分直到找到最小的mid使得cnt K。变体五多维状态与复杂约束问题示例统计区间内数字‘4’和‘7’出现次数之差不超过T的数字个数。状态设计state需要两个维度分别记录‘4’和‘7’的出现次数或者记录它们的差值。由于差值可能为负需要加一个偏移量如T使其变为非负数组下标。扩展思路从记忆化搜索到递推我们讲解的一直是记忆化搜索DFSMemo的写法因为它直观易于理解和调试。实际上数位DP也可以写成纯递推迭代的形式通常称为“数位DP的递推写法”或“Digital DP的DP表填充”。递推写法的代码有时更简洁但思维难度稍高不如记忆化搜索那样能清晰地体现“按位构造”的过程。对于初学者强烈建议先精通记忆化搜索的写法。数位DP的精髓在于“按位确定”和“状态压缩”。它将一个庞大的区间计数问题分解为对每个数位独立的、带状态的决策过程。理解并熟练运用lead和limit这两个标志是写好数位DP的关键。从简单的统计出现次数到复杂的模式匹配和数论问题其内核都是一致的。多练习多思考状态的设计你就能将这种强大的计数工具运用自如。
1. 从一道“数数”题说起为什么我们需要数位DP如果你刷过一些算法题尤其是像POJ、蓝桥杯这类竞赛题大概率遇到过这样一类问题给你一个区间[L, R]让你统计在这个区间内所有数字的十进制或二进制表示中某个特定数字比如‘6’出现了多少次或者满足某种特殊性质的数字有多少个。比如POJ2282 “The Counting Problem” 就是让你统计0-9每个数字在给定区间内出现的总次数。第一次遇到这种题你可能会想“这还不简单从L到R遍历每个数拆开每一位数一下不就行了”然后你兴冲冲地写了个循环一提交——Time Limit Exceeded超时。为什么因为L和R的范围可能非常大比如1 L R 2,000,000,000。20亿次的循环和数位拆分对于计算机来说也是沉重的负担。这时你就需要一个更“聪明”的算法它不需要遍历每一个数而是通过分析数字的结构直接“计算”出结果。这就是数位动态规划Digit DP的核心价值所在。数位DP解决的是一类与数字的“位数”和“位值”相关的计数问题。它把一个大范围的、看似需要暴力枚举的问题转化成了一个基于数位位置和状态记忆的、高效的计算过程。理解并掌握数位DP不仅能让你轻松解决POJ2282、POJ3208寻找第N个包含“666”的数字这类经典题目更是应对蓝桥杯等竞赛中计数问题的利器。今天我们就以这几个经典问题为脉络彻底拆解数位DP的思维框架和实现细节。2. 数位DP的核心思想与通用“记忆化搜索”模板数位DP之所以高效是因为它利用了数字的一个关键特性前缀无关性。举个例子当我们统计1到54321之间有多少个包含连续“666”的数时对于前两位是“54”的所有五位数即54000到54999它们后续三位百位、十位、个位中“666”的出现情况只取决于当前是否已经出现了“666”以及最后几位是什么而和前面的“54”具体是多少没有直接关系只要不超过上界。这就产生了大量重复的子问题。数位DP最经典、也最易于理解的实现方式是记忆化搜索DFS with Memoization。我们用一个DFS函数来“构造”数字从最高位向最低位递归在递归过程中记录关键状态并利用记忆化数组避免重复计算。下面给出一个解决“统计区间[0, x]内满足条件P的数字个数”的通用模板。我们通常先实现一个函数solve(int x)它返回[0, x]内满足条件的数的个数那么区间[L, R]的答案就是solve(R) - solve(L-1)。#include bits/stdc.h using namespace std; using ll long long; // 将数字x的每一位分解到数组a中低位在前方便递归长度len int a[20]; ll dp[20][state]; // 状态数组维度根据具体问题定义 ll dfs(int pos, int state, bool lead, bool limit) { // pos: 当前处理到第几位从0开始即最低位 // state: 当前的状态记录之前位的信息如前缀中特定数字的个数、是否已出现特定模式等 // lead: 前导零标志。true表示前面的位都是0即我们构造的数字目前有效部分还没开始 // limit: 上限标志。true表示当前位能填的数字受原始数字x对应位的限制 // 递归边界所有位都处理完毕 if (pos -1) { return check(state) ? 1 : 0; // 根据最终状态判断是否计入答案 } // 记忆化只有在无前导零且无上限限制时才能直接使用之前计算的结果 // 因为前导零和上限限制会影响后续选择使得子问题不通用 if (!lead !limit dp[pos][state] ! -1) { return dp[pos][state]; } int up limit ? a[pos] : 9; // 当前位能填的最大数字 ll ans 0; for (int i 0; i up; i) { // 计算下一位的状态 int next_state get_next_state(state, i, lead); // 核心递归下一位更新状态更新前导零和上限标志 ans dfs(pos - 1, next_state, lead i 0, limit i up); } // 记录状态同样只在无限制时记录 if (!lead !limit) { dp[pos][state] ans; } return ans; } ll solve(ll x) { if (x 0) return 0; // 根据题意有时0需要特殊处理 int len 0; while (x) { a[len] x % 10; x / 10; } memset(dp, -1, sizeof(dp)); // 初始化DP数组为-1未计算 // 从最高位开始递归初始状态通常为0有前导零受上限限制 return dfs(len - 1, 0, true, true); }这个模板中有四个关键参数理解它们至关重要pos(位置)表示当前正在处理数字的第几位。递归深度。state(状态)这是数位DP的灵魂用于记录从最高位到当前pos位不含为止我们所关心的所有信息。不同的题目state的定义完全不同。例如统计数字‘d’出现次数state可以是一个整数记录到目前为止‘d’出现了几次。寻找包含“666”的数state可以记录当前末尾连续‘6’的个数0, 1, 2或者用一个状态码表示是否已经出现了“666”。二进制问题统计1的个数state可以记录当前1的个数。lead(前导零)这是一个非常容易出错的点。前导零是指我们构造的数字中高位连续的0。例如数字0054前两个0就是前导零。为什么需要它影响状态计算对于统计数字‘0’出现次数的问题前导零的‘0’不应该被计入。lead为true时当前位的‘0’是前导零不计入状态。影响记忆化状态(pos, state)只有在lead为false即已经开始了有效数字时才是通用的可以记忆化。否则state可能是在前导零背景下计算出来的不适用于非前导零的情况。limit(上限限制)表示当前位填的数字是否受到原始数字x对应位的限制。例如x543当前处理百位pos2如果前面所有位都填的和x一样即目前构造的前缀等于x的前缀那么当前位最多只能填5limittrue。如果前面有任何一位填的比x对应位小比如十位我们填了3而x的十位是4那么从这一位开始后面所有位都可以填0-9limitfalse。它同样影响记忆化。只有limitfalse时后续位的选择才是完全自由的0-9子问题才是通用的才能被记忆化。一个核心技巧我们通常把数字分解成低位在数组前。这样pos从len-1递归到0更符合我们从高位向低位思考的习惯。dfs函数中的pos表示“还剩多少位待处理”当pos -1时表示所有位都处理完了。3. 实战拆解一POJ2282 The Counting Problem统计数字出现次数问题描述给定两个整数a和b0 a, b 1e8对于每个数字d (0-9)统计在[a, b]包含区间内所有整数的十进制表示中数字d出现的总次数。思路分析这是最经典的数位DP入门题。我们可以对每个数字d (0-9)分别计算。定义state为从最高位到当前位数字d已经出现的次数cnt。状态设计dp[pos][cnt]表示处理到第pos位时数字d已经出现了cnt次在无前导零、无上限限制的条件下从这一位往后能构造出多少个数这些数最终都会被计入答案但我们需要在递归边界根据最终的cnt来加权计算总次数。但是注意我们最终要的是出现次数的总和而不是数字的个数。如果只在边界返回1或0我们只能算出有多少个数字包含d而不是d出现的总次数。解决方案修改DFS的返回值。让DFS返回一个pairll, ll第一个值cnt表示满足条件的数字个数第二个值sum表示这些数字中数字d出现的总次数。递归过程从下一位DFS获取结果(next_cnt, next_sum)。当前位如果填的是数字d则对总次数的贡献是next_cnt因为当前位的这个d会在next_cnt个数字的每一位都出现一次加上next_sum来自后续位的贡献。当前位如果填的不是数字d则贡献只有next_sum。细节处理对于数字0需要特别小心前导零。只有当lead为false时当前位的0才被视为有效数字0并可能被统计。核心代码片段pairll, ll dfs(int pos, int cnt, bool lead, bool limit, int digit) { if (pos -1) { return {1, cnt}; // 一个数字贡献了cnt次 } if (!lead !limit dp[pos][cnt].first ! -1) { return dp[pos][cnt]; } int up limit ? a[pos] : 9; pairll, ll ans {0, 0}; for (int i 0; i up; i) { bool is_lead lead (i 0); int next_cnt cnt; if (!is_lead i digit) { // 非前导零且是目标数字 next_cnt; } auto res dfs(pos - 1, next_cnt, is_lead, limit i up, digit); ans.first res.first; // 数字个数累加 ans.second res.second ( (!is_lead i digit) ? res.first : 0 ); // 次数累加后续位的总次数 当前位的贡献如果当前位是d } if (!lead !limit) { dp[pos][cnt] ans; } return ans; }避坑点状态定义与返回值这是本题的关键。如果只返回数字个数无法直接求出总次数。必须让DFS携带“贡献值”信息。前导零与数字0这是最容易WA错误答案的地方。必须明确只有非前导零状态的0才是数字0才需要被统计。在判断i digit时一定要结合lead标志。记忆化维度dp数组的第二维cnt大小是多少最坏情况下一个8位数1e8每个位都是dcnt最大为8。但安全起见可以设为当前剩余位数pos1或者一个稍大的常数如20。通过分别对0-9每个数字调用一次solve函数内部调用DFS我们就能得到每个数字在区间内的总出现次数。时间复杂度为O(10 * 位数 * 状态数 * 10)对于题目范围绰绰有余。4. 实战拆解二POJ3208 启示录寻找第N个包含“666”的数问题描述寻找第N个N可达5e7包含连续三个“6”即“666”的正整数。例如第一个是666第二个是1666第三个是2666第四个是3666第五个是4666第六个是5666第七个是6660注意这里6660中的666是连续的。思路分析这不是一个区间计数问题而是一个“按序查找”问题。一种方法是二分答案数位DP检验。即二分一个数字mid用数位DP计算[1, mid]之间有多少个包含“666”的数如果个数N则答案在右边否则在左边。直到找到最小的mid使得[1, mid]内的个数N。因此核心还是实现一个数位DP函数count(long long x)返回[1, x]内包含“666”的数的个数。状态设计我们需要记录一个状态来表示当前末尾连续‘6’的个数以及是否已经出现了“666”。 一个经典的设计是state 0: 当前末尾没有连续的6。state 1: 当前末尾有1个连续的6。state 2: 当前末尾有2个连续的6。state 3: 已经出现了“666”无论末尾是什么。状态转移如果当前state 0或1或2当前位填6state增加1如果state已经是2则变为3。当前位填其他数字state重置为0。如果当前state 3无论当前位填什么state都保持为3已经满足条件。递归边界当pos -1时如果state 3返回1否则返回0。核心代码片段ll dp[20][4]; // dp[pos][state] ll dfs(int pos, int state, bool lead, bool limit) { if (pos -1) { return state 3 ? 1 : 0; } if (!lead !limit dp[pos][state] ! -1) { return dp[pos][state]; } int up limit ? a[pos] : 9; ll ans 0; for (int i 0; i up; i) { int next_state state; if (state 3) { if (i 6) { next_state state 1; if (next_state 3) next_state 3; } else { next_state 0; } } // 如果state已经是3next_state保持为3 ans dfs(pos - 1, next_state, lead i 0, limit i up); } if (!lead !limit) { dp[pos][state] ans; } return ans; }二分查找实现long long findNth(int N) { long long left 1, right 1e18; // 一个足够大的上界 long long ans right; while (left right) { long long mid left (right - left) / 2; if (count(mid) N) { // count(mid)返回[1,mid]中满足条件的数的个数 ans mid; right mid - 1; } else { left mid 1; } } return ans; }避坑点状态3的设计一旦进入状态3已出现“666”就必须永远保持为3无论后面填什么数字。这确保了只要前缀满足了条件整个数就被计入。前导零的处理在这个问题中前导零不影响“666”模式的识别。因为前导零不是‘6’。所以lead标志主要用来控制记忆化的条件在状态转移中当lead为true且i0时next_state应该保持为0因为前导零不是有效数字不参与连续‘6’的计数。二分边界N可以很大5e7第N个包含“666”的数会非常大二分的右边界right必须设得足够大。1e18是一个比较安全的选择。二分时注意是寻找下界第一个使count(mid) N的mid。这个方法将“查找第N个”的问题转化为了O(log(MAX))次“计数问题”每次计数是数位DP的O(位数*状态数*10)效率非常高。5. 实战拆解三第十二届蓝桥杯国赛CB组H题——二进制问题统计1的个数为K的数问题描述给定一个区间[L, R]L, R可达1e18和一个整数K0 K 60统计该区间内有多少个整数的二进制表示中恰好有K个‘1’。思路分析这是数位DP从十进制向二进制的一个直接迁移。数位DP的本质是与进制无关的它处理的是“按位计数”。我们只需要把模板中的十进制位0-9换成二进制位0-1把up从9换成1即可。状态设计state可以直接定义为当前已经放置的‘1’的个数cnt。DP数组dp[pos][cnt]表示处理到第pos位时已经使用了cnt个‘1’在无前导零、无上限限制的情况下能构造出多少个数。这里前导零在二进制中同样重要因为高位的‘0’不影响‘1’的计数但影响数字的有效性不过对于统计‘1’的个数前导零的‘0’显然不计为‘1’。递归边界当pos -1时所有位处理完毕判断cnt K相等则返回1否则返回0。核心代码片段ll dp[70][70]; // pos最大约为60因为1e18 2^60cnt最大为K ll dfs(int pos, int cnt, bool lead, bool limit) { if (pos -1) { return cnt K ? 1 : 0; } if (!lead !limit dp[pos][cnt] ! -1) { return dp[pos][cnt]; } int up limit ? a[pos] : 1; // 二进制位最大为1 ll ans 0; for (int i 0; i up; i) { bool is_lead lead (i 0); int next_cnt cnt; if (i 1) { next_cnt; } // 剪枝如果next_cnt已经超过K后续无论怎么填都不可能满足条件可以跳过 // 但在这个简单循环中剪枝效果不明显可写可不写 ans dfs(pos - 1, next_cnt, is_lead, limit i up); } if (!lead !limit) { dp[pos][cnt] ans; } return ans; }二进制数位分解ll solve(ll x) { if (x 0) return 0; int len 0; while (x) { a[len] x 1; // 取二进制最低位 x 1; } // 注意如果x0len为0需要特殊处理因为0的二进制表示中‘1’的个数为0 if (len 0) { // 即x0 a[0] 0; len 1; } memset(dp, -1, sizeof(dp)); return dfs(len - 1, 0, true, true); }避坑点与优化0的处理solve(0)需要单独处理。因为我们的数位分解循环while(x)在x0时不会执行导致len0。而dfs(len-1, ...)会访问非法索引。可以在solve开始判断如果x0直接返回K0 ? 1 : 0。或者在分解后如果len0手动设置len1, a[0]0。前导零在二进制中前导零同样不贡献‘1’。所以lead标志的逻辑和十进制完全一致。状态压缩与剪枝dp[pos][cnt]的第二维大小是K1。由于K60pos60内存是足够的。可以进行一个有效的剪枝在递归中如果cnt K可以直接返回0因为后面无论怎么填‘1’的个数只会增加不可能再等于K了。与组合数学的联系这个问题实际上可以用组合数直接求解在无上限限制时。数位DP相当于自动化、通用化地处理了“上限限制”这个麻烦。理解这一点有助于加深对DP状态的理解。6. 数位DP的难点精析与调试技巧经过上面三个例题你应该对模板和常见状态设计有了了解。但在实战中还有几个难点和易错点需要特别注意。难点一状态设计的抽象与简化状态state是数位DP最难的部分。它需要精确描述“前缀信息对后续决策的影响”。好的状态应该包含足够信息能唯一确定后续的计数情况。尽可能小状态空间太大比如把整个前缀作为状态会导致记忆化失效或超内存。 对于“包含特定子串”类问题如“666”常用的技巧是使用自动机状态如0,1,2,3或KMP的next数组思想来记录匹配进度。对于更复杂的数字性质如“能被某个数整除”状态可能需要记录前缀模某个数的余数。难点二前导零lead的正确处理前导零的处理是数位DP错误的主要来源。必须想清楚前导零是否影响状态例如统计数字‘0’时前导零的‘0’不算统计数字‘1’时前导零无影响。前导零是否影响数字的合法性例如有些题目要求数字不能有前导零即数字是正数且没有多余的0开头这时在递归边界如果lead仍然为true说明构造的数字是0可能需要根据题意判断是否合法。记忆化与lead的关系记忆化数组dp[pos][state]默认是在leadfalse即已经开始了有效数字的前提下定义的。leadtrue意味着前面的位都是0此时即使state相同后续的计数也可能和leadfalse时完全不同比如对数字0的统计。所以只有当!lead !limit时才能使用记忆化的结果。难点三上限限制limit的理解limit标志决定了当前位的选择范围。它是保证我们计算的是[0, x]区间而不是所有位数的全排列的关键。在limittrue时当前位的选择受限于原数x的对应位并且递归下去的子问题也可能受限于更低位。只有limitfalse时当前位及其所有低位都可以自由选择0-9或0-1此时子问题是“通用的”可以被记忆化。常见错误在记忆化判断或存储时忽略了limit条件导致计算结果错误通常偏大。调试技巧小数据暴力对拍写一个朴素的暴力算法for循环遍历区间逐个判断用于验证数位DP程序在小数据范围如1到10000内的正确性。这是最有效的调试手段。打印递归树在DFS函数开头打印pos, state, lead, limit等参数观察递归过程。特别关注limit从true变为false的时刻以及lead的变化。关注边界条件重点测试L0,L1,R0,R9,R10,R99等边界情况以及LR的情况。状态值验证在记忆化存储和读取时可以打印dp数组的值看是否和预期一致。对于state设计复杂的问题可以手动计算几个小例子验证状态转移的正确性。7. 举一反三数位DP的常见变体与扩展思路掌握了基础模型我们可以看看数位DP还能解决哪些变体问题这有助于你应对竞赛中的新题。变体一统计“数位和”或“数位积”满足条件的数问题示例统计区间内各位数字之和为S或之积为P的数字个数。状态设计state直接记录到当前位的和或积。注意“积”可能很大需要观察范围。有时积可以转化为“质因子分解”的状态或者如果P很小可以直接记录。技巧数位和的范围是有限的最大为9*位数适合直接作为状态。数位积则可能需要离散化或特殊处理。变体二统计“回文数”、“单调数”等具有整体性质的数问题示例统计区间内的回文数个数。状态设计这通常需要同时从高位和低位向中间构造。状态可能需要记录已经匹配的前缀或后缀或者记录当前构造到中间的位置。这类问题状态设计更灵活有时需要结合其他算法思想。变体三与数论结合如“能被M整除的数”问题示例统计区间内能被M整除的数字个数。状态设计state记录当前前缀模M的余数r。那么从当前位继续构造新的余数就是(r * 10 i) % M。递归边界时判断余数是否为0。技巧这是数位DP与模运算结合的经典应用。状态大小是O(M)。变体四求满足条件的第K小数扩展POJ3208解法二分答案数位DP检验。这是非常通用的方法。先二分一个答案mid用数位DP计算[1, mid]内满足条件的数的个数cnt。如果cnt K说明答案比mid大否则答案小于等于mid。不断二分直到找到最小的mid使得cnt K。变体五多维状态与复杂约束问题示例统计区间内数字‘4’和‘7’出现次数之差不超过T的数字个数。状态设计state需要两个维度分别记录‘4’和‘7’的出现次数或者记录它们的差值。由于差值可能为负需要加一个偏移量如T使其变为非负数组下标。扩展思路从记忆化搜索到递推我们讲解的一直是记忆化搜索DFSMemo的写法因为它直观易于理解和调试。实际上数位DP也可以写成纯递推迭代的形式通常称为“数位DP的递推写法”或“Digital DP的DP表填充”。递推写法的代码有时更简洁但思维难度稍高不如记忆化搜索那样能清晰地体现“按位构造”的过程。对于初学者强烈建议先精通记忆化搜索的写法。数位DP的精髓在于“按位确定”和“状态压缩”。它将一个庞大的区间计数问题分解为对每个数位独立的、带状态的决策过程。理解并熟练运用lead和limit这两个标志是写好数位DP的关键。从简单的统计出现次数到复杂的模式匹配和数论问题其内核都是一致的。多练习多思考状态的设计你就能将这种强大的计数工具运用自如。
![2026学术工具专业测评｜Paperxie全维度性能实测报告[特殊字符]](http://pic.xiahunao.cn/yaotu/2026学术工具专业测评｜Paperxie全维度性能实测报告[特殊字符])
![凭什么稳居论文工具顶流[特殊字符]Paperxie综合实力深度全解析](http://pic.xiahunao.cn/yaotu/凭什么稳居论文工具顶流[特殊字符]Paperxie综合实力深度全解析)
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
