1. 从一道题看数位DP的核心思想B-number这类题目在算法竞赛圈子里算是数位DP的经典入门题之一。题目的核心要求通常是统计某个区间内满足特定数字结构条件的数的个数比如“包含子串13且能被13整除”这样的双重约束。第一次接触这类题的人往往会想用暴力枚举但一看数据范围就傻眼了——区间上界可能到10的9次方甚至更大逐个判断根本不现实。这时候数位DP就派上用场了。所谓数位DP本质上是按位处理的动态规划。它的核心思路是把一个十进制数拆成一位一位的数字然后从高位到低位逐位决策同时用状态记录当前已经满足或未满足的条件。这样做的好处是大量具有相同前缀特征的数字可以共享同一套状态从而把指数级的枚举压缩成多项式级别的状态转移。以B-number为例我们需要同时跟踪两个维度的信息当前数字对13取模的余数以及当前数字中是否已经出现了“13”这个子串。这两个维度组合起来再加上位置信息就构成了DP的状态空间。为什么用记忆化搜索来实现数位DP这是有讲究的。递推式的数位DP写起来比较绕尤其是处理上界限制的时候需要额外判断当前位是否贴着上界走。而记忆化搜索的写法更符合人的直觉我写一个dfs函数参数包括当前处理到第几位、当前余数是多少、当前是否已经出现了13、以及一个布尔标记表示当前位是否受到上界约束。如果不受上界约束说明后面的位可以自由选择0到9这时候就可以把计算结果缓存起来下次遇到相同状态直接返回。这种“贴着上界”和“自由发挥”的区分是数位DP记忆化搜索写法的精髓所在。对于B-number这道题状态设计大致是这样的dfs(pos, mod, has13, limit)其中pos表示当前处理到第几位从高位往低位数mod表示当前前缀对13取模的余数has13表示当前前缀中是否已经包含了子串“13”limit表示当前位是否受到上界约束。转移的时候枚举当前位可以填的数字d如果limit为真那么d的上限是当前位的数字否则d可以从0枚举到9。新的余数是(mod * 10 d) % 13新的has13状态取决于之前是否已经有13或者当前位和前一位是否构成了13。这里有一个容易忽略的细节判断是否形成“13”需要知道前一位填的是什么所以状态里其实还需要记录前一位的数字或者换一种方式在转移的时候直接判断。很多初学者在这里会卡住为什么状态里不需要记录前一位的数字其实可以换一种状态定义方式把“是否已经出现13”和“前一位是否为1”合并成一个三值状态0表示还没出现13且前一位不是11表示还没出现13但前一位是12表示已经出现了13。这样状态数更少转移也更清晰。这种状态压缩的技巧在数位DP中非常常见值得仔细体会。2. 状态设计与转移方程的细节拆解2.1 为什么选择三值状态而不是布尔标记前面提到判断是否出现“13”需要知道前一位的信息。如果只用布尔值has13那么在转移时就需要额外知道前一位是不是1。有两种处理方式一种是在dfs参数里多加一个pre变量记录前一位数字另一种是把has13扩展成三值状态。两种方式都能work但三值状态在记忆化时更高效因为状态空间更小缓存命中率更高。具体来说三值状态的定义如下state0表示当前前缀中还没有出现“13”且前一位不是1state1表示当前前缀中还没有出现“13”但前一位是1state2表示当前前缀中已经出现了“13”。转移规则也很直观如果当前state2那么无论填什么数字新的state仍然是2如果当前state1且填入的数字是3那么新的state变成2如果当前state1且填入的数字是1那么新的state保持1如果当前state1且填入其他数字那么新的state变成0如果当前state0且填入1那么新的state变成1如果当前state0且填入其他数字新的state保持0。这种状态设计的精妙之处在于它把“前一位是否为1”这个信息编码进了状态本身避免了在dfs参数中额外传递pre变量。状态数从原来的2种has13的真假变成了3种但省去了一个参数维度总体状态空间反而更小。在实际写代码的时候这种设计能让记忆化数组的维度更少缓存效率更高。2.2 余数状态的处理与边界条件余数状态的处理相对直接每次填入数字d之后新的余数等于(mod * 10 d) % 13。初始时mod0因为空前缀对应的数值是00对13取模还是0。最终判断一个数是否合法需要满足两个条件state2出现了13且mod0能被13整除。这里有一个容易踩的坑前导零的处理。在数位DP中如果从高位开始枚举可能会出现前导零的情况。比如统计1到1000中满足条件的数数字5实际上只有一位但在按位处理时会被当成0005来处理。前导零会影响state的转移吗答案是会。如果当前还是前导零阶段那么填入0不应该被当作“前一位是0”来处理而应该保持在前导零状态。不过对于B-number这道题来说前导零并不会影响最终结果因为前导零不会形成“13”也不会影响余数0乘以10加0还是0。但为了代码的严谨性最好还是加一个标记来区分前导零和非前导零。另一个边界条件是pos的终止位置。当pos超出数字的最高位时说明所有位都已经处理完毕此时返回(state2 mod0) ? 1 : 0。这个返回值表示当前这个完整的数是否满足条件。在记忆化搜索中只有limit为false的状态才会被缓存因为limit为true的状态依赖于具体的上界数字不具备通用性。2.3 记忆化数组的维度与初始化记忆化数组的维度取决于dfs的参数。对于B-numberdfs的参数是pos、mod、state、limit其中limit不需要被缓存因为limit为true的状态不会被重复访问所以记忆化数组可以是三维的dp[pos][mod][state]。pos的范围是数字的位数最多十位左右mod的范围是0到12state的范围是0到2。总状态数大约是10 * 13 * 3 390非常小完全可以在常数时间内完成所有状态的填充。初始化的时候通常把dp数组全部置为-1表示该状态还没有被计算过。在dfs函数中如果limit为false且dp[pos][mod][state]不等于-1直接返回缓存值。计算完当前状态后如果limit为false把结果存入dp数组。这种“先查缓存、再计算、后存缓存”的模式是记忆化搜索的标准写法。需要注意的是如果题目有多组测试数据而每次查询的区间不同那么记忆化数组在每组数据之间是否需要清空答案是如果dp数组的状态定义不依赖于具体的上界数字那么不需要清空。因为dp[pos][mod][state]表示的是“从第pos位开始当前余数为mod、状态为state且后续位可以自由选择”的方案数这个值与上界无关。所以多组数据可以共享同一个dp数组只需要在每组数据开始时把limit相关的部分重新计算即可。这一点在写题解的时候经常被忽略但实际比赛中能省下不少时间。3. 完整代码实现与逐行解析3.1 核心DFS函数的实现下面给出B-number的完整C实现代码并逐段解析关键逻辑。#include bits/stdc.h using namespace std; int dp[15][13][3]; int digit[15]; // pos: 当前处理到第几位 // mod: 当前前缀对13取模的余数 // state: 0-无13且前一位非1, 1-无13且前一位是1, 2-已有13 // limit: 当前位是否受上界约束 int dfs(int pos, int mod, int state, bool limit) { if (pos 0) { return (state 2 mod 0) ? 1 : 0; } if (!limit dp[pos][mod][state] ! -1) { return dp[pos][mod][state]; } int up limit ? digit[pos] : 9; int res 0; for (int d 0; d up; d) { int newMod (mod * 10 d) % 13; int newState state; if (state 0 d 1) { newState 1; } else if (state 1) { if (d 3) newState 2; else if (d 1) newState 1; else newState 0; } // state 2 时 newState 保持 2 res dfs(pos - 1, newMod, newState, limit d up); } if (!limit) { dp[pos][mod][state] res; } return res; } int solve(int n) { if (n 0) return 0; int len 0; while (n 0) { digit[len] n % 10; n / 10; } memset(dp, -1, sizeof(dp)); return dfs(len, 0, 0, true); } int main() { int n; while (cin n) { cout solve(n) endl; } return 0; }这段代码的核心在于dfs函数的转移逻辑。注意digit数组是从下标1开始存储最低位的所以dfs从len开始往下递归pos0时表示所有位都处理完了。这种从高位到低位的处理顺序是数位DP的标准写法。3.2 状态转移的逐行拆解在for循环中枚举当前位可以填入的数字d。如果limit为true那么d的上限是digit[pos]否则d可以从0到9。这个上限控制是数位DP的关键它保证了我们不会枚举出超过上界的数字。newMod的计算很直接(mod * 10 d) % 13。这里mod是当前前缀对13的余数乘以10再加上当前位数字就得到了新的前缀数值对13的余数。这个递推关系利用了模运算的性质避免了直接计算大整数。newState的更新逻辑稍微复杂一些。如果当前state0且d1说明前一位不是1但当前位是1新的state变成1。如果当前state1说明前一位是1此时如果d3就形成了“13”新的state变成2如果d1前一位仍然是1新的state保持1如果d是其他数字前一位不再是1新的state变成0。如果当前state2说明之前已经出现过13无论填什么数字新的state都保持2。递归调用时limit参数更新为limit d up。这意味着只有当之前一直贴着上界且当前位也贴着上界时下一位才继续受上界约束。一旦某一位填入了小于上界的数字后面的位就可以自由选择了。3.3 多组数据的处理与性能分析代码中使用了while(cin n)来处理多组输入。每次调用solve函数时都会重新memset dp数组。虽然dp数组的状态定义与上界无关理论上可以复用但为了代码简洁每次清空也不会有性能问题因为状态数只有几百个。性能方面dfs的时间复杂度大约是O(位数 * 13 * 3 * 10)对于10位以内的数字计算量在几千次操作左右完全可以在1毫秒内完成。即使有多组测试数据只要组数不是特别大总运行时间也能轻松控制在时限内。这里有一个优化技巧如果题目要求统计区间[a, b]内满足条件的数的个数可以用solve(b) - solve(a-1)来计算。这种前缀和的思想在数位DP中非常常见因为solve函数统计的是1到n中满足条件的数的个数区间查询可以通过两次前缀查询相减得到。4. 常见错误与调试技巧实录4.1 状态转移中的典型错误初学者在写B-number的时候最容易犯的错误是状态转移写错。比如在state1且d3的时候忘记把newState更新为2或者在state0且d1的时候忘记把newState更新为1。这些错误会导致最终统计结果偏少或偏多。另一个常见错误是余数的初始值设置错误。有些人在dfs的初始调用中把mod设为0这是正确的但有些人在递归过程中把newMod算成了(mod d) % 13这就完全错了。正确的公式是(mod * 10 d) % 13因为每填入一位数字原来的前缀数值要乘以10再加上当前位。还有一个隐蔽的错误是digit数组的下标处理。如果digit数组从下标0开始存储最低位那么dfs的终止条件应该是pos 0而不是pos 0。这种下标偏移错误在调试时很难发现因为代码可能在小数据上跑出正确结果但在大数据上就出问题了。4.2 记忆化搜索的缓存失效问题记忆化搜索的核心是缓存但如果缓存条件写错了就会导致结果错误。最常见的错误是在limit为true的时候也去查缓存。因为limit为true的状态依赖于具体的上界数字不同的上界数字对应的结果不同如果缓存了limit为true的状态下次遇到相同的pos、mod、state但不同的上界时就会返回错误的结果。正确的做法是只有在limit为false的时候才查缓存和存缓存。limit为true的状态直接计算不缓存。这个规则在所有的数位DP题目中都适用务必牢记。另一个缓存相关的坑是dp数组的初始化。如果多组数据之间没有清空dp数组而dp数组的状态定义又依赖于某些全局变量就会导致错误。对于B-number来说dp数组的状态定义不依赖于任何全局变量所以理论上可以不清空。但为了代码的健壮性建议每组数据都清空一次。4.3 调试技巧与验证方法调试数位DP代码的时候最有效的方法是写一个暴力枚举程序来对拍。暴力程序可以简单地遍历1到n的所有数字逐个判断是否包含“13”且能被13整除。然后用随机生成的n来测试两个程序的输出是否一致。如果发现不一致可以缩小n的范围找到第一个出错的n然后手动分析这个n的每一位是如何被处理的。另一个调试技巧是在dfs函数中打印中间状态。比如在每次递归调用时打印pos、mod、state、limit和当前枚举的d观察状态转移是否符合预期。这种方法虽然输出量大但对于定位状态转移错误非常有效。对于B-number这道题还可以用一些特殊值来验证。比如n13时答案应该是1只有13本身满足条件n26时答案应该是113满足26不满足n130时答案应该是213和130都满足。用这些特殊值来测试代码能快速发现明显的逻辑错误。5. 数位DP的通用模板与扩展应用5.1 从B-number抽象出的通用模板B-number虽然是一道具体的题目但它的解法可以抽象成一个通用的数位DP模板。这个模板的核心结构是一个dfs函数参数包括位置、若干状态变量、以及上界标记一个记忆化数组用于缓存不受上界约束的状态一个solve函数负责把数字拆位并调用dfs。通用模板的伪代码大致如下int dfs(int pos, StateType state, bool limit) { if (pos 0) return check(state) ? 1 : 0; if (!limit dp[pos][state] ! -1) return dp[pos][state]; int up limit ? digit[pos] : 9; int res 0; for (int d 0; d up; d) { StateType newState transition(state, d); res dfs(pos - 1, newState, limit d up); } if (!limit) dp[pos][state] res; return res; }这个模板可以套用到大多数数位DP题目上只需要根据具体题目定义StateType和transition函数即可。StateType可以是一个整数、一个结构体、或者多个整数的组合。transition函数负责根据当前状态和填入的数字计算新状态。5.2 数位DP的常见变体与扩展数位DP的变体非常多常见的扩展方向包括统计满足多个条件的数的个数、统计满足条件的数的和、统计满足条件的数的平方和等。对于求和的问题状态中需要额外记录当前已经形成的数的和以及数的个数转移的时候需要用到一些数学公式。另一个常见的扩展是处理二进制或其他进制。数位DP不仅适用于十进制也适用于二进制、八进制等任意进制。只需要把拆位和枚举数字的部分改成对应的进制即可。比如二进制数位DP中每位只能填0或1状态转移会更简单。还有一种扩展是处理区间查询。前面提到过区间[a, b]的查询可以通过solve(b) - solve(a-1)来实现。但如果题目要求的是区间内满足条件的数的某种统计量比如和那么直接相减可能不行需要更复杂的处理。这时候可以考虑在状态中记录更多信息或者使用差分的思想。5.3 数位DP与其他算法的结合数位DP经常和其他算法结合出现。比如与矩阵快速幂结合处理位数非常大的情况与AC自动机结合处理多模式串匹配的问题与状压DP结合处理状态空间较大的问题。这些结合方式在高级题目中很常见但核心思想仍然是数位DP的那一套按位处理、状态压缩、记忆化搜索。对于B-number这道题来说它本身已经涵盖了数位DP的核心要素多维度状态、上界约束、记忆化缓存。把这题吃透再去看其他数位DP题目会发现很多都是类似的套路。我个人建议是先把B-number这类经典题反复写几遍直到能闭着眼睛写出正确的状态转移然后再去挑战更复杂的变体。6. 实操中的性能优化与代码风格建议6.1 记忆化数组的维度压缩在实际写题的时候记忆化数组的维度直接影响缓存效率。对于B-numberdp数组是三维的dp[15][13][3]。如果能把某些维度合并就能减少缓存miss。比如state只有3种取值可以把它编码进mod维度中变成dp[15][39]其中mod*3state作为新的索引。这样做的好处是数组更紧凑缓存局部性更好。不过对于B-number这种状态数本来就不大的题目维度压缩带来的性能提升微乎其微。但在状态数较大的题目中维度压缩能显著减少内存占用和缓存miss。这是一个值得养成的编码习惯。6.2 递归深度与栈溢出风险数位DP的递归深度等于数字的位数。对于10位以内的数字递归深度最多10层完全不会有栈溢出风险。但如果题目中的数字位数达到100位甚至1000位比如处理大整数那么递归深度就会很大可能导致栈溢出。这时候需要把递归改成迭代或者手动增大栈空间。对于B-number来说数字位数最多10位递归深度很小不需要担心栈溢出。但在写通用模板的时候最好考虑到这个风险必要时使用迭代版本的数位DP。6.3 代码风格与可读性建议数位DP的代码虽然不长但状态转移的逻辑比较绕容易写错。建议在写代码的时候把状态的定义和转移规则用注释写清楚方便自己和他人阅读。变量命名也要有意义比如用has13而不是h用remainder而不是r。另外建议把dfs函数和solve函数分开写solve函数负责拆位和初始化dfs函数负责状态转移。这样代码结构更清晰也方便调试。如果题目有多组数据可以在main函数中循环调用solve函数。最后建议在写完之后用暴力程序对拍确保正确性。数位DP的边界条件比较多手动测试很难覆盖所有情况对拍是最可靠的验证方法。