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

1. 从一道国赛真题说起：二进制问题的“暴力”困境

去年带学生备赛蓝桥杯国赛，复盘到2021年这道“二进制问题”时，好几个平时刷题挺猛的同学都卡住了。题目大意是：给定一个正整数N和一个整数K，问在区间[1, N]的所有整数中，其二进制表示里恰好有K个1的数有多少个。比如N=7, K=2，那么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，首先得跳出“遍历数字”的惯性思维。面对N=10^18，它的二进制大约有60位（因为2^60 ≈ 1.15e18）。我们虽然不能枚举10^18个数，但枚举一个60位的二进制串的所有可能状态，在辅以DP优化后，是完全可行的。数位DP做的就是这件事。

2.1 “数位”与“上限”的概念

数位DP通常用于解决在某个上限范围内，满足特定条件的数字个数问题。这里的“数位”可以是十进制位，也可以是二进制位、八进制位等。本题是二进制，所以我们处理的是二进制的每一个bit。

关键约束是“上限N”。我们不能简单地生成所有60位的二进制数，因为那样会包含许多大于N的数。例如N=5 (101b)，我们考虑3位二进制。如果我们生成110b (6)，它就超过了N。因此，在枚举每一位时，我们必须知道当前已经确定的前几位，是否已经“顶到”了N的对应位。这就引入了数位DP中最重要的一个状态：是否处于上限（limit）。

我们来模拟一下，假设N = 5 (二进制 101)，我们从最高位（第2位，下标从0开始）开始枚举：

1. 枚举最高位（bit[2]）：
   • 如果这一位填0，那么无论后面两位怎么填，最终的数字一定小于N（因为0xx最大是011=3，小于101=5）。此时，后续位的枚举就不再受N的限制，可以自由填0或1。
   • 如果这一位填1，那么当前构造的数字的前缀1和N的前缀1完全相同，我们还没有“安全”。此时，后续位的枚举仍然受到N对应位的限制。下一位（bit[1]）是N的0，那么我们最多只能填到0，不能填1（填1就成了11x，最小是110=6 > 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)且limit=false时，就可以直接返回缓存的结果，无需重复计算。这就是数位DP效率的源泉，它将指数级的枚举复杂度，降低到了多项式级别（状态数pos * cnt，每个状态计算常数时间）。

注意：dp数组只能缓存limit=false的状态。因为limit=true的状态与具体的N的剩余位紧密相关，不同的N会导致不同的结果，无法通用。所以，在记忆化时一定要判断：只有!limit时，才去查询和存储dp数组。

2.3 状态转移与递归流程

有了状态定义，转移就清晰了。在dfs(pos, cnt, limit)中：

1. 递归边界：如果pos已经超过最低位（即所有位都处理完了），我们检查cnt是否等于目标K。等于则返回1（找到一种合法数字），否则返回0。
2. 记忆化查询：如果!limit且dp[pos][cnt]已经计算过，直接返回。
3. 计算当前位上限：up = limit ? bits[pos] : 1。bits[pos]是N在pos位的值（0或1）。如果顶着上限，最多只能填到bits[pos]；否则可以填到1。
4. 枚举与递归：枚举当前位i从0到up。
   • 计算新的cnt_next = cnt + (i == 1 ? 1 : 0)。
   • 计算新的limit_next = limit && (i == up)。这个逻辑是关键：只有之前一直顶着上限（limit=true），并且当前位也填到了允许的最大值（i == up），那么对于下一位来说，它才可能继续顶着上限。否则，只要有一位没顶到，后面的位就彻底自由了（limit_next=false）。
5. 累加结果：将dfs(pos+1, cnt_next, limit_next)的结果累加到ans。
6. 记忆化存储：如果!limit，将ans存入dp[pos][cnt]。
7. 返回结果：返回ans。

主函数里，我们先把N转换成二进制数组bits[]，然后调用dfs(0, 0, true)。注意初始limit=true，因为最开始没有任何位被确定，相当于和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; } // 填充bits，bits[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. 从最高位(pos=0)开始DFS，初始已填1的个数cnt=0，初始状态是顶着上限的(limit=true) 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状态，并且当前位填到了最大值(i==up)，下一位才继续受限制 boolean nextLimit = limit && (i == up); // 累加子问题的结果 res += dfs(pos + 1, nextCnt, nextLimit); } // 记忆化存储：只有非限制状态的结果才需要存储 if (!limit) { dp[pos][cnt] = res; } return res; } }

代码关键点解析：

1. 二进制转换与索引：代码中用了两步来获得正序的bits数组，bits[0]是最高位。这样在DFS时，pos从0递增到len-1，逻辑上是从最高位处理到最低位，非常符合直觉。另一种常见写法是得到逆序数组后，DFS时pos从len-1递减到0，本质一样。
2. DP数组初始化：dp数组初始化为-1，而不是0。因为计算结果可能为0（表示该状态无法构造出合法数字）。用-1可以区分“未计算”和“计算结果为0”两种情况。
3. limit的传递逻辑：nextLimit = limit && (i == up)是核心中的核心。它保证了“顶着上限”这个状态的严格传递。一旦某一位填的数小于上限（i < up），那么nextLimit就会变成false，后续所有位都将进入自由状态，其结果就可以被dp数组缓存和复用。
4. 记忆化的条件：if (!limit && dp[pos][cnt] != -1)和if (!limit) { dp[pos][cnt] = res; }。务必注意，只有!limit的状态才具有通用性，才能被记忆化。这是数位DP模板里最容易写错的地方之一。
5. 时间复杂度：状态数大约是len * K，本题中len <= 60,K <= 60，状态数最多3600个。每个状态需要枚举当前位（最多2种选择）。因此计算量非常小，完全满足竞赛要求。

4. 从理解到精通：数位DP的变通与边界处理

掌握了上面这个模板，可以说解决了80%的二进制数位DP问题。但要在赛场上灵活运用，还需要理解它的变通性和一些边界情况。

4.1 处理“0”这个特殊数字

我们的DFS通常是从最高位开始，枚举每一位。但这里有一个隐含问题：我们枚举的数字是包含前导零的。例如N=5(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。因此，当K=0时，我们的答案需要减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”。其模板和二进制完全一致，只有两点不同：

1. 数位进制：枚举每位时，up的上限是9（十进制），而不是1。
2. 状态设计：可能需要更多维度。例如“不含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。
• 与数论结合：求区间内每个数字都是质数的数的个数（如237，2,3,7都是质数）。状态中可能需要记录是否合法，或者在枚举当前位时直接跳过非质数数字。
• 与位运算结合：本题就是最直接的位运算（二进制）应用。更复杂的如求区间内数字的二进制表示中，1的个数是质数的数的个数。只需要在递归边界处，不仅检查cnt是否等于某个值，而是检查cnt是否为质数。

5.3 竞赛中的实战策略

1. 识别题型：看到“区间[L, R]内，满足……条件的数的个数”，且L和R范围巨大（比如10^18），第一时间就要想到数位DP。
2. 设计状态：这是最难也是最关键的一步。问自己：在已知前缀的情况下，要确定后续的填法，最少需要哪些信息？这些信息必须能唯一确定后续的“可能性空间”。通常，pos（位置）和limit是必须的。其他维度根据题目条件添加，如计数类加cnt，相邻关系加pre，模运算加mod等。原则是：在limit=false的情况下，相同的状态必须对应完全相同的后续方案数。
3. 处理前导零：如果题目条件与前导零有关（比如数字不能有前导零，或者像“数字本身”这样的值与零有关），就需要一个isZero状态。在isZero=true时，当前位填0意味着继续是前导零，可能有一些特殊处理。
4. 实现与调试：套用模板，仔细实现dfs函数。特别注意limit的传递和记忆化的条件。用小的N暴力枚举验证结果。
5. 优化：如果状态维度多，可能dp数组会很大。要评估状态数是否在可接受范围内（通常10^6以内是安全的）。必要时进行剪枝，比如当cnt已经超过K时直接返回0。

回到我们开头的蓝桥杯真题，它属于数位DP中最基础、最经典的“数位计数”问题。通过这道题，我们不仅学会了一个模板，更重要的是理解了“按位枚举+记忆化”这一核心思想。掌握了这个思想，你就拥有了一把打开一大类计数问题大门的钥匙。在比赛中，遇到类似的题目，冷静分析，设计出正确的状态，就能将看似恐怖的枚举量，化解为一次高效的深度优先搜索。