1. 项目概述从一道华为OD机试真题说起最近在帮几个准备华为OD机试的朋友做模拟练习发现“不含101的数”这道题出现的频率相当高而且讨论热度一直不减。这道题本身属于数位动态规划Digit DP的经典入门题型但很多初次接触的朋友尤其是从传统算法题转向机试实战的同学往往会被它“简单描述复杂实现”的特点给唬住。题目要求很简单给定一个区间[L, R]统计在这个区间内所有整数的二进制表示中不包含连续子串“101”的数的个数。比如5的二进制是101它就包含“101”所以不被统计而6的二进制是110它就不包含连续的“101”模式。这题考察的核心远不止是二进制转换和字符串匹配它真正考验的是候选人将问题抽象为状态机模型并利用动态规划高效求解大规模数据范围L和R可能很大比如1 L R 10^9的能力。对于备战OD机试的C、Java、Python或JavaScript开发者来说吃透这道题就等于掌握了数位DP这一重要武器库的钥匙后续遇到类似“不含某个模式”、“满足某种数字限制”的计数问题都能触类旁通。2. 核心思路拆解为什么是数位DP看到“统计区间内满足某性质的数的个数”并且数据范围巨大暴力枚举每个数再检查其二进制显然是不可行的10^9的量级必然超时。这几乎就是数位动态规划的标准应用场景信号。数位DP的精髓在于“按位决策”和“记忆化搜索”它允许我们一次性处理整个数位范围而不是单个数字。2.1 问题转化与状态定义我们首先需要把“不含连续的‘101’”这个条件转化成一个可以在数字的二进制每一位上做决策时进行判断的状态机。让我们从最高位向最低位或反之逐位构造数字。在构造过程中我们需要记住最近两位是什么才能判断当前位填0或1时是否会形成“101”。具体来说我们可以定义三个状态prev2: 上上一位的数字0或1。prev1: 上一位的数字0或1。pos: 当前正在处理第几位从最高位开始向低位处理。那么在决定当前位current填0还是1时非法情况就是(prev2, prev1, current) (1, 0, 1)。只要避开这种情况当前位的选择就是合法的。然而在数位DP的记忆化搜索中我们通常用dp[pos][state][limit]这样的形式。这里的state需要编码足够的信息使得从pos位开始往后随意填数时能知道之前的选择对后续决策的影响。对于“不含101”这个问题state至少需要编码最后两位(prev1, prev2)的信息因为判断“101”需要看连续三位。但更常见的优化是由于我们只关心是否可能以“10”结尾因为如果以“10”结尾下一位就不能填1所以state可以定义为state 0: 之前填的位不以“1”或“10”结尾即最后一位是0且倒数第二位不是1或者刚开始。state 1: 之前填的位最后一位是“1”。state 2: 之前填的位最后两位是“10”。这样状态就从二维(prev2, prev1)压缩成了一维状态数更少效率更高。当state 2时当前位绝对不能填1否则就形成了“101”。2.2 记忆化搜索框架解析数位DP通常采用DFS记忆化的模板。函数dfs(pos, state, limit)表示当前处理到二进制数字的第pos位从0开始或从最高位开始依实现而定。当前的状态为state根据上述定义0, 1, 2。limit是一个布尔值表示当前位是否受到原始数字N对应位的限制。如果limit为真那么当前位能填的最大值就是N在这一位的值0或1如果limit为假那么当前位可以填0或1。函数的返回值是从第pos位开始在给定state和limit条件下能构造出的所有合法数字的个数。搜索过程递归边界如果pos越界所有位都处理完说明成功构造了一个合法的数字返回1。检查记忆化如果limit为假即后续位可以自由选择0或1并且dp[pos][state]已经计算过则直接返回缓存值。limit为真时不能记忆化因为受限情况下的结果不具备通用性。确定当前位可选范围根据limit和数字N的当前位bit确定current可以填0还是1或者两者皆可。枚举当前位的选择i(0 或 1)根据当前的state和选择的i计算出新的状态next_state。判断(state, i)是否构成非法组合即state 2 i 1。如果是跳过。计算新的next_limit如果当前位本来就受限(limit为真)并且i等于上限值bit那么下一位继续受限否则下一位不再受限。递归调用dfs(pos1, next_state, next_limit)将结果累加。如果当前不受限 (!limit)将累加结果存入dp[pos][state]。返回累加结果。最终区间[L, R]的答案就是count(R) - count(L-1)其中count(N)表示[0, N]区间内满足条件的数的个数。注意在实际编码中我们需要将数字N转换为二进制位数组。同时为了处理方便通常会让二进制位数组从最高位索引0开始。state的转移逻辑是核心需要仔细推敲。例如如果state0末尾是0或刚开始当前位填0新状态还是0填1新状态变为1。如果state1末尾是1当前位填0新状态变为2形成“10”填1新状态变为1形成“11”注意“11”不会直接导致非法但末尾变成了1。如果state2末尾是“10”当前位只能填0新状态变为0形成“100”末尾是0填1会导致非法必须被禁止。3. 多语言代码实现与解析理解了上述框架我们就可以用不同语言来实现。不同语言在实现细节上略有差异但核心逻辑一致。下面我将分别用C、Java、Python和JavaScript给出实现并附上关键点解析。3.1 C 实现C实现通常追求效率和简洁。我们会使用一个三维数组dp来记忆化但第三维limit不参与记忆化所以实际是dp[pos][state]。#include iostream #include cstring #include vector using namespace std; using ll long long; ll dp[35][3]; // pos 最大位数state 有3种 vectorint digits; ll dfs(int pos, int state, bool limit) { if (pos digits.size()) { return 1; // 成功构造一个合法数字 } if (!limit dp[pos][state] ! -1) { return dp[pos][state]; } int upper limit ? digits[pos] : 1; ll sum 0; for (int i 0; i upper; i) { if (state 2 i 1) { continue; // 形成101模式非法 } int next_state; if (state 0) { next_state (i 1) ? 1 : 0; } else if (state 1) { next_state (i 0) ? 2 : 1; } else { // state 2 next_state 0; // 只能填0状态变为0 } sum dfs(pos 1, next_state, limit i upper); } if (!limit) { dp[pos][state] sum; } return sum; } ll count(ll num) { if (num 0) return 0; digits.clear(); while (num) { digits.push_back(num 1); num 1; } if (digits.empty()) digits.push_back(0); // 处理num为0的情况 reverse(digits.begin(), digits.end()); // 得到从高位到低位的二进制数组 memset(dp, -1, sizeof(dp)); // 注意从最高位开始初始状态为0表示前面没有数字且最高位受限 return dfs(0, 0, true); } int main() { ll L, R; // 假设输入 L 和 R // cin L R; L 1; R 10; // 示例 ll ans count(R) - count(L - 1); cout ans endl; return 0; }C实现要点dp数组初始化memset(dp, -1, sizeof(dp))用-1表示未计算。二进制转换用while(num)循环和位操作取出每一位再reverse得到高位在前的数组。注意处理num0的特殊情况。递归函数设计dfs参数和返回值使用long long以防结果过大。状态转移逻辑用if-else清晰定义了state在三种情况下根据当前位i如何转移到next_state。这是整个算法的核心务必理解透彻。3.2 Java 实现Java实现与C类似但需要注意使用long类型和递归的栈深度。对于10^9二进制位数不超过30位递归深度安全。import java.util.*; public class Main { private static long[][][] dp; private static ListInteger digits new ArrayList(); private static long dfs(int pos, int state, boolean limit) { if (pos digits.size()) { return 1L; } if (!limit dp[pos][state][0] ! -1) { return dp[pos][state][0]; } int upper limit ? digits.get(pos) : 1; long sum 0L; for (int i 0; i upper; i) { if (state 2 i 1) { continue; } int nextState; if (state 0) { nextState (i 1) ? 1 : 0; } else if (state 1) { nextState (i 0) ? 2 : 1; } else { // state 2 nextState 0; // 只能填0 } sum dfs(pos 1, nextState, limit i upper); } if (!limit) { dp[pos][state][0] sum; } return sum; } private static long count(long num) { if (num 0) return 0L; digits.clear(); while (num 0) { digits.add((int)(num 1L)); num 1; } if (digits.isEmpty()) digits.add(0); Collections.reverse(digits); int len digits.size(); dp new long[len][3][1]; for (int i 0; i len; i) { for (int j 0; j 3; j) { dp[i][j][0] -1L; } } return dfs(0, 0, true); } public static void main(String[] args) { long L 1L, R 10L; // 示例输入 long ans count(R) - count(L - 1); System.out.println(ans); } }Java实现要点dp数组这里为了简化使用了三维dp[pos][state][0]第三维大小为1用来区分limit的情况。也可以使用二维dp配合limit参数不记忆化的通用做法。集合使用用ArrayListInteger存储二进制位注意使用Collections.reverse()进行反转。类型处理所有可能大的整数都用long类型位操作时注意1L。3.3 Python 实现Python的实现得益于其动态类型和装饰器可以写得非常简洁。这里使用lru_cache来实现记忆化代码可读性极高。from functools import lru_cache def count(num: int) - int: if num 0: return 0 # 将数字转换为二进制字符串去掉0b并转换成整数列表高位在前 s bin(num)[2:] digits list(map(int, s)) lru_cache(maxsizeNone) def dfs(pos: int, state: int, limit: bool) - int: if pos len(digits): return 1 upper digits[pos] if limit else 1 total 0 for i in range(upper 1): if state 2 and i 1: continue if state 0: next_state 1 if i 1 else 0 elif state 1: next_state 2 if i 0 else 1 else: # state 2 next_state 0 # 只能填0 total dfs(pos 1, next_state, limit and i upper) return total return dfs(0, 0, True) def main(): L, R 1, 10 # 示例输入 ans count(R) - count(L - 1) print(ans) if __name__ __main__: main()Python实现要点bin()函数直接得到二进制字符串[2:]去掉0b前缀非常方便。lru_cache这是Python实现记忆化搜索的神器无需手动管理dp数组。参数maxsizeNone表示缓存无限制。注意limit参数也会被缓存但由于limit为True的路径是唯一的对应原数num所以不影响正确性但可能会稍微增加缓存复杂度。更严谨的做法可以将limit分离只在not limit时缓存。递归深度Python默认递归深度有限但本题位数少完全足够。简洁性Python代码清晰地展现了状态转移逻辑是理解算法的最佳辅助。3.4 JavaScript 实现JavaScript在浏览器或Node.js环境中运行需要注意递归性能和记忆化实现。我们可以用一个Map或三维数组来模拟记忆化。function count(num) { if (num 0) return 0n; // 使用BigInt处理大数 // 转换为二进制数组高位在前 const binaryStr num.toString(2); const digits binaryStr.split().map(Number); const n digits.length; // dp[pos][state][limit?] limit为0表示false1表示true。实际上只缓存limit为0的情况。 const dp Array.from({ length: n }, () Array.from({ length: 3 }, () [-1n, -1n])); function dfs(pos, state, limit) { if (pos n) { return 1n; } // 只缓存不受限的情况 const limitIndex limit ? 1 : 0; if (!limit dp[pos][state][0] ! -1n) { return dp[pos][state][0]; } const upper limit ? digits[pos] : 1; let sum 0n; for (let i 0; i upper; i) { if (state 2 i 1) { continue; } let nextState; if (state 0) { nextState i 1 ? 1 : 0; } else if (state 1) { nextState i 0 ? 2 : 1; } else { // state 2 nextState 0; // 只能填0 } sum dfs(pos 1, nextState, limit i upper); } if (!limit) { dp[pos][state][0] sum; } return sum; } return dfs(0, 0, true); } function main() { const L 1n, R 10n; // 使用BigInt const ans count(R) - count(L - 1n); console.log(ans.toString()); } main();JavaScript实现要点BigInt由于JavaScript的Number类型在表示大整数时可能不精确使用BigInt数字后加n可以安全地进行大整数运算。toString(2)快速将数字转为二进制字符串。dp数组这里设计为dp[pos][state][2]其中索引0存储limitfalse的结果索引1存储limittrue的结果但通常不缓存limittrue的情况这里为了数组结构统一。判断缓存时只使用dp[pos][state][0]。递归逻辑与其他语言一致注意使用进行严格比较。4. 调试技巧与边界条件处理数位DP的代码逻辑相对复杂容易在边界条件和状态转移上出错。以下是一些实用的调试技巧和必须注意的边界1. 测试小范围数据对比暴力解在实现完数位DP后第一件事就是用暴力算法遍历区间[L,R]对每个数检查二进制是否含“101”对小数据如L1, R1000进行验证。这是确保核心逻辑正确的黄金标准。2. 处理数字0count(N)函数需要正确处理N0的情况。0的二进制表示为“0”它不包含“101”应该被计数。在我们的DFS中当pos len(digits)时返回1正好计入了数字0一条完整的路径。但在count函数中如果num为0bin(0)得到0b0转换后的digits数组是[0]DFS从state0开始第一位只能选0因为limittrue且upper0然后进入下一层pos1此时pos len(digits)返回1。所以结果是正确的。但务必在代码中显式处理num0的情况返回0。3. 状态转移的验证这是最容易出错的地方。可以手动模拟几个简单数字的构造过程构造数字0二进制0状态变化0 - (填0) - 0合法。构造数字5二进制101状态变化0 - (填1) - 1 - (填0) - 2 - (填1)。在最后一步state2时填i1被if (state 2 i 1)拦截因此5不会被计入。正确。构造数字6二进制110状态变化0 -1 -1 -0。(1,1,0)不是“101”合法。4. 记忆化条件的判断记忆化只能用于limitfalse的情况这是数位DP的一个关键点。因为limittrue意味着前面的位都和上限数字N的对应位完全一致后续位的选择仍然受限于N的低位。这种情况下的结果只对当前这个特定的前缀有效不能复用于其他前缀。而limitfalse意味着前面的位已经有至少一位小于N的对应位后续位可以自由选择0或1这个结果对于任何拥有相同pos和state的搜索都是通用的。5. 使用打印调试在DFS函数的关键位置添加打印语句输出pos, state, limit, i, next_state等信息对于理解递归过程和定位错误非常有帮助。尤其是在状态转移逻辑复杂时。5. 性能分析与优化方向对于本题的数据范围R最大10^9二进制位数最多30位上述数位DP解法的时间复杂度是O(位数 * 状态数 * 2)大约是30 * 3 * 2 180次递归调用再乘以一个很小的常数加上记忆化实际计算量极小可以在毫秒级完成。空间复杂度是O(位数 * 状态数)也完全可以忽略不计。潜在的优化点状态压缩我们已经将状态从(prev2, prev1)的4种可能压缩成了3种。这是最优的了吗对于“不含101”这个问题是的。因为只需要知道末尾是否是“10”即可。迭代法DP除了记忆化搜索还可以用迭代的动态规划从低位向高位计算。但记忆化搜索的模板更通用更容易理解和修改以解决其他数位DP问题。预处理DP表如果题目需要多次查询不同的[L, R]区间可以预处理一个通用的DP表然后利用“前缀和相减”的思想快速计算每个count(N)。但本题通常是一次查询预处理收益不大。Python的lru_cache优化如前所述lru_cache会缓存所有参数组合包括limitTrue的情况。可以写一个包装函数将limit参数分离只在内部函数中使用lru_cache这样可以减少不必要的缓存提升一点性能但代码会稍复杂。对于更极端的数据范围比如R最大10^18我们的算法依然有效因为位数只增加到60位左右复杂度仍然是线性的。但如果R大到10^100需要处理大数那么数位DP的框架依然适用但需要将数字用字符串或数组来存储limit的判断逻辑需要相应调整。6. 举一反三数位DP的常见变体掌握了“不含101”这道题你就掌握了数位DP的经典范式。这个范式可以解决一大类问题不含其他模式比如“不含连续的11”、“不含010”等。只需要修改状态定义和转移时的非法判断条件。数字和限制求区间内各位数字之和满足特定条件的数的个数。状态需要记录当前数字和。数字整除问题求区间内能被某个数K整除的数的个数。状态需要记录当前数模K的余数。包含模式求包含至少一个“101”的数的个数。可以用补集思想总数减去不含的或者直接设计状态表示“是否已经包含101”。二进制1的个数求区间内二进制中1的个数为质数的数的个数。状态需要记录当前1的个数。通用解题步骤确定状态分析限制条件确定在逐位构造时需要记录哪些信息前几位是什么、数字和、余数、是否已经满足某个条件等。设计DFS函数dfs(pos, state, limit, lead)。lead表示是否有前导零对于十进制问题很重要二进制中前导零通常不影响但有时也需要。确定转移根据当前状态和当前位的选择计算出下一个状态。确定边界当所有位处理完时根据最终状态判断是否是一个合法数字返回1或0。记忆化在!limit !lead通常的条件下对结果进行缓存。计算答案ans count(R) - count(L-1)。这道“不含101的数”就像数位DP领域的“Hello World”它结构清晰状态定义典型是理解更复杂变体的绝佳起点。在华为OD或其他公司的机试中一旦识别出这是数位DP问题套用这个模板仔细推导状态转移就能稳稳拿下。