数位DP精讲：从二进制计数到通用框架，解决蓝桥杯国赛难题

1. 从一道国赛真题说起二进制与数位DP的碰撞最近在整理蓝桥杯的历年国赛真题第十二届那道“二进制问题”让我印象挺深。这题表面上是问在1到N的整数中有多少个数的二进制表示里恰好有K个1。乍一看这题用暴力枚举好像也能做但仔细一想N的上限是10^18这直接遍历的念头可以趁早打消了。这题明摆着是数位动态规划数位DP的经典应用场景。很多同学一听到“数位DP”就觉得头大感觉是竞赛里的“高端”技巧其实它的核心思想非常朴素就是“按位考虑记忆化搜索”用来解决这类与数字的数位无论是十进制还是二进制性质相关的计数问题是再合适不过的工具。今天我就结合这道国赛真题把二进制场景下的数位DP从思路到代码再到容易踩的坑给大家彻底捋清楚。无论你是正在备赛蓝桥杯还是对算法中的这种精巧思想感兴趣相信这篇都能给你带来可以直接“抄作业”的收获。2. 问题重述与暴力解法的死胡同我们先明确一下题目给定一个非常大的正整数 N1 ≤ N ≤ 10^18和一个非负整数 K0 ≤ K ≤ 60我们需要求出区间 [1, N] 内所有满足“其二进制表示中‘1’的个数恰好为 K”的整数 x 的个数。为什么暴力枚举行不通我们来算笔账。N最大是10^18约等于2^60。也就是说最坏情况下我们需要检查大约1e18个数。即使你的计算机每秒能处理1亿1e8次运算也需要1e10秒这超过300年。显然这条路是走不通的。这迫使我们必须寻找一种与数字大小“无关”而与数字的“位数”相关的算法。数位DP正是为此而生它的时间复杂度通常为 O(位数 * 状态数)在这里就是 O(60 * 60 * 2)完全在可接受范围内。这里就引出了数位DP的一个核心思想我们不直接枚举数字而是枚举构成数字的每一个数位bit的可能取值并在枚举过程中动态维护我们关心的状态在这里就是当前已经出现的‘1’的个数。这就像我们写一个多位数的密码锁我们不是去试每一个可能的密码数字而是从最高位开始一位一位地决定这个数字的构成同时记录下到当前位为止我们已经用了几个“1”。3. 数位DP的核心框架与记忆化搜索数位DP通常采用记忆化搜索DFS Memoization的实现方式因为它写起来思路清晰易于理解。整个框架可以分解为以下几个关键部分3.1 状态定义与DFS函数设计我们设计一个递归函数dfs(pos, count, isLimit)。pos(当前位)表示当前正在处理二进制数字的第几位。通常我们从最高位最左边开始处理向最低位最右边递归。对于N最大为2^60我们考虑60位二进制位实际上可能用不到60位但为了统一我们可以将数字看作一个固定60位的二进制串高位不足补0。count(当前状态)表示从最高位处理到pos位之前已经累计出现了多少个‘1’。这是我们关心的核心状态。isLimit(是否受到限制)这是一个非常关键且容易出错的参数。它表示当前位pos的取值是否受到前缀的约束。如果isLimit true意味着之前所有高位pos之前的取值已经和我们的上界 N 的对应位完全一致。那么当前位pos能取的最大值不能超过 N 在pos位上的值0或1。如果isLimit false意味着之前的高位中至少有一位已经填了一个比 N 对应位小的数比如N的该位是1我们填了0。那么从这一位开始后面的所有位都可以自由地在0和1之间选择不再受 N 的限制。理解这一点是理解整个算法为何高效的关键。3.2 记忆化搜索的“记忆”什么记忆化搜索是为了避免重复计算。我们用一个数组dp[pos][count]来缓存计算结果。但是这里有一个至关重要的细节dp数组只能缓存当isLimit false时的结果为什么因为isLimit true的情况是与当前具体的上界 N 紧密绑定的它表示一条“紧贴着上界”的路径。这条路径在整个搜索过程中很可能是唯一的或者与其他isLimit false的路径不通用缓存它没有意义反而可能出错。而isLimit false的情况代表“已经脱离上界限制”的路径此时后续位的选择是自由的其结果从当前pos和count状态开始能构造出多少满足条件的数是通用的可以被缓存和复用。所以我们的记忆化逻辑是在DFS函数开始时如果isLimit false并且dp[pos][count]已经计算过则直接返回缓存值。否则进行计算并在返回前同样仅在isLimit false时将结果存入dp数组。3.3 递归的流程与决策在每一层递归中即处理第pos位时我们需要决定这一位填0还是填1。确定当前位能取值的上限up如果isLimit为真则up等于 N 在pos位上的值0或1否则up为1二进制位最大就是1。枚举当前位i从 0 到up。计算新的状态next_count count (i 1 ? 1 : 0)。即如果这一位填了1则已使用的‘1’的个数加1。计算新的限制状态next_isLimit isLimit (i up)。这意味着只有当前位也“顶格”取了上限值且之前的状态本来就是受限的传递给下一位的限制状态才继续为真。否则只要当前位没取到上限或者之前已经不受限了那么下一位就自由了。递归调用dfs(pos-1, next_count, next_isLimit)将所有可能的后续路径的结果累加即为当前状态下的方案数。3.4 递归边界与结果返回当pos变为 -1或0取决于你的起始定义时意味着所有位都已经处理完毕。此时我们检查状态count是否等于目标 K。如果相等则找到一种合法数字返回1否则返回0。最终我们调用dfs(start_pos, 0, true)。start_pos是最高有效位的位置初始计数为0并且初始状态是受到限制的isLimit true因为我们一开始构造的数字不能超过N。4. 针对“二进制问题”的代码实现与逐行解析理论说完了我们来看具体代码。这里提供一个清晰的C实现并加上详细注释。#include iostream #include cstring #include vector using namespace std; typedef long long ll; ll N; int K; // dp[pos][count] 记忆化数组pos范围[0, 64] count范围[0, 60] ll dp[65][65]; // 存储数字N的二进制位bits[0]是最低位个位方便循环处理 vectorint bits; // 记忆化搜索函数 // pos: 当前处理到的位索引从最高位向最低位走初始为最高位索引 // cnt: 当前已经使用的‘1’的个数 // limit: 当前是否受到上界N的限制 ll dfs(int pos, int cnt, bool limit) { // 递归边界所有位都处理完了 if (pos 0) { // 如果使用的‘1’的个数恰好等于K则这是一个合法数字 return cnt K ? 1 : 0; } // 记忆化只有在不受限制时结果才是通用的可以缓存 if (!limit dp[pos][cnt] ! -1) { return dp[pos][cnt]; } // 计算当前位能取的最大值 int up limit ? bits[pos] : 1; // 二进制位不受限时最大为1 ll res 0; // 枚举当前位取0或1 for (int i 0; i up; i) { // 计算新的‘1’的计数 int next_cnt cnt (i 1); // 如果新的计数已经超过K后续无论如何填都不可能满足条件剪枝 // 这是一个重要的优化可以提前结束无效分支 if (next_cnt K) { continue; } // 计算传递给下一位的限制状态 // 只有当前位也取到了上限值且之前是受限的下一位才继续受限 bool next_limit limit (i up); // 累加后续所有位的方案数 res dfs(pos - 1, next_cnt, next_limit); } // 只有在不受限时才将结果存入记忆化数组 if (!limit) { dp[pos][cnt] res; } return res; } // 主求解函数计算[1, N]中满足条件的数的个数 ll solve(ll n, int k) { N n; K k; // 初始化记忆化数组为-1表示未计算 memset(dp, -1, sizeof(dp)); bits.clear(); // 将数字N分解为二进制位存入bits // 这里bits[0]存的是最低位方便索引 ll temp N; while (temp 0) { bits.push_back(temp 1); // 取最低位 temp 1; // 右移一位 } // 如果N是0bits为空需要特殊处理。但题目N1所以这里不考虑。 // 注意此时bits的最后一个元素是N的最高有效位。 // 例如 N5 (101)bits [1, 0, 1]索引0是低位1索引2是高位1。 // 从最高位开始搜索。最高位索引是 bits.size() - 1 // 初始计数为0初始状态是受限的limit true return dfs(bits.size() - 1, 0, true); } int main() { ll n; int k; // 题目输入 cin n k; // 调用求解函数 ll ans solve(n, k); cout ans endl; return 0; }代码关键点解析二进制位存储bits向量存储N的二进制表示bits[0]是最低位。这样在递归时pos从最高位索引 (bits.size()-1) 开始递减到0符合我们从高到低思考的习惯。dfs参数pos它表示当前处理的是bits容器中的第pos个元素即从低到高数的第pos位。在递归调用时传递pos-1就是处理下一位更低一位。剪枝优化if (next_cnt K) continue;这行代码非常关键。一旦当前路径累积的‘1’已经超过了K那么无论后面怎么填0总数都会超过K这条路径不可能产生合法结果直接跳过节省了大量不必要的递归。记忆化的条件if (!limit) dp[pos][cnt] res;再次强调只有不受限的状态才能被缓存。5. 从理解到精通数位DP的易错点与实战技巧理解了框架和代码不代表实战中就能一次写对。下面是我在多次做题和教学中总结的几个容易踩坑的地方和对应的技巧。5.1 关于“前导零”的处理问题在我们这道二进制题里前导零即二进制表示中高位的0会影响‘1’的计数吗比如数字5101和数字5看作4位二进制的0101其中‘1’的个数都是2个所以在这个特定问题里前导零不影响结果。因此我们的代码没有特殊处理前导零。陷阱与扩展但是在很多其他数位DP问题中前导零是必须处理的。例如统计数字中“非零数字”的个数、处理数字回文、或者某些数字的数值特性时前导零的存在会干扰状态定义。通常的处理方法是在DFS函数中增加一个状态isLead表示当前位之前是否全是前导零。当isLead为真且当前位填0时isLead继续保持为真并且count状态不更新因为前导零不计入统计。当isLead为真且当前位填了非零数时isLead变为假开始正式计数。记忆化时需要将isLead也作为一个维度通常只缓存isLeadfalse的状态因为前导零状态也是与具体路径相关的。5.2 记忆化数组的维度与初始化维度我们的dp[pos][cnt]是二维的。pos的维度至少要等于最大位数这里取65很安全。cnt的维度至少要等于可能的最大‘1’的个数二进制下就是最大位数所以也取65。如果问题有更多状态比如是否包含某个数字、奇偶性等就需要增加维度。初始化务必在每次求解一个新的问题即新的N和K时重新初始化dp数组为-1或其他未计算标记。因为dp缓存的是!limit状态下的结果这个结果是通用的但只针对相同的数字上限N的二进制长度和相同的K吗仔细看dp[pos][cnt]的含义是在不受原始数字N限制的情况下从第pos位开始当前已有cnt个1后续能组成的所有数字中满足总‘1’的个数为K的方案数。这个结果实际上与具体的N值无关只与剩余位数(pos)和当前计数(cnt)有关。所以如果我们连续求解多个不同N但相同K的问题理论上可以不清空dp数组因为状态是通用的。但为了避免混淆和潜在错误比如K变了最稳妥的做法还是在solve函数内初始化。5.3 递归边界的多样性我们的边界是pos 0。有时也可以定义pos 0时处理最低位然后边界是pos -1。关键是保持一致。在边界处要根据题目要求返回正确的值。本题是计数所以返回1或0。如果是求满足条件的数字之和边界就可能需要返回数字本身或0并在递归过程中拼接数字。5.4 如何调试数位DP数位DP的递归树可能很深直接跟踪比较困难。我的调试技巧是小数据暴力对拍写一个朴素的暴力程序枚举1到一个小范围的M比如1000统计答案。然后用你的数位DP程序去计算solve(M, K)对比结果是否一致。这是最有效、最根本的调试方法。打印递归日志在DFS函数入口打印pos, cnt, limit的值在返回前打印计算结果。观察哪些状态被重复计算了记忆化生效哪些路径被剪枝了。这能帮你理解算法的执行流程。检查记忆化逻辑重点确认!limit的条件判断是否正确。可以尝试去掉记忆化用小数据看结果是否一样速度会慢但可用于验证逻辑正确性。6. 性能分析与算法扩展思考对于本题N最大为10^18二进制位数最多约为60位。我们的状态数是pos(60) *cnt(60) ≈ 3600。每个状态计算时需要枚举0和1两种可能。所以总的时间复杂度大约是 O(60 * 60 * 2) O(7200)忽略常数后就是 O(m^2)其中m是位数。空间复杂度是 O(m^2)。对于现代计算机来说这几乎是一瞬间的事情。扩展思考如果问题变成十进制呢比如求1到N之间各位数字之和为S的数的个数。思路完全一样数位变成十进制0-9。状态count变为当前数字之和。递归枚举时当前位i从0枚举到upup在受限制时为N的当前位数字否则为9。剪枝条件变为next_sum S。记忆化数组dp[pos][sum]。 框架完全通用这体现了数位DP作为一种“方法论”的强大之处。再扩展求满足条件的数字之和而不仅仅是个数。这时状态需要携带更多信息。通常我们让DFS函数返回一个结构体或pair里面包含两个值(count, sum)即从当前状态出发能构成的合法数字的个数以及这些数字的总和。在递归边界如果合法返回(1, 0)个数为1但当前数字和为0因为还没数字。在递归过程中当枚举当前位填i时得到子状态的(sub_count, sub_sum)。那么当前状态通过填i得到的贡献是个数为sub_count而总和需要加上i放在当前位所代表的值即i * (10^pos)或i * (2^pos)乘以sub_count因为i这个值会在sub_count个数字中出现。最后汇总所有i的贡献。记忆化也需要相应地缓存这个pair。7. 总结与个人心得数位DP的本质是一种基于数位的、带状态记忆的深度优先搜索。它通过“逐位构造数字”的方式将指数级的大范围枚举问题转化为关于“位数”的多项式时间问题。其核心难点和精髓在于状态的设计和限制(limit)的处理。在实际写代码时我个人习惯遵循以下步骤确定状态题目问什么什么信息需要在不同数位间传递和决策这些就是状态。本题是“1的个数”所以状态是cnt。设计DFS函数参数至少包含pos,状态,limit。考虑是否需要isLead前导零状态。确定记忆化维度状态有哪些dp数组就开几维。记住只记忆化!limit的状态。明确递归边界及返回值根据问题是求个数、和、最大值等确定边界返回什么。当前位的决策根据limit确定枚举范围进行递归调用并更新状态。剪枝在枚举前或递归前判断当前状态是否已经不可能达到目标如cnt K提前返回提升效率。最后再提一个容易忽略的点题目问的是 [1, N]我们的算法通常处理的是 [0, N]。如果0不符合条件比如本题要求二进制中1的个数为K而0的二进制没有1除非K0否则0不合法那么我们的算法结果就是对的。如果0符合条件而题目要求从1开始只需要在最终结果中减去1如果0合法或者直接计算即可。本题中当K0时0是合法的0个1但区间是[1, N]所以0不应该被计入。我们的算法solve(N, K)计算的是[0, N]中满足条件的数的个数。因此当K0时最终答案应该是solve(N, K) - 1减去0这个数。当K0时0本身就不合法所以solve(N, K)直接就是答案。这是一个边界情况在比赛中需要仔细考虑。