数位DP精讲：从二进制计数问题到蓝桥杯国赛真题实战

1. 从一道国赛真题说起二进制问题的“暴力”困境去年带学生备赛蓝桥杯国赛复盘到2021年这道“二进制问题”时好几个平时刷题挺猛的同学都卡住了。题目大意是给定一个正整数N和一个整数K问在区间[1, N]的所有整数中其二进制表示里恰好有K个1的数有多少个。比如N7, K2那么1到7的二进制分别是1(001),2(010),3(011),4(100),5(101),6(110),7(111)其中二进制包含2个1的数有3(011),5(101),6(110)所以答案是3。乍一看这题太简单了不就是遍历1到N每个数转二进制数一下1的个数吗一个for循环加一个Integer.bitCount()就搞定了。确实如果N只有几千、几万这么写完全没问题运行时间可以忽略不计。但蓝桥杯国赛的题目数据范围往往是个“陷阱”。这道题里N的上限是10^18。这意味着什么意味着你不可能用循环去遍历。10^18次循环即使用世界上最快的超级计算机算到比赛结束也算不完。这就是典型的“数太大不能枚举”的场景也是动态规划中“数位DP”这个专门武器大显身手的地方。很多同学初次接触数位DP会觉得它很“玄学”状态设计抽象转移方程复杂。其实它的核心思想非常直观我们不直接枚举数字而是枚举构成数字的每一位。对于二进制问题我们就是一位一位地决定这个数字的二进制形式。在这个过程中我们利用动态规划来“记忆”和“复用”中间结果从而避免了对整个巨大区间的暴力枚举。理解了这个思想再去看那些看似复杂的代码就会清晰很多。接下来我们就以这道国赛题为引子彻底拆解数位DP解决二进制计数问题的完整思路、实现细节以及那些容易让人栽跟头的坑。2. 数位DP的核心化“枚举数”为“枚举位”要理解数位DP首先得跳出“遍历数字”的惯性思维。面对N10^18它的二进制大约有60位因为2^60 ≈ 1.15e18。我们虽然不能枚举10^18个数但枚举一个60位的二进制串的所有可能状态在辅以DP优化后是完全可行的。数位DP做的就是这件事。2.1 “数位”与“上限”的概念数位DP通常用于解决在某个上限范围内满足特定条件的数字个数问题。这里的“数位”可以是十进制位也可以是二进制位、八进制位等。本题是二进制所以我们处理的是二进制的每一个bit。关键约束是“上限N”。我们不能简单地生成所有60位的二进制数因为那样会包含许多大于N的数。例如N5 (101b)我们考虑3位二进制。如果我们生成110b (6)它就超过了N。因此在枚举每一位时我们必须知道当前已经确定的前几位是否已经“顶到”了N的对应位。这就引入了数位DP中最重要的一个状态是否处于上限limit。我们来模拟一下假设N 5 (二进制 101)我们从最高位第2位下标从0开始开始枚举枚举最高位bit[2]如果这一位填0那么无论后面两位怎么填最终的数字一定小于N因为0xx最大是0113小于1015。此时后续位的枚举就不再受N的限制可以自由填0或1。如果这一位填1那么当前构造的数字的前缀1和N的前缀1完全相同我们还没有“安全”。此时后续位的枚举仍然受到N对应位的限制。下一位bit[1]是N的0那么我们最多只能填到0不能填1填1就成了11x最小是1106 5。这个“是否受到原始数字N限制”的状态就是limit。它为true时当前位最多只能填到N的对应位为false时当前位可以填0或1在二进制下。2.2 状态设计与记忆化搜索知道了要枚举位也知道了limit约束我们如何用DP来加速核心是记忆化搜索Memoization。我们定义DFS函数dfs(pos, cnt, limit)。pos: 当前正在处理第几位从最高位向最低位处理。cnt: 从最高位到pos-1位我们已经填了多少个1。limit: 布尔值表示之前已确定的位是否和N的对应位完全一致即是否“顶着上限”。这个函数的返回值是在pos位之后包含pos位的所有位能够构造出最终满足条件整个二进制串中1的个数等于K的数字的个数。那么记忆化搜索的“记忆”体现在哪里我们注意到当limit false时后续位的填充是完全自由的不受N的约束。此时dfs(pos, cnt, false)的结果只与pos和cnt有关与具体的N无关因为对于所有“未顶着上限”的状态后续位的可选范围都是0和1是固定的。因此我们可以用一个数组dp[pos][cnt]来缓存dfs(pos, cnt, false)的结果。当再次遇到相同的(pos, cnt)且limitfalse时就可以直接返回缓存的结果无需重复计算。这就是数位DP效率的源泉它将指数级的枚举复杂度降低到了多项式级别状态数pos * cnt每个状态计算常数时间。注意dp数组只能缓存limitfalse的状态。因为limittrue的状态与具体的N的剩余位紧密相关不同的N会导致不同的结果无法通用。所以在记忆化时一定要判断只有!limit时才去查询和存储dp数组。2.3 状态转移与递归流程有了状态定义转移就清晰了。在dfs(pos, cnt, limit)中递归边界如果pos已经超过最低位即所有位都处理完了我们检查cnt是否等于目标K。等于则返回1找到一种合法数字否则返回0。记忆化查询如果!limit且dp[pos][cnt]已经计算过直接返回。计算当前位上限up limit ? bits[pos] : 1。bits[pos]是N在pos位的值0或1。如果顶着上限最多只能填到bits[pos]否则可以填到1。枚举与递归枚举当前位i从0到up。计算新的cnt_next cnt (i 1 ? 1 : 0)。计算新的limit_next limit (i up)。这个逻辑是关键只有之前一直顶着上限limittrue并且当前位也填到了允许的最大值i up那么对于下一位来说它才可能继续顶着上限。否则只要有一位没顶到后面的位就彻底自由了limit_nextfalse。累加结果将dfs(pos1, cnt_next, limit_next)的结果累加到ans。记忆化存储如果!limit将ans存入dp[pos][cnt]。返回结果返回ans。主函数里我们先把N转换成二进制数组bits[]然后调用dfs(0, 0, true)。注意初始limittrue因为最开始没有任何位被确定相当于和N的前0位“完全一致”所以处于上限状态。3. 蓝桥杯2021国赛真题代码实现与逐行解析理论说完了我们来看这道“二进制问题”的具体代码实现。这里以Java为例因为蓝桥杯主要使用Java语言。我会在关键代码处加上详细注释。import java.util.Arrays; import java.util.Scanner; public class BinaryProblem { static long N; static int K; static int[] bits new int[65]; // 存储N的二进制位65位足够容纳10^18 (2^60) static long[][] dp new long[65][65]; // dp[pos][cnt] 记忆化数组 static int len; // N的二进制有效长度 public static void main(String[] args) { Scanner sc new Scanner(System.in); N sc.nextLong(); K sc.nextInt(); sc.close(); // 1. 将N转化为二进制数组bits[0]是最高位 len 0; long temp N; while (temp 0) { bits[len] (int)(temp 1); // 获取最低位 temp 1; // 右移一位 } // 注意上面的循环结束后bits里是逆序的低位在前。 // 为了方便从高位开始DFS我们通常不反转它而是在DFS时从 len-1 开始作为最高位。 // 但更常见的写法是先得到逆序数组然后DFS时从下标 len-1 向 0 递归。 // 这里我们采用另一种清晰的做法先得到正序数组高位在低索引。 // 重新初始化获取正序二进制位 len 0; temp N; // 先计算长度 while (temp 0) { len; temp 1; } // 填充bitsbits[0]为最高位 temp N; for (int i len - 1; i 0; i--) { bits[i] (int)(temp 1); temp 1; } // 2. 初始化DP数组为-1表示未计算 for (int i 0; i dp.length; i) { Arrays.fill(dp[i], -1); } // 3. 从最高位(pos0)开始DFS初始已填1的个数cnt0初始状态是顶着上限的(limittrue) long ans dfs(0, 0, true); System.out.println(ans); } /** * 记忆化搜索函数 * param pos 当前处理到的二进制位下标0为最高位 * param cnt 从最高位到pos-1位已经填了多少个1 * param limit 之前已确定的位是否完全等于N的上限 * return 返回在pos位之后能构造出满足条件总1的个数为K的数字个数 */ static long dfs(int pos, int cnt, boolean limit) { // 递归边界所有位都处理完了 if (pos len) { // 检查整个数字中1的个数是否恰好为K return cnt K ? 1 : 0; } // 记忆化只有在非限制状态下(!limit)的结果才可以被复用 if (!limit dp[pos][cnt] ! -1) { return dp[pos][cnt]; } long res 0; // 计算当前位可以填的最大值 int up limit ? bits[pos] : 1; // 枚举当前位填0或1但不能超过up for (int i 0; i up; i) { // 计算如果当前位填i新的1的个数 int nextCnt cnt (i 1 ? 1 : 0); // 计算新的limit状态 // 只有之前是limit状态并且当前位填到了最大值(iup)下一位才继续受限制 boolean nextLimit limit (i up); // 累加子问题的结果 res dfs(pos 1, nextCnt, nextLimit); } // 记忆化存储只有非限制状态的结果才需要存储 if (!limit) { dp[pos][cnt] res; } return res; } }代码关键点解析二进制转换与索引代码中用了两步来获得正序的bits数组bits[0]是最高位。这样在DFS时pos从0递增到len-1逻辑上是从最高位处理到最低位非常符合直觉。另一种常见写法是得到逆序数组后DFS时pos从len-1递减到0本质一样。DP数组初始化dp数组初始化为-1而不是0。因为计算结果可能为0表示该状态无法构造出合法数字。用-1可以区分“未计算”和“计算结果为0”两种情况。limit的传递逻辑nextLimit limit (i up)是核心中的核心。它保证了“顶着上限”这个状态的严格传递。一旦某一位填的数小于上限i up那么nextLimit就会变成false后续所有位都将进入自由状态其结果就可以被dp数组缓存和复用。记忆化的条件if (!limit dp[pos][cnt] ! -1)和if (!limit) { dp[pos][cnt] res; }。务必注意只有!limit的状态才具有通用性才能被记忆化。这是数位DP模板里最容易写错的地方之一。时间复杂度状态数大约是len * K本题中len 60,K 60状态数最多3600个。每个状态需要枚举当前位最多2种选择。因此计算量非常小完全满足竞赛要求。4. 从理解到精通数位DP的变通与边界处理掌握了上面这个模板可以说解决了80%的二进制数位DP问题。但要在赛场上灵活运用还需要理解它的变通性和一些边界情况。4.1 处理“0”这个特殊数字我们的DFS通常是从最高位开始枚举每一位。但这里有一个隐含问题我们枚举的数字是包含前导零的。例如N5(101b)在枚举3位二进制时010b(2)和001b(1)都是合法的中间状态。这没有问题因为前导零不影响二进制中1的个数。但是题目问的是区间[1, N]。我们的DFS逻辑实际上计算了从0到N的所有数。因为当所有位都填0时对应的数字就是0。所以如果题目要求[1, N]我们的算法结果直接就是答案。如果题目要求[0, N]结果也是对的。如果题目要求[L, R]区间通常的做法是计算[0, R]的满足条件的数量减去[0, L-1]的数量。在本题中0的二进制表示中1的个数为0。如果K恰好等于0那么我们的DFS会把数字0也算进去。但题目区间是[1, N]不包含0。因此当K0时我们的答案需要减1。这是一个非常重要的边界处理让我们修正一下主函数long ans dfs(0, 0, true); if (K 0) { // 减去数字0的情况 ans--; } System.out.println(ans);踩坑心得数位DP中一定要明确DFS的起点和终点代表的数字范围。处理[0, N]是最自然的处理其他区间需要做加减法。对于计数“1”的个数这类问题要特别小心0这个数字是否被包含以及它是否满足条件。4.2 状态设计的扩展从“恰好K个1”到“至少K个1”原题是“恰好K个1”。如果问题变成“至少K个1”或者“不超过K个1”呢我们不需要大幅修改算法只需要调整递归边界和状态定义。至少K个1在递归边界(pos len)判断cnt K。但是这样记忆化会有点问题因为dp[pos][cnt]中的cnt可能超过K但超过K的状态其实都是等价的都满足“至少K个1”。我们可以将状态定义为dfs(pos, cnt, limit)其中cnt记录已填1的个数但在记忆化和返回时如果cnt K我们可以将其视为同一个状态比如在记忆化时将cnt截断为K。更简单的方法是在递归过程中一旦cnt K我们可以认为后续无论怎么填都满足条件此时可以直接用数学公式计算后续自由位的组合数从而提前返回大幅加速。不超过K个1同理递归边界判断cnt K。也可以在cnt K时直接返回0剪枝。这些变体考察的是对DP状态意义的理解和灵活剪枝的能力。4.3 记忆化数组的维度与初始化本例中状态是(pos, cnt)所以dp是二维的。在某些更复杂的数位DP问题中状态可能需要更多维度比如pre上一位填的数字用于处理相邻位限制问题如“不含连续1”。status一个压缩的状态表示前面位的某种特征如是否已经包含某个子串、模某个数的余数等。zero一个布尔标志表示当前构造的数字是否还是前导零状态这在处理数字本身的值或者需要排除前导零影响时非常有用例如计算数字和。dp数组的维度要根据所有在非限制状态下影响后续结果的变量来决定。初始化值通常设为-1代表未计算。4.4 调试技巧打印递归树数位DP抽象调试起来不太直观。一个非常有效的调试方法是打印递归树。在dfs函数入口打印当前的pos,cnt,limit,up等信息在返回前打印返回值。通过观察递归调用的层次和结果可以清晰地看到算法是如何遍历所有状态的以及记忆化是如何生效的。这对于理解算法过程和定位错误尤其是limit逻辑错误有奇效。5. 举一反三数位DP的经典题型与实战策略数位DP绝不仅限于二进制计数。它是一套解决“数字区间内满足某性质计数”的通用方法论。理解其精髓后可以解决一大类问题。5.1 十进制下的数位DP这是更常见的场景。例如求[L, R]区间内有多少个数满足“各位数字之和是S”或者“不含数字4和62”。其模板和二进制完全一致只有两点不同数位进制枚举每位时up的上限是9十进制而不是1。状态设计可能需要更多维度。例如“不含62”就需要pre状态来记录上一位是不是6。例题变形求[1, N]中十进制表示下各位数字之和为K的数的个数。// 状态dfs(pos, sum, limit) // sum: 当前已确定的各位数字之和 // 递归边界pos到头判断 sum K // 当前位枚举范围0 到 up (up limit ? digits[pos] : 9)你看框架一模一样只是把“二进制位”换成了“十进制位”把“计数1”换成了“累加数字”。5.2 结合其他约束条件数位DP可以很容易地结合其他算法或数学知识。与模运算结合求区间内能被M整除的数的个数。状态中需要增加一个维度mod记录当前数字对M取模的结果。在递归边界判断mod 0。与数论结合求区间内每个数字都是质数的数的个数如2372,3,7都是质数。状态中可能需要记录是否合法或者在枚举当前位时直接跳过非质数数字。与位运算结合本题就是最直接的位运算二进制应用。更复杂的如求区间内数字的二进制表示中1的个数是质数的数的个数。只需要在递归边界处不仅检查cnt是否等于某个值而是检查cnt是否为质数。5.3 竞赛中的实战策略识别题型看到“区间[L, R]内满足……条件的数的个数”且L和R范围巨大比如10^18第一时间就要想到数位DP。设计状态这是最难也是最关键的一步。问自己在已知前缀的情况下要确定后续的填法最少需要哪些信息这些信息必须能唯一确定后续的“可能性空间”。通常pos位置和limit是必须的。其他维度根据题目条件添加如计数类加cnt相邻关系加pre模运算加mod等。原则是在limitfalse的情况下相同的状态必须对应完全相同的后续方案数。处理前导零如果题目条件与前导零有关比如数字不能有前导零或者像“数字本身”这样的值与零有关就需要一个isZero状态。在isZerotrue时当前位填0意味着继续是前导零可能有一些特殊处理。实现与调试套用模板仔细实现dfs函数。特别注意limit的传递和记忆化的条件。用小的N暴力枚举验证结果。优化如果状态维度多可能dp数组会很大。要评估状态数是否在可接受范围内通常10^6以内是安全的。必要时进行剪枝比如当cnt已经超过K时直接返回0。回到我们开头的蓝桥杯真题它属于数位DP中最基础、最经典的“数位计数”问题。通过这道题我们不仅学会了一个模板更重要的是理解了“按位枚举记忆化”这一核心思想。掌握了这个思想你就拥有了一把打开一大类计数问题大门的钥匙。在比赛中遇到类似的题目冷静分析设计出正确的状态就能将看似恐怖的枚举量化解为一次高效的深度优先搜索。