数位DP实战：从蓝桥杯真题掌握二进制问题与通用解法

1. 项目概述从一道国赛真题看数位DP的精髓最近在复盘蓝桥杯的历年国赛真题第十二届那道“二进制问题”让我印象很深。它初看像是一道普通的组合数学题但数据范围一出来N最大到10^18暴力枚举的路就被彻底堵死了。这正是数位动态规划Digit DP的典型用武之地。很多刚接触数位DP的朋友会觉得它概念抽象、状态设计绕其实它的核心思想非常直观把一个大数的处理转化为对其每一位数字的、带有约束条件的“计数”过程。这道题就是一个绝佳的学习样本它不涉及复杂的进制转换技巧直指数位DP最本质的“数位限制”与“状态记忆”思想。通过拆解这道题我们不仅能学会如何解决“在[1, N]区间内二进制表示中恰好有K个1的数字个数”这一问题更能掌握数位DP的通用解题框架与状态设计心法这种思路同样适用于十进制或其他进制下关于数字特性的统计问题。无论你是正在备赛蓝桥杯还是想深入理解动态规划的一个细分领域这篇从实战出发的拆解都值得一看。2. 问题核心与暴力解法的局限题目描述通常很简洁给定一个正整数NN ≤ 10^18和一个整数KK ≥ 0求[1, N]区间内有多少个正整数的二进制表示中恰好包含K个‘1’。举个例子N13二进制1101K2。那么在1到13之间二进制表示恰好有2个1的数字有3011、5101、6110、91001、101010、121100。一共6个。最直接的想法是暴力循环。从1遍历到N对每个数转换成二进制字符串数其中‘1’的个数如果等于K则计数器加一。这个思路清晰易懂写起来也就十来行代码。但为什么行不通呢关键在于数据规模N最大可达10^18。这是一个天文数字即使每秒能处理1亿个数这已经是极高的性能要求遍历完也需要超过300年。更不用说每个数还要进行进制转换和字符统计开销巨大。因此暴力法在竞赛中毫无悬念会超时Time Limit Exceeded。这迫使我们寻找更聪明的办法。我们注意到数字的二进制表示天然具有“数位”结构。统计满足条件的数字个数实质上是在所有可能的、不超过N的二进制串中筛选出那些‘1’的个数等于K的串。这引导我们想到按位数位进行决策并利用动态规划来高效地统计所有可能情况——这就是数位DP。注意数位DP的“数位”并不特指十进制。任何进制下的每一位都可以视为“数位”二进制只是其中最简单的一种因为每位只有0和1两种选择这反而降低了状态设计的复杂度更适合初学者理解。3. 数位DP通用框架与状态设计心法数位DP通常采用记忆化搜索Memoization Search的实现方式它比递推更直观也更容易处理“上界限制”。其核心是定义一个递归函数dfs(pos, count, limit)并配合一个记忆化数组dp[pos][count]来避免重复计算。我们来拆解这个函数每个参数的含义pos(当前处理位)表示我们正在从高位到低位处理这个二进制数的第几位。通常我们会把数字转换成字符串或数组来处理pos就是当前下标。count(关键状态)表示在已经处理完的高位中我们已经放置了多少个‘1’。这是题目要求恰好K个1的核心状态也是我们记忆化的依据。limit(上限限制)这是一个布尔值表示当前位是否受到原始数字N的对应位的限制。如果limit为真那么当前位能填的最大数字不能超过N在pos位上的值如果为假那么当前位可以填0或1在二进制中。dp[pos][count]数组用于记忆化。它表示在位置pos已经使用了count个‘1且**没有上限限制**limitfalse的情况下从这一位开始往后构造数字所有可能的结果数。为什么要求limitfalse因为limittrue的情况是与特定的N绑定的不具有通用性无法被复用。只有无限制的状态才能被记忆化。状态设计的心法数位DP的状态设计本质上是将那些会影响后续决策的、且与具体数字无关的条件抽象出来。在这道题里唯一影响后续决策的就是“已经用了多少个1”count因为它决定了我们后续还能用多少个1来满足总数K的要求。而“是否紧贴上界”limit是一个过程变量它决定了当前位的选择范围但它本身是“一次性”的所以不作为记忆化数组的维度而是作为递归函数的一个参数来传递。理解了框架我们来看如何将其应用到二进制问题上。4. 针对“二进制问题”的DP状态与转移方程对于本题我们定义记忆化数组dp[pos][cnt]表示当处理到第pos位时前面已经使用了cnt个‘1’并且当前位没有受到N的限制即limitfalse时从这一位往后能构造出的、所有合法数字的个数。这里“合法”最终意味着整个数字的‘1’的总数等于K。递归函数dfs(pos, cnt, limit)的流程如下递归边界如果pos已经超过了数字的最高位即所有位都处理完毕那么我们就得到了一个完整的数字。此时判断已使用的‘1’的数量cnt是否等于K。如果相等则这是一个有效数字返回1否则返回0。记忆化查询如果limit为false即当前位无限制并且dp[pos][cnt]已经被计算过不等于初始值-1那么我们可以直接返回这个缓存的结果。这是提升效率的关键。确定当前位上限计算当前位可以填的最大数字up。如果limit为true则up等于N在pos位上的值0或1如果为false则up为1二进制下最大数字。枚举与决策初始化一个结果变量res 0。然后枚举当前位i从0到up。如果i 0那么‘1’的计数cnt保持不变。如果i 1那么新的计数为cnt 1。我们需要判断新的cnt是否已经超过了K。如果超过了那么后续无论怎么填总‘1’数都会超过K可以直接跳过剪枝因为继续递归没有意义。计算新的limit状态next_limit limit (i up)。这意味着只有当前位是紧贴上界的limittrue并且我这一位填的正是上界值up时下一位才会继续受到限制否则下一位就自由了limitfalse。递归与汇总对于每一个合法的i递归调用dfs(pos1, new_cnt, next_limit)将结果累加到res中。记忆化存储在递归返回前如果当前是limitfalse的无限制状态将res存入dp[pos][cnt]以便后续复用。返回结果返回res。主函数中我们将数字N转换为二进制字符串或数组然后初始化dp数组为-1表示未计算调用dfs(0, 0, true)。注意初始状态从第0位最高位开始已用‘1’数为0并且初始状态是受到限制的limittrue因为我们构造的数字不能超过N。实操心得二进制转换时注意处理前导零。但在本题的dfs过程中我们是从最高有效位开始处理的前导零自然被忽略因为高位为0不影响数值且我们统计的是1的个数。这是二进制数位DP比十进制简单的一个地方十进制处理前导零有时需要额外状态。5. 完整代码实现与逐行解析下面我们用C来实现上述思路的代码并加上详细注释。选择C是因为它是算法竞赛的主流语言执行效率高。#include iostream #include cstring #include vector using namespace std; long long N; int K; long long dp[70][70]; // dp[pos][cnt] 记忆化数组 vectorint digits; // 存放N的二进制每一位从高位到低位 /** * 数位DP记忆化搜索函数 * param pos 当前处理到的位数从0开始指向digits数组 * param cnt 当前已经使用的‘1’的个数 * param limit 当前位是否受到上界N的限制 * return 从当前状态开始能构造出的合法数字个数 */ long long dfs(int pos, int cnt, bool limit) { // 1. 递归边界所有位都处理完了 if (pos digits.size()) { // 判断是否恰好用了K个‘1’ return cnt K ? 1 : 0; } // 2. 记忆化查询只有在无限制状态下才能复用 if (!limit dp[pos][cnt] ! -1) { return dp[pos][cnt]; } // 3. 确定当前位能填的数字上限 int up limit ? digits[pos] : 1; // 二进制每位最大是1 long long res 0; // 4. 枚举当前位的所有可能选择 for (int i 0; i up; i) { int new_cnt cnt (i 1); // 如果当前位填1则计数加1 // 重要剪枝如果已经用的1超过了K后续无论如何都会超过K直接跳过 if (new_cnt K) { continue; } // 计算下一位是否受限当前受限且填到了上限则下一位继续受限 bool next_limit limit (i up); res dfs(pos 1, new_cnt, next_limit); } // 5. 记忆化存储只存储无限制状态的结果 if (!limit) { dp[pos][cnt] res; } return res; } /** * 主求解函数计算[1, N]中二进制表示恰好有K个1的数字个数 * param n 上界N * param k 目标1的个数K * return 满足条件的数字个数 */ long long solve(long long n, int k) { N n; K k; // 将N转换为二进制位数组高位在前 digits.clear(); while (n 0) { digits.push_back(n % 2); n / 2; } reverse(digits.begin(), digits.end()); // 反转使得digits[0]是最高位 // 初始化记忆化数组为-1表示未计算 memset(dp, -1, sizeof(dp)); // 注意dfs从最高位开始初始已用cnt0且初始状态是受限的limittrue return dfs(0, 0, true); } int main() { long long n; int k; // 假设输入为 N 和 K cin n k; cout solve(n, k) endl; return 0; }关键点解析与避坑指南dp数组大小dp[70][70]为什么是70因为N最大为10^18其二进制位数最多不超过60位2^60 ≈ 1.15e18。这里取70是为了留有余地防止边界错误。cnt的维度也是70因为最多不会超过二进制位数。digits数组的顺序我们通过while循环得到的是N的二进制表示的低位在前。但数位DP习惯从高位向低位处理所以必须用reverse反转一下。这是很容易出错的一步。记忆化的条件!limit这是数位DP记忆化的精髓也是新手最容易混淆的地方。一定要理解dp[pos][cnt]定义的是无限制状态下的结果。因为limittrue意味着前面所有位都紧贴N的上界这个状态是“唯一”的依赖于具体的N不能被其他搜索路径复用。只有脱离了上界限制后面的选择才是“自由”的状态才可以被共享。剪枝优化if (new_cnt K)这是一个非常重要的优化。如果在某一位放置1后导致已用1的个数超过了K那么之后无论怎么填即使全填0总1的个数也必然超过K不可能满足条件。因此可以直接跳过这个分支不再进行无谓的递归。这能显著减少搜索空间。初始调用与结果dfs(0, 0, true)的初始limit是true因为我们从构造数字的一开始就不能超过N。这个函数返回的结果就是区间[1, N]内所有满足条件的数的个数。6. 从二进制到通用数位DP的思维扩展通过这道二进制问题我们掌握了数位DP的基本套路。这个套路具有很强的扩展性可以解决一大类“统计区间内满足某种数位特性的数字个数”的问题。关键在于状态设计的灵活变化。状态设计扩展举例十进制下数字和问题求[L, R]内各位数字之和为S的数字个数。状态变化dp[pos][sum]sum表示已处理位数字之和。转移枚举当前位i从0到9受limit限制new_sum sum i。边界pos结束时判断sum S。包含特定数字或模式求[L, R]内不包含数字‘4’的数字个数。状态变化可以不需要额外的计数状态但需要一个标志位hasFour。更通用的做法是如果限制条件更复杂如不能连续出现两个‘6’状态就需要包含前一位的信息例如dp[pos][pre]pre表示前一位填的数字。模运算相关求[L, R]内能被M整除的数字个数。状态变化dp[pos][mod]mod表示当前构造的数字对M取模的结果。转移new_mod (mod * 10 i) % M十进制下。边界pos结束时判断mod 0。通用解题步骤总结问题转化将区间[L, R]的问题转化为[1, R]的结果减去[1, L-1]的结果前缀和思想。数位化将上界数字转换为数位数组如字符串、vector。设计状态分析满足题目条件需要记录哪些与具体数字无关的、影响后续决策的信息。常见的有计数如1的个数、数字和、模数、前导零标志、前一位数字等。定义DP数组dp[pos][state1][state2]...通常不包含limit维度。编写DFS函数参数(pos, state..., limit)边界返回条件判断。记忆化if (!limit dp[pos][state] ! -1) return ...枚举当前位计算新状态进行剪枝如果可能。递归累加结果。记忆化存储在!limit条件下。初始化与调用初始化DP数组为-1调用dfs(0, init_state, true)。7. 常见问题与调试技巧实录在实际编写和调试数位DP时以下几个坑点我几乎每次都会提醒自己注意Q1结果总是偏大或偏小检查点1limit的记忆化条件。这是最最常见的错误。确保只在!limit时才读取和存储dp数组。如果你错误地把limittrue的状态也存了会导致结果重复计算因为不同的受限路径可能对应同一个(pos, cnt)状态但它们后续的选择空间其实是不同的。检查点2递归边界返回值。仔细核对pos digits.size()时返回的条件。本题是cnt K ? 1 : 0。如果是求数字和可能就是sum S ? 1 : 0。返回错误会导致基础计数单元出错。检查点3digits数组的生成。确认是从最高位到最低位存储的吗reverse了吗处理N0的情况了吗本题区间是[1,N]所以N0时直接返回0但digits数组会为空DFS边界需要能正确处理。Q2程序运行超时即使用了记忆化排查点1状态设计是否合理状态数量是pos数 × 状态空间大小。如果状态空间太大例如你设计了一个dp[pos][sum][mod][pre]每个维度范围都很大那么记忆化也救不了。需要思考状态能否合并或简化。排查点2剪枝是否充分像本题中的if (new_cnt K) continue;就是很好的剪枝。在其他问题中也要积极寻找类似的“提前终止无效搜索”的条件。排查点3dp数组初始化开销。每次调用solve都memset整个dp数组如果dp很大比如dp[20][200][200]会有一定开销。在多次查询不同[L,R]区间的问题中可以考虑复用或更精细的初始化。Q3如何处理前导零情况分析在统计数字本身属性如1的个数、数字和时前导零不影响结果通常无需特殊处理就像本题一样。需要处理的情况当题目条件与前导零有关时例如“统计不含前导零的、各位数字互不相同的数字”。这时需要在状态中增加一个isLead参数表示当前是否还处于前导零阶段。在isLeadtrue且当前位填0时isLead保持为true且cnt等状态不更新因为前导零不计入统计。调试技巧小数据对拍写一个暴力程序用于N较小比如N10000的情况。用你的数位DP程序与暴力程序的结果进行对比快速定位错误。打印递归树在DFS函数入口打印pos, cnt, limit和当前位选择i可以非常清晰地看到程序的执行路径帮助你理解limit是如何传递和变化的以及记忆化是否生效。关注边界值测试N0,N1,K0,K1以及K大于二进制位数的情况。这些边界情况最容易出问题。最后数位DP的熟练离不开练习。理解了二进制这个简单模型后可以尝试蓝桥杯或其他OJ上的十进制数位DP题目例如“不要62”、“windy数”等经典问题逐步加深对状态设计和问题转化的理解。这道“二进制问题”就像一把钥匙帮你打开了数位DP这扇门门后的世界还需要你用自己的代码去探索和征服。