1. 项目概述从一道蓝桥杯国赛题看数位DP的实战拆解最近在复盘历年蓝桥杯国赛真题时又遇到了那道经典的“二进制问题”。这道题可以说是数位动态规划Digit DP的绝佳练兵场它把看似简单的二进制计数包装成了一个需要深度思考状态定义的难题。很多朋友初次接触时会觉得思路很绕不就是数二进制数吗但题目往往要求你在一个巨大的区间内比如[1, 10^18]统计满足特定二进制位约束条件的数字个数。暴力枚举连边都摸不着。这正是数位DP大显身手的地方。数位DP的精髓在于“按位决策”和“状态记忆”。它教会我们如何把一个大问题分解成对数字每一位的、有记忆的、递推式的求解过程。无论是记忆化搜索DFS with Memoization还是纯递推Iterative DP其核心都是设计一个能够完整描述当前决策进度的“状态”。这道二进制问题完美地展示了如何从题目描述中抽象出关键状态以及两种实现范式各自的思维路径和代码风格。理解它你就能触类旁通解决一大类“数字区间内满足某条件的数有多少个”的问题。2. 核心思路解析为什么是数位DP以及状态如何设计拿到“二进制问题”我们首先要破题。题目通常是这样给定一个区间[L, R]求区间内所有数字的二进制表示中满足“任意两个相邻的‘1’之间至少间隔 K 个‘0’”这一条件的数字个数。K是一个给定的正整数。2.1 暴力枚举为何不可行最直接的想法是遍历L到R的每个数检查其二进制形式。但L和R的范围往往极大例如1 L R 2^60这使得线性遍历在时间上完全不可能。我们必须寻找与数字大小其值无关而与数字的长度和位模式相关的计算方法。2.2 数位DP的切入点转化为前缀和相减数位DP的经典技巧是我们不直接计算区间[L, R]的答案而是计算[0, N]的答案记为f(N)。那么区间[L, R]的答案就是f(R) - f(L-1)。这样我们就把问题规约到了“求从0到N之间满足条件的数字个数”。接下来的所有思考都围绕如何高效计算f(N)展开。2.3 状态设计记忆化搜索的核心计算f(N)时我们采用深度优先搜索DFS的方式从二进制的高位向低位逐位确定数字。在这个过程中我们需要用一些参数来定义“当前搜索到了哪一步”这些参数就是状态。一个设计良好的状态必须包含所有影响后续决策的、已做出的选择信息。对于本题影响后续决策的关键因素有当前处理到的数位pos我们正在决定第pos位从高位向低位填0还是1。前一位或前K位是否填了‘1’pre为了满足“相邻1之间至少隔K个0”的条件我们需要知道最近一个被填为‘1’的位距离当前位置有多远。一个巧妙的做法是我们记录“上一个‘1’出现在距离当前位置多少位之前”。如果这个距离小于等于K那么当前位就不能填‘1’如果大于K或者之前还没填过‘1’那么当前位可以填‘1’。更具体地我们可以定义pre表示“上一个‘1’出现在pre位之前”。初始化时我们可以设pre K1或一个大于K的值表示“虚拟”的前一个‘1’在足够远的地方使得第一位可以自由选择填1。在搜索过程中如果当前位填‘0’则pre pre 1距离增加。如果当前位填‘1’则需要先判断pre K是否成立。若成立则可以填并将pre重置为1因为当前位成了新的‘1’对于下一位来说这个‘1’就在前1位若不成立则不能填‘1’。是否已经小于上限limit这是数位DP处理上限N的关键。limit是一个布尔值表示当前位之前的所有位是否都和N的对应位完全相同。如果limit为true那么当前位能填的最大值受到N在该位上值的限制即N的二进制串bits[pos]。例如N5(101)当我们固定了第一位为‘1’与N相同那么第二位就处于limit状态它最大只能填N的第二位‘0’不能填‘1’。如果limit为false则说明高位已经有某一位小于N的对应位了那么当前位可以自由填0或1在本题二进制下就是0或1不再受N的限制。这个参数保证了我们枚举的所有数字都在[0, N]范围内。是否有前导零lead处理数字时高位的‘0’可能只是占位符不代表真正的数值位。例如数字5的二进制是‘101’但如果我们用8位表示是‘00000101’。高位的‘0’就是前导零。在数位DP中前导零通常需要特殊处理因为它可能影响状态比如在统计‘1’的个数时前导零的‘0’不应被计入。在本问题中前导零会影响pre的计算。如果当前位是前导零即它本身是‘0’且它之前的所有高位也都是‘0’那么这个‘0’不应该被视为一个有效的、用于间隔‘1’的‘0’。因此在lead为真时我们填‘0’后pre不应该简单地1而可能要保持一个初始状态如K1。综上所述一个典型的状态可以定义为dfs(pos, pre, limit, lead)它返回在当前位置pos上一个‘1’出现在pre位之前是否处于上限限制limit状态是否处于前导零lead状态下能构造出的所有合法数字的个数。2.4 记忆化搜索的实现框架有了状态定义我们就可以用记忆化搜索来实现。核心是如果当前状态(pos, pre, limit, lead)之前已经计算过并且当时没有受到上限限制即limitfalse那么我们就可以直接返回缓存的结果。因为在不受到N的特定限制时从某个状态往后能构造的数字个数是确定的可以重复利用。// 假设 N 的二进制位已存入数组 bits[]长度为 len // dp[pos][pre] 用于记忆化前提是 limitfalse 且 leadfalse long long dfs(int pos, int pre, bool limit, bool lead) { // 递归边界所有位都处理完毕 if (pos len) { // 通常一个有效的数字需要被计数即使全是0数字0也是合法的 // 但有时需要排除全0的情况具体看题目要求。本题一般包含数字0。 return 1; // 找到一种合法填法 } // 记忆化只有在无限制且无前导零时结果才是通用的、可复用的 if (!limit !lead dp[pos][pre] ! -1) { return dp[pos][pre]; } long long res 0; // 计算当前位能填的上限 int up limit ? bits[pos] : 1; // 二进制所以上限是1 // 遍历当前位可能的取值 for (int i 0; i up; i) { // 根据当前位填的值计算新的状态参数 int next_pre; bool next_lead; if (lead i 0) { // 仍然是前导零状态 next_lead true; next_pre pre; // 或者保持为初始值 K1前导零不更新pre } else { next_lead false; if (i 0) { // 填0且不是前导零有效0间隔距离1 next_pre min(pre 1, K 1); // 距离超过K1后就没有更多限制了可以截断 } else { // i 1 // 填1需要检查是否满足间隔条件 if (pre K) { // 上一个1在至少K1位之前可以填1 next_pre 1; // 新的‘1’出现对于下一位距离是1 } else { continue; // 不满足条件跳过这种填法 } } } // 递归处理下一位limit参数更新为当前位是否达到上限且之前也都在上限 bool next_limit limit (i up); res dfs(pos 1, next_pre, next_limit, next_lead); } // 记录记忆化结果 if (!limit !lead) { dp[pos][pre] res; } return res; }注意pre的取值范围是[1, K1]。当距离超过K1时其限制效果和K1是一样的因为只要距离大于K就可以填1所以我们可以把大于K1的值都视为K1以压缩状态空间。这也是上面代码中使用min(pre1, K1)的原因。3. 递推迭代解法详解另一种思维视角记忆化搜索是“自上而下”的带备忘录的递归更符合人的直觉。而递推迭代解法则是一种“自下而上”的DP它需要更严谨地定义DP数组的含义和转移方程。对于数位DP递推通常有两种实现方式一种是基于“数字位长度”的预处理DP另一种是结合了“上限处理”的经典数位DP递推。这里我们讨论更接近记忆化搜索思维、但用循环实现的递推方法。3.1 递推状态定义我们定义dp[pos][pre][smt]其中pos: 当前处理到的位数从0到len。pre: 同上表示上一个‘1’出现在多少位之前取值范围[0, K1]这里用0表示尚未出现过‘1’或处于特殊初始状态可与记忆化搜索的K1初始值对应。smt: (smaller) 一个标志位0表示当前前缀与N的前缀完全相同即处于limit状态1表示当前前缀已经小于N的前缀即已脱离limit状态。这个定义直接对应了记忆化搜索中limit参数为false时的通用状态。smt1就等价于limitfalse。3.2 递推的初始化与转移递推从最高位开始向低位推进。我们需要小心处理前导零。一种常见的做法是先单独处理第一位因为它的状态比较特殊。初始化处理第0位最高位。我们可以填0作为前导零这会转移到状态(pos1, pre0, smt0)如果N的最高位是0那么填0后前缀依然等于N的前缀如果N的最高位是1填0后前缀就小于N了所以smt需要根据情况判断这里简化了实际需要分类讨论。更稳妥的方法是在循环中统一处理。我们可以填1如果不超过N的最高位检查pre初始可设为K1或一个代表“无限制”的值是否允许填1。允许则转移到(pos1, pre1, smt(i bits[0])?1:0)。实际上更清晰的递推写法是直接使用双层循环枚举状态并基于当前状态(pos, pre, smt)去更新pos1的状态。我们初始化dp[0][K1][0] 1表示在开始之前第0位之前处于“无限制”且前缀严格等于N因为还没开始填的状态有一种方案。状态转移 对于每一个状态(pos, pre, smt)我们枚举当前位pos要填的数字cur0或1。cur能取的最大值由smt和N的第pos位bit决定如果smt 1说明前缀已小当前位可以填0或1。如果smt 0说明前缀相等那么cur不能超过bit。根据cur的值和旧的pre计算新的next_pre逻辑同记忆化搜索。计算新的next_smt如果smt 1那么next_smt始终为1一旦小于永远小于。如果smt 0那么next_smt (cur bit) ? 1 : 0。状态转移方程dp[pos1][next_pre][next_smt] dp[pos][pre][smt]最终答案 所有位处理完毕后即pos lendp[len][pre][smt]就代表了以某种pre状态结束、且与N的大小关系为smt的合法数字数量。我们需要的是所有pre取值下smt为0或1的总和即所有不超过N的数字。但注意smt0代表这个数字恰好等于N我们需要确认N本身是否合法。通常我们计算f(N)时最终答案是sum(dp[len][pre][0]) sum(dp[len][pre][1])或者更简单地在递推过程中smt0和smt1的状态都代表了不超过N的数字最后对dp[len][...][...]求和即可。3.3 递推与记忆化搜索的对比思维难度记忆化搜索更直观它模拟了人脑“尝试填充”的过程状态转移隐藏在递归调用中。递推需要更显式地定义状态和转移方程思维更抽象。代码复杂度记忆化搜索的代码通常更简短逻辑集中在递归函数里。递推的代码可能需要更多的循环和边界条件处理。性能两者时间复杂度在同一量级。记忆化搜索因为有递归开销常数可能略大但在题目限制下通常无关紧要。递推有时可以更好地优化空间例如滚动数组。适用性记忆化搜索几乎可以解决所有数位DP问题是“万能”方法。某些特殊形式的数位DP如只统计特定长度、无上限限制的用递推预处理可能更高效。对于初学者我强烈建议从记忆化搜索入手。它更容易理解和调试是掌握数位DP思想的捷径。当你对状态转移烂熟于心后再去看递推解法会有更深刻的理解。4. 实战演练以一道例题完整实现假设题目为求区间[L, R]内二进制表示中任意两个‘1’不相邻即 K1的数字个数。我们以L1, R10为例进行演算。首先10的二进制是1010。我们计算f(10)。记忆化搜索步骤将10转化为二进制位数组bits [1, 0, 1, 0](高位在前)len4K1。调用dfs(0, 2, true, true)。初始pre2(K1)表示虚拟的前一个‘1’在足够远的地方。递归过程简述pos0: limittrue, leadtrue。只能填0或1因为bits[0]1。填0 (i0): next_leadtrue, next_pre2 (保持)next_limitfalse (因为01)。递归。进入一个以0开头的前导零分支最终会统计所有小于1000(8) 的合法数。填1 (i1): leadfalse, 检查 pre21 成立next_pre1, next_limittrue (因为11)。递归。pos1: 状态来自填1的分支 (pre1, limittrue, leadfalse)。bits[1]0。只能填0或1但up0limittrue所以只能填0。填0: next_pre min(11, 2)2, next_limittrue (00)。递归。pos2: 状态 (pre2, limittrue, leadfalse)。bits[2]1。up1。填0: next_pre2, next_limitfalse (01)。递归。填1: 检查 pre21 成立next_pre1, next_limittrue (11)。递归。... 以此类推直到 pos4返回1。将所有合法路径的返回值相加得到f(10)。同理计算f(0)注意区间是[L,R]我们计算f(R)-f(L-1)所以需要f(0)。f(0)通常就是数字0本身是否合法。根据题意数字0二进制0一般视为合法没有两个‘1’的问题。最终答案 f(10) - f(0)。我们可以手动验证[0, 10]的合法数字二进制不含相邻1有0(0), 1(1), 2(10), 4(100), 5(101), 8(1000), 9(1001), 10(1010)。共8个。所以[1,10]的答案应为7个排除0。通过程序计算应得到相同结果。代码实现要点记忆化搜索#include bits/stdc.h using namespace std; using ll long long; ll L, R, K; int bits[70]; ll dp[70][70]; // dp[pos][pre] pre范围[0, K1] ll dfs(int pos, int pre, bool limit, bool lead) { if (pos -1) { // 所有位处理完 return 1; // 找到一种合法方案计数1 } if (!limit !lead dp[pos][pre] ! -1) { return dp[pos][pre]; } int up limit ? bits[pos] : 1; ll res 0; for (int i 0; i up; i) { if (lead i 0) { // 仍然是前导零 res dfs(pos - 1, K1, limit i up, true); } else { if (i 0) { // 填0 int next_pre min(pre 1, (int)K 1); res dfs(pos - 1, next_pre, limit i up, false); } else { // i 1 if (pre K) { // 可以填1 res dfs(pos - 1, 1, limit i up, false); } // 否则不能填1跳过 } } } if (!limit !lead) { dp[pos][pre] res; } return res; } ll solve(ll num) { if (num 0) return 0; int len 0; while (num) { bits[len] num 1; // 低位在前方便递归从高位开始pos从len-1到0 num 1; } // 如果num为0bits为空需要特殊处理直接返回1数字0 if (len 0) return 1; memset(dp, -1, sizeof(dp)); // 从最高位(len-1)开始初始preK1limittrueleadtrue return dfs(len - 1, K1, true, true); } int main() { K 1; // 假设K1即不允许相邻的1 L 1, R 10; cout solve(R) - solve(L - 1) endl; // 期望输出 7 return 0; }实操心得在写记忆化搜索时pos的处理方向从高位到低位还是从低位到高位是个人习惯。上述代码采用了低位存储在数组前的格式递归从高位len-1向低位0进行。关键是保持bits数组和递归方向一致。另外递归边界pos -1表示所有位处理完毕。初始化dp数组为-1用于记忆化。5. 常见陷阱与调试技巧数位DP思路清晰但实现时细节魔鬼。下面是一些我踩过的坑和调试方法。5.1 状态设计不完整或错误遗漏前导零lead处理这是最常见的错误。在前导零状态下填‘0’不应该影响pre间隔计数。如果不处理会导致多算或少算。例如数字0...010高位的0是前导零它们不应该被认为在两个‘1’之间提供了间隔。pre状态含义不清或范围过大pre表示距离但距离可能无限增长。必须意识到当距离大于K之后再增加距离对决策没有影响因为已经满足可以填‘1’的条件。因此通常将pre的上限设为K1并截断可以大幅减少状态空间。例如K2pre3和pre100对于后续决策是一样的都可以填‘1’。limit标志理解错误limit为真代表之前所有位都和上限N的对应位相等而不仅仅是当前位受限制。因此更新next_limit时是limit (i up)。如果之前已经有一位小于N了limitfalse那么后续所有位的limit都是false。5.2 记忆化搜索的条件判断错误记忆化是性能关键但条件错了就会导致答案错误。只有!limit的状态才能记忆化因为limittrue的状态是与特定的上限N绑定的不具有通用性。对于不同的Nlimittrue的路径是不同的。通常!lead的状态才能记忆化前导零状态也可能具有特殊性。但有时经过精心设计前导零状态也可以记忆化比如将lead也作为状态维度。最稳妥的做法是在记忆化条件中加上!lead或者将lead也加入记忆化数组的维度。在上面的例题代码中我们在!limit !lead时才记忆化。数组维度大小dp[pos][pre]的大小要开够。pos最大是二进制位数例如60。pre最大是K1。如果K很大比如题目没限制可能需要调整状态定义或者用map存储。5.3 递推法的初始化与答案统计初始化递推的起点状态需要仔细考虑。是dp[0][0][0]1还是dp[0][K1][0]1这对应于一个“虚拟”的起点。通常需要根据状态定义来设定确保它代表了开始填充数字之前的状态。答案统计递推结束后dp[len][...][...]中的哪些状态应该被计入答案通常所有smt0和smt1的状态都代表不超过N的数字需要求和。但要特别注意数字0是否被重复计算或漏算。一个好的测试用例是计算f(0)。5.4 调试技巧小数据暴力对拍写一个暴力程序枚举小范围比如[0, 10000]内的所有数直接检查条件并计数。用这个结果与你的数位DP程序solve(R)-solve(L-1)的结果进行对比。这是最有效的调试方法。打印递归树在记忆化搜索的DFS函数开头打印pos, pre, limit, lead等参数。观察递归路径看状态转移是否符合预期。特别注意limit和lead的变化。检查边界情况L1, R1答案应该是1如果1合法。L0, R0答案应该是1如果0合法。LR且是一个很大的数。K值很大甚至大于数字二进制长度。使用不同的实现对比尝试用记忆化搜索和递推两种方法实现同一道题确保它们输出结果一致。5.5 复杂度分析假设数字二进制最大长度为L例如R 2^60则L60K为约束常数。状态数记忆化搜索中有效的状态是(pos, pre)且满足!limit !lead。pos有L种pre有K2种0到K1。所以状态总数约为O(L * K)。单次状态转移每个状态最多尝试填0或1即2种决策。总时间复杂度约为O(L * K * 2)对于L60, K60的情况非常快。空间复杂度O(L * K)用于存储DP表。数位DP的威力就在于它将一个与数值大小R相关的问题转化为了一个与R的位数L相关的问题从而实现了指数级的优化。掌握“二进制问题”这类数位DP就像是获得了一把钥匙它能打开诸如“不含连续数字的数”、“数字各位之和满足条件的数”、“能被某个数整除的数”等一系列问题的锁。核心永远是定义出能够完整刻画当前决策对后续影响的状态然后让搜索或递推在这个状态空间里有记忆地行进。多练习几道变种题你就能对这种思维方式运用自如了。 
长河君 · 2026/8/28 10:47:33 · 阅读 1.2k 数位DP实战：从二进制问题看状态设计与记忆化搜索
1. 项目概述从一道蓝桥杯国赛题看数位DP的实战拆解最近在复盘历年蓝桥杯国赛真题时又遇到了那道经典的“二进制问题”。这道题可以说是数位动态规划Digit DP的绝佳练兵场它把看似简单的二进制计数包装成了一个需要深度思考状态定义的难题。很多朋友初次接触时会觉得思路很绕不就是数二进制数吗但题目往往要求你在一个巨大的区间内比如[1, 10^18]统计满足特定二进制位约束条件的数字个数。暴力枚举连边都摸不着。这正是数位DP大显身手的地方。数位DP的精髓在于“按位决策”和“状态记忆”。它教会我们如何把一个大问题分解成对数字每一位的、有记忆的、递推式的求解过程。无论是记忆化搜索DFS with Memoization还是纯递推Iterative DP其核心都是设计一个能够完整描述当前决策进度的“状态”。这道二进制问题完美地展示了如何从题目描述中抽象出关键状态以及两种实现范式各自的思维路径和代码风格。理解它你就能触类旁通解决一大类“数字区间内满足某条件的数有多少个”的问题。2. 核心思路解析为什么是数位DP以及状态如何设计拿到“二进制问题”我们首先要破题。题目通常是这样给定一个区间[L, R]求区间内所有数字的二进制表示中满足“任意两个相邻的‘1’之间至少间隔 K 个‘0’”这一条件的数字个数。K是一个给定的正整数。2.1 暴力枚举为何不可行最直接的想法是遍历L到R的每个数检查其二进制形式。但L和R的范围往往极大例如1 L R 2^60这使得线性遍历在时间上完全不可能。我们必须寻找与数字大小其值无关而与数字的长度和位模式相关的计算方法。2.2 数位DP的切入点转化为前缀和相减数位DP的经典技巧是我们不直接计算区间[L, R]的答案而是计算[0, N]的答案记为f(N)。那么区间[L, R]的答案就是f(R) - f(L-1)。这样我们就把问题规约到了“求从0到N之间满足条件的数字个数”。接下来的所有思考都围绕如何高效计算f(N)展开。2.3 状态设计记忆化搜索的核心计算f(N)时我们采用深度优先搜索DFS的方式从二进制的高位向低位逐位确定数字。在这个过程中我们需要用一些参数来定义“当前搜索到了哪一步”这些参数就是状态。一个设计良好的状态必须包含所有影响后续决策的、已做出的选择信息。对于本题影响后续决策的关键因素有当前处理到的数位pos我们正在决定第pos位从高位向低位填0还是1。前一位或前K位是否填了‘1’pre为了满足“相邻1之间至少隔K个0”的条件我们需要知道最近一个被填为‘1’的位距离当前位置有多远。一个巧妙的做法是我们记录“上一个‘1’出现在距离当前位置多少位之前”。如果这个距离小于等于K那么当前位就不能填‘1’如果大于K或者之前还没填过‘1’那么当前位可以填‘1’。更具体地我们可以定义pre表示“上一个‘1’出现在pre位之前”。初始化时我们可以设pre K1或一个大于K的值表示“虚拟”的前一个‘1’在足够远的地方使得第一位可以自由选择填1。在搜索过程中如果当前位填‘0’则pre pre 1距离增加。如果当前位填‘1’则需要先判断pre K是否成立。若成立则可以填并将pre重置为1因为当前位成了新的‘1’对于下一位来说这个‘1’就在前1位若不成立则不能填‘1’。是否已经小于上限limit这是数位DP处理上限N的关键。limit是一个布尔值表示当前位之前的所有位是否都和N的对应位完全相同。如果limit为true那么当前位能填的最大值受到N在该位上值的限制即N的二进制串bits[pos]。例如N5(101)当我们固定了第一位为‘1’与N相同那么第二位就处于limit状态它最大只能填N的第二位‘0’不能填‘1’。如果limit为false则说明高位已经有某一位小于N的对应位了那么当前位可以自由填0或1在本题二进制下就是0或1不再受N的限制。这个参数保证了我们枚举的所有数字都在[0, N]范围内。是否有前导零lead处理数字时高位的‘0’可能只是占位符不代表真正的数值位。例如数字5的二进制是‘101’但如果我们用8位表示是‘00000101’。高位的‘0’就是前导零。在数位DP中前导零通常需要特殊处理因为它可能影响状态比如在统计‘1’的个数时前导零的‘0’不应被计入。在本问题中前导零会影响pre的计算。如果当前位是前导零即它本身是‘0’且它之前的所有高位也都是‘0’那么这个‘0’不应该被视为一个有效的、用于间隔‘1’的‘0’。因此在lead为真时我们填‘0’后pre不应该简单地1而可能要保持一个初始状态如K1。综上所述一个典型的状态可以定义为dfs(pos, pre, limit, lead)它返回在当前位置pos上一个‘1’出现在pre位之前是否处于上限限制limit状态是否处于前导零lead状态下能构造出的所有合法数字的个数。2.4 记忆化搜索的实现框架有了状态定义我们就可以用记忆化搜索来实现。核心是如果当前状态(pos, pre, limit, lead)之前已经计算过并且当时没有受到上限限制即limitfalse那么我们就可以直接返回缓存的结果。因为在不受到N的特定限制时从某个状态往后能构造的数字个数是确定的可以重复利用。// 假设 N 的二进制位已存入数组 bits[]长度为 len // dp[pos][pre] 用于记忆化前提是 limitfalse 且 leadfalse long long dfs(int pos, int pre, bool limit, bool lead) { // 递归边界所有位都处理完毕 if (pos len) { // 通常一个有效的数字需要被计数即使全是0数字0也是合法的 // 但有时需要排除全0的情况具体看题目要求。本题一般包含数字0。 return 1; // 找到一种合法填法 } // 记忆化只有在无限制且无前导零时结果才是通用的、可复用的 if (!limit !lead dp[pos][pre] ! -1) { return dp[pos][pre]; } long long res 0; // 计算当前位能填的上限 int up limit ? bits[pos] : 1; // 二进制所以上限是1 // 遍历当前位可能的取值 for (int i 0; i up; i) { // 根据当前位填的值计算新的状态参数 int next_pre; bool next_lead; if (lead i 0) { // 仍然是前导零状态 next_lead true; next_pre pre; // 或者保持为初始值 K1前导零不更新pre } else { next_lead false; if (i 0) { // 填0且不是前导零有效0间隔距离1 next_pre min(pre 1, K 1); // 距离超过K1后就没有更多限制了可以截断 } else { // i 1 // 填1需要检查是否满足间隔条件 if (pre K) { // 上一个1在至少K1位之前可以填1 next_pre 1; // 新的‘1’出现对于下一位距离是1 } else { continue; // 不满足条件跳过这种填法 } } } // 递归处理下一位limit参数更新为当前位是否达到上限且之前也都在上限 bool next_limit limit (i up); res dfs(pos 1, next_pre, next_limit, next_lead); } // 记录记忆化结果 if (!limit !lead) { dp[pos][pre] res; } return res; }注意pre的取值范围是[1, K1]。当距离超过K1时其限制效果和K1是一样的因为只要距离大于K就可以填1所以我们可以把大于K1的值都视为K1以压缩状态空间。这也是上面代码中使用min(pre1, K1)的原因。3. 递推迭代解法详解另一种思维视角记忆化搜索是“自上而下”的带备忘录的递归更符合人的直觉。而递推迭代解法则是一种“自下而上”的DP它需要更严谨地定义DP数组的含义和转移方程。对于数位DP递推通常有两种实现方式一种是基于“数字位长度”的预处理DP另一种是结合了“上限处理”的经典数位DP递推。这里我们讨论更接近记忆化搜索思维、但用循环实现的递推方法。3.1 递推状态定义我们定义dp[pos][pre][smt]其中pos: 当前处理到的位数从0到len。pre: 同上表示上一个‘1’出现在多少位之前取值范围[0, K1]这里用0表示尚未出现过‘1’或处于特殊初始状态可与记忆化搜索的K1初始值对应。smt: (smaller) 一个标志位0表示当前前缀与N的前缀完全相同即处于limit状态1表示当前前缀已经小于N的前缀即已脱离limit状态。这个定义直接对应了记忆化搜索中limit参数为false时的通用状态。smt1就等价于limitfalse。3.2 递推的初始化与转移递推从最高位开始向低位推进。我们需要小心处理前导零。一种常见的做法是先单独处理第一位因为它的状态比较特殊。初始化处理第0位最高位。我们可以填0作为前导零这会转移到状态(pos1, pre0, smt0)如果N的最高位是0那么填0后前缀依然等于N的前缀如果N的最高位是1填0后前缀就小于N了所以smt需要根据情况判断这里简化了实际需要分类讨论。更稳妥的方法是在循环中统一处理。我们可以填1如果不超过N的最高位检查pre初始可设为K1或一个代表“无限制”的值是否允许填1。允许则转移到(pos1, pre1, smt(i bits[0])?1:0)。实际上更清晰的递推写法是直接使用双层循环枚举状态并基于当前状态(pos, pre, smt)去更新pos1的状态。我们初始化dp[0][K1][0] 1表示在开始之前第0位之前处于“无限制”且前缀严格等于N因为还没开始填的状态有一种方案。状态转移 对于每一个状态(pos, pre, smt)我们枚举当前位pos要填的数字cur0或1。cur能取的最大值由smt和N的第pos位bit决定如果smt 1说明前缀已小当前位可以填0或1。如果smt 0说明前缀相等那么cur不能超过bit。根据cur的值和旧的pre计算新的next_pre逻辑同记忆化搜索。计算新的next_smt如果smt 1那么next_smt始终为1一旦小于永远小于。如果smt 0那么next_smt (cur bit) ? 1 : 0。状态转移方程dp[pos1][next_pre][next_smt] dp[pos][pre][smt]最终答案 所有位处理完毕后即pos lendp[len][pre][smt]就代表了以某种pre状态结束、且与N的大小关系为smt的合法数字数量。我们需要的是所有pre取值下smt为0或1的总和即所有不超过N的数字。但注意smt0代表这个数字恰好等于N我们需要确认N本身是否合法。通常我们计算f(N)时最终答案是sum(dp[len][pre][0]) sum(dp[len][pre][1])或者更简单地在递推过程中smt0和smt1的状态都代表了不超过N的数字最后对dp[len][...][...]求和即可。3.3 递推与记忆化搜索的对比思维难度记忆化搜索更直观它模拟了人脑“尝试填充”的过程状态转移隐藏在递归调用中。递推需要更显式地定义状态和转移方程思维更抽象。代码复杂度记忆化搜索的代码通常更简短逻辑集中在递归函数里。递推的代码可能需要更多的循环和边界条件处理。性能两者时间复杂度在同一量级。记忆化搜索因为有递归开销常数可能略大但在题目限制下通常无关紧要。递推有时可以更好地优化空间例如滚动数组。适用性记忆化搜索几乎可以解决所有数位DP问题是“万能”方法。某些特殊形式的数位DP如只统计特定长度、无上限限制的用递推预处理可能更高效。对于初学者我强烈建议从记忆化搜索入手。它更容易理解和调试是掌握数位DP思想的捷径。当你对状态转移烂熟于心后再去看递推解法会有更深刻的理解。4. 实战演练以一道例题完整实现假设题目为求区间[L, R]内二进制表示中任意两个‘1’不相邻即 K1的数字个数。我们以L1, R10为例进行演算。首先10的二进制是1010。我们计算f(10)。记忆化搜索步骤将10转化为二进制位数组bits [1, 0, 1, 0](高位在前)len4K1。调用dfs(0, 2, true, true)。初始pre2(K1)表示虚拟的前一个‘1’在足够远的地方。递归过程简述pos0: limittrue, leadtrue。只能填0或1因为bits[0]1。填0 (i0): next_leadtrue, next_pre2 (保持)next_limitfalse (因为01)。递归。进入一个以0开头的前导零分支最终会统计所有小于1000(8) 的合法数。填1 (i1): leadfalse, 检查 pre21 成立next_pre1, next_limittrue (因为11)。递归。pos1: 状态来自填1的分支 (pre1, limittrue, leadfalse)。bits[1]0。只能填0或1但up0limittrue所以只能填0。填0: next_pre min(11, 2)2, next_limittrue (00)。递归。pos2: 状态 (pre2, limittrue, leadfalse)。bits[2]1。up1。填0: next_pre2, next_limitfalse (01)。递归。填1: 检查 pre21 成立next_pre1, next_limittrue (11)。递归。... 以此类推直到 pos4返回1。将所有合法路径的返回值相加得到f(10)。同理计算f(0)注意区间是[L,R]我们计算f(R)-f(L-1)所以需要f(0)。f(0)通常就是数字0本身是否合法。根据题意数字0二进制0一般视为合法没有两个‘1’的问题。最终答案 f(10) - f(0)。我们可以手动验证[0, 10]的合法数字二进制不含相邻1有0(0), 1(1), 2(10), 4(100), 5(101), 8(1000), 9(1001), 10(1010)。共8个。所以[1,10]的答案应为7个排除0。通过程序计算应得到相同结果。代码实现要点记忆化搜索#include bits/stdc.h using namespace std; using ll long long; ll L, R, K; int bits[70]; ll dp[70][70]; // dp[pos][pre] pre范围[0, K1] ll dfs(int pos, int pre, bool limit, bool lead) { if (pos -1) { // 所有位处理完 return 1; // 找到一种合法方案计数1 } if (!limit !lead dp[pos][pre] ! -1) { return dp[pos][pre]; } int up limit ? bits[pos] : 1; ll res 0; for (int i 0; i up; i) { if (lead i 0) { // 仍然是前导零 res dfs(pos - 1, K1, limit i up, true); } else { if (i 0) { // 填0 int next_pre min(pre 1, (int)K 1); res dfs(pos - 1, next_pre, limit i up, false); } else { // i 1 if (pre K) { // 可以填1 res dfs(pos - 1, 1, limit i up, false); } // 否则不能填1跳过 } } } if (!limit !lead) { dp[pos][pre] res; } return res; } ll solve(ll num) { if (num 0) return 0; int len 0; while (num) { bits[len] num 1; // 低位在前方便递归从高位开始pos从len-1到0 num 1; } // 如果num为0bits为空需要特殊处理直接返回1数字0 if (len 0) return 1; memset(dp, -1, sizeof(dp)); // 从最高位(len-1)开始初始preK1limittrueleadtrue return dfs(len - 1, K1, true, true); } int main() { K 1; // 假设K1即不允许相邻的1 L 1, R 10; cout solve(R) - solve(L - 1) endl; // 期望输出 7 return 0; }实操心得在写记忆化搜索时pos的处理方向从高位到低位还是从低位到高位是个人习惯。上述代码采用了低位存储在数组前的格式递归从高位len-1向低位0进行。关键是保持bits数组和递归方向一致。另外递归边界pos -1表示所有位处理完毕。初始化dp数组为-1用于记忆化。5. 常见陷阱与调试技巧数位DP思路清晰但实现时细节魔鬼。下面是一些我踩过的坑和调试方法。5.1 状态设计不完整或错误遗漏前导零lead处理这是最常见的错误。在前导零状态下填‘0’不应该影响pre间隔计数。如果不处理会导致多算或少算。例如数字0...010高位的0是前导零它们不应该被认为在两个‘1’之间提供了间隔。pre状态含义不清或范围过大pre表示距离但距离可能无限增长。必须意识到当距离大于K之后再增加距离对决策没有影响因为已经满足可以填‘1’的条件。因此通常将pre的上限设为K1并截断可以大幅减少状态空间。例如K2pre3和pre100对于后续决策是一样的都可以填‘1’。limit标志理解错误limit为真代表之前所有位都和上限N的对应位相等而不仅仅是当前位受限制。因此更新next_limit时是limit (i up)。如果之前已经有一位小于N了limitfalse那么后续所有位的limit都是false。5.2 记忆化搜索的条件判断错误记忆化是性能关键但条件错了就会导致答案错误。只有!limit的状态才能记忆化因为limittrue的状态是与特定的上限N绑定的不具有通用性。对于不同的Nlimittrue的路径是不同的。通常!lead的状态才能记忆化前导零状态也可能具有特殊性。但有时经过精心设计前导零状态也可以记忆化比如将lead也作为状态维度。最稳妥的做法是在记忆化条件中加上!lead或者将lead也加入记忆化数组的维度。在上面的例题代码中我们在!limit !lead时才记忆化。数组维度大小dp[pos][pre]的大小要开够。pos最大是二进制位数例如60。pre最大是K1。如果K很大比如题目没限制可能需要调整状态定义或者用map存储。5.3 递推法的初始化与答案统计初始化递推的起点状态需要仔细考虑。是dp[0][0][0]1还是dp[0][K1][0]1这对应于一个“虚拟”的起点。通常需要根据状态定义来设定确保它代表了开始填充数字之前的状态。答案统计递推结束后dp[len][...][...]中的哪些状态应该被计入答案通常所有smt0和smt1的状态都代表不超过N的数字需要求和。但要特别注意数字0是否被重复计算或漏算。一个好的测试用例是计算f(0)。5.4 调试技巧小数据暴力对拍写一个暴力程序枚举小范围比如[0, 10000]内的所有数直接检查条件并计数。用这个结果与你的数位DP程序solve(R)-solve(L-1)的结果进行对比。这是最有效的调试方法。打印递归树在记忆化搜索的DFS函数开头打印pos, pre, limit, lead等参数。观察递归路径看状态转移是否符合预期。特别注意limit和lead的变化。检查边界情况L1, R1答案应该是1如果1合法。L0, R0答案应该是1如果0合法。LR且是一个很大的数。K值很大甚至大于数字二进制长度。使用不同的实现对比尝试用记忆化搜索和递推两种方法实现同一道题确保它们输出结果一致。5.5 复杂度分析假设数字二进制最大长度为L例如R 2^60则L60K为约束常数。状态数记忆化搜索中有效的状态是(pos, pre)且满足!limit !lead。pos有L种pre有K2种0到K1。所以状态总数约为O(L * K)。单次状态转移每个状态最多尝试填0或1即2种决策。总时间复杂度约为O(L * K * 2)对于L60, K60的情况非常快。空间复杂度O(L * K)用于存储DP表。数位DP的威力就在于它将一个与数值大小R相关的问题转化为了一个与R的位数L相关的问题从而实现了指数级的优化。掌握“二进制问题”这类数位DP就像是获得了一把钥匙它能打开诸如“不含连续数字的数”、“数字各位之和满足条件的数”、“能被某个数整除的数”等一系列问题的锁。核心永远是定义出能够完整刻画当前决策对后续影响的状态然后让搜索或递推在这个状态空间里有记忆地行进。多练习几道变种题你就能对这种思维方式运用自如了。