刷算法题这些年数位DP算是我见过“套路化”程度最高的一类问题了。头一回接触的时候我在深夜对着limit和lead两个参数硬扛了三个小时怎么都想不明白一个记忆化搜索为什么要写这么多奇怪的参数后来想通了才发现数位DP的模板一旦吃透基本就是复制粘贴改三行的事真正花心思的地方全在状态设计上。这篇就把我一直在用的模板、每个参数背后的道理以及我踩过的坑完整拆开讲一遍适合刚刚接触数位DP、被一堆题解绕晕的读者也适合想把手头模板整理得更稳妥的老手。数位DP解决的是一类非常典型的“区间计数”问题给你一个区间[L, R]统计满足某个条件的整数个数而这个条件恰好只和十进制位上的数字有关。比如不含数字4、不含连续“62”、能被K整除、某个数字出现不超过几次诸如此类。暴力做法是从 L 到 R 循环逐个判断当 R 是10^18级别时这个循环注定跑不完。数位DP的聪明之处在于它根本不打算把每个整数都生成出来而是把整数看成一段固定长度的“数字串”从高位往低位逐个填数用记忆化搜索把重复计算的子树合并掉。下面我从最底层的思路讲起再给出可以直接抄走的模板。1. 数位DP到底在处理什么问题——从暴力数数说起1.1 一类问题的共同画像先看几个问题长什么样子统计[1, n]中不含数字4的数字个数统计[1, n]中不含连续62的数字个数统计[1, n]中各位数字之和能被7整除的数字个数统计[1, n]中数字0到9各自出现的总次数。把这些问题放在一起看它们的共同点非常明显区间上下界很大大到绝对不能逐个枚举判定条件只依赖十进制表示本身不依赖这个数在数轴上的位置、不依赖质因数分解这类深层性质。换句话说条件是“局部”的只要你在填数字串的过程中记住前几位留下的某些摘要信息就足以决定下一位能不能填、填完之后的答案怎么更新。这种“摘要信息”就是数位DP里的状态。它可以是上一位数字是什么、当前数字和模K的余数、某个数字已经出现了几次、出现过哪些数字的bitmask等等。只要这个状态能随着填位不断递推计数问题就转化成了一个在状态图上走步的问题。1.2 核心观察逐位决策替代整数值域扫描为什么逐位填数会比扫描整个区间快原因很朴素一个位数是len的数把它当成数字串来看长度最多 1910^18级别而每一位只有 0 到 9 十种选择。如果设计一棵决策树从最高位开始往下填那么理论上整棵树的叶子数是10^len还是很大。但是数位DP真正利用的是另一件事决策树里大量的子树是“完全等价”的。举个例子假设当前已经填了高三位剩下的四位还没有填。只要高三位没有触碰到 n 的数字上界限制那么剩下四位可以自由选择 0-9 的所有组合且这些组合的合法数量只取决于你关心的状态跟你高三位具体填了123还是456没有任何关系。于是“剩下四位自由填”的这个子树只需要计算一次之后所有相同状态的高位都可以直接复用结果。这就是记忆化搜索的威力用状态数量压缩掉指数级的枚举量。你可以把整个过程想象成“猜电话号码”。不去逐个拨打一亿个号码而是先确定第一位是几再确定第二位是几每一位的决策都会缩小范围而很多局部情况比如前几位都一样、后面随便配可以共用同一套结论。猜电话号码不是暴力拨打数位DP也不是暴力枚举。1.3 从“数值”到“数字序列”的三步转换无论题目怎么变落到代码上几乎都是固定三步把整数 n 拆成十进制数字数组。我这里习惯从低位到高位存digits[1]是个位digits[len]是最高位递归的时候从pos len往pos 0扫。写一个dfs(pos, state, limit, lead)表示当前正在决策从高到低第pos位已经收集到的摘要信息是statelimit表示之前的高位是否已经贴着 n 的上界lead表示当前是不是还在“前导零”阶段。写出solve(n)返回值是区间[0, n]里的合法数字个数。最终两个区间相减得到[L, R]的答案solve(R) - solve(L-1)。这里特别说明为什么统一用[0, n]。因为后续区间减法非常自然[L, R]的答案等于[0, R]减去[0, L-1]。你只需要把一个solve函数写对就能应付所有区间查询。至于0这个数本身算不算是另一个边界细节我放在第 5 章专门说。2. 记忆化搜索模板dfs(pos, limit, lead) 三个参数撑起半边天2.1 模板骨架这是我一直在用的模板骨架几乎所有数位DP题目都是从它改出来的using ll long long; ll f[20][STATE_SIZE]; // 根据题目状态维度调整 int digits[20]; // 从低位到高位拆好的数字 // pos: 当前还剩多少位要填state: 自定义的摘要状态 // limit: 之前高位是否紧贴上界lead: 是否处于前导零阶段 ll dfs(int pos, int state, bool limit, bool lead) { if (pos 0) { // 所有位都填完了检查最终状态是否合法 return valid(state) ? 1 : 0; } // 只有完全自由!limit !lead的子树才能安全记忆化 if (!limit !lead f[pos][state] ! -1) { return f[pos][state]; } // 当前位能填的上限受 limit 控制 int up limit ? digits[pos] : 9; ll ans 0; for (int d 0; d up; d) { bool next_lead lead (d 0); // 根据题目规则用 d 更新 state得到 next_state ans dfs(pos - 1, trans(state, d, next_lead), limit (d up), next_lead); } if (!limit !lead) f[pos][state] ans; return ans; } ll solve(int n) { if (n 0) return 0; int len 0; while (n 0) { digits[len] n % 10; n / 10; } memset(f, -1, sizeof(f)); return dfs(len, 0, true, true); }这个骨架里的valid、trans都是占位函数实际题目中要么直接写在循环里要么用全局变量配合。关键在于循环里的三个传递规则limit (d up)会严格保证“如果之前贴着上界那么当前位也必须贴着上界填”这一约束一路传下去next_lead lead (d 0)则保证“只要还在前导零阶段后面填出来的每一位都是无效的零”。2.2 limit 参数为什么必须进状态limit这个参数可能是初学数位DP时最困惑的一个东西。它其实就是“这个数目前有没有被 n 卡住”的标记。假设 n 是325我们正在填第一位如果第一位填1那么第二位可以从0填到9任意选没人管你因为即使后面填到99总数也只是199仍然小于325如果第一位填3那第二位就必须受上界约束只能在0到2之间选否则填出330就越界了。这种“有没有被上界约束”的区别直接决定了当前子树能不能被记忆化。原因在于当limit false时后面的每一位都是完全自由的答案只取决于pos和state与前面具体填了什么数字无关所以完全可以缓存当limit true时后面能填什么取决于 n 的具体数字结构这种子树在整棵搜索树里出现的次数非常少实际上沿着上界走只有一条路径缓存它既没有意义也容易因为细节处理不当而写错。所以模板里记忆化的条件严格写成!limit !lead少一个!都不行。这个坑我在第 5 章会专门展开。2.3 lead 参数与“0的歧义”lead的全称是 leading zero表示“前导零”。为什么要单独管它因为前导零和数字零在语义上完全是两回事。举个最经典的例子统计[1, n]中数字0出现的总次数。数字102里只有一个0但如果把102按三位补零写成102最高位之前并没有多余的0而数字5如果补零写成005那两个被补出来的0是绝对不应该算进“数字0出现次数”的。lead参数就是用来区分“这个 0 是不是一个有效数字”的。初始调用dfs(len, 0, true, true)里的lead true表示还没填出任何非零有效位。一旦某个位置填了非零数字lead就变成false之后所有0都是真实的数字零。如果某个题目完全不关心前导零比如“不含数字4”理论上可以不处理lead但考虑到统计类题目经常涉及数字出现次数我建议模板里永远保留lead一劳永逸。3. 模板落地用“不含62”跑通第一个完整程序3.1 题目与状态设计经典题目来了统计[1, n]中不含数字4也不含连续62的数字个数。这是一个非常标准的入门题用来验证模板再好不过。要判断“不含连续62”我们需要在填下一位的时候知道上一位是不是6。所以自定义状态只需要一维pre6取值0或1表示上一位是不是6。转移规则如下当前位d 4直接剪枝如果pre6 1且d 2说明形成了62直接剪枝否则继续填位新状态的pre6更新为(d 6)。这里没有额外的valid检查因为只要全程没有剪枝自然就是合法数字。边界pos 0直接返回1即可表示“成功走完了一条合法路径”。3.2 完整代码与逐段解读#include bits/stdc.h using namespace std; using ll long long; ll f[20][2]; int digits[20]; ll dfs(int pos, int pre6, bool limit, bool lead) { if (pos 0) return 1; if (!limit !lead f[pos][pre6] ! -1) { return f[pos][pre6]; } int up limit ? digits[pos] : 9; ll ans 0; for (int d 0; d up; d) { if (d 4) continue; // 不含数字4 if (pre6 d 2) continue; // 不含连续62 ans dfs(pos - 1, d 6, limit (d up), lead (d 0)); } if (!limit !lead) f[pos][pre6] ans; return ans; } ll solve(int n) { if (n 0) return 0; // 区间 [1, n]n0 时没有合法数字 int len 0; while (n 0) { digits[len] n % 10; n / 10; } memset(f, -1, sizeof(f)); return dfs(len, 0, true, true); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int L, R; while (cin L R) { if (L 0 R 0) break; cout solve(R) - solve(L - 1) \n; } return 0; }这个程序里值得注意的一个细节是solve(0)。因为题目区间是[1, n]n 0时本来就没有正整数所以直接返回0。如果题目要统计[0, n]你就要单独考虑数字0是否合法这一点我会在后面边界小节里再提。模板另一个关键点是memset(f, -1, sizeof(f))的位置每次调用solve(n)都要清空一次f数组。原因很简单不同的 n 拆出来的数字不同之前缓存的“自由子树”结果虽然可能仍然适用但为了安全起见比赛时直接全清是成本最低的选择。反正f数组通常只有20 * 状态数个元素memset 的开销可以忽略。3.3 用暴力对拍确认模板正确写完模板一定要对拍这是我反复强调的习惯。对数位DP来说最简单有效的验证方式是写一个纯暴力函数小范围枚举并逐个判断然后和数位DP的结果做对比。bool ok(int x) { while (x 0) { if (x % 10 4) return false; if (x % 100 62) return false; x / 10; } return true; } ll brute(int n) { ll cnt 0; for (int i 1; i n; i) { if (ok(i)) cnt; } return cnt; }然后在main里写个循环随机生成n比较solve(n)和brute(n)。我一般会跑几百组1 n 100000的随机数据只有全部一致才放心往下写题。很多人觉得对拍麻烦但数位DP的状态一旦设计错样例可能全过交上去却错得莫名其妙对拍能帮你把这个环节的试错成本压到最低。4. 状态设计升级从“无脑填数”到“关系型状态”4.1 例一统计数字 d 在 [1, n] 中出现的总次数“不含62”只需要记住上一位是不是6本质上是一个很简单的邻居关系状态。但更多的题目需要你把“已经统计出什么东西”也放进状态里。比如这个题给定d统计[1, n]中数字d出现的总次数。思路是dfs的返回值不表示“合法数字个数”而表示“后续继续填数时最终累计得到的 d 出现次数”。所以状态里要有一个cnt表示在已经填好的高位部分里数字d出现了几次。等所有位都填完直接返回cnt。ll f[20][20]; int target; ll dfs(int pos, int cnt, bool limit, bool lead) { if (pos 0) return cnt; if (!limit !lead f[pos][cnt] ! -1) { return f[pos][cnt]; } int up limit ? digits[pos] : 9; ll ans 0; for (int d 0; d up; d) { bool next_lead lead (d 0); int add 0; if (!next_lead d target) add 1; // 非前导零才算数 ans dfs(pos - 1, cnt add, limit (d up), next_lead); } if (!limit !lead) f[pos][cnt] ans; return ans; }这里add的判断特别容易写错。next_lead是“下一轮是否依然处于前导零阶段”它等价于“当前填的这个 d 是不是一个无效的占位零”。如果next_lead false说明当前位已经是真实数字的有效位此时d target才会计数。比如统计数字0时数字100里的两个0都是有效零会被正确计入而数字5前面补的00因为next_lead仍然是true不会被计入。4.2 例二能被 K 整除的数字个数另一类非常常见的状态是“余数状态”。题目让你统计[1, n]中能被K整除的数字个数。既然要判断整除最好的递推方式就是记录当前已经形成的数字模 K 的余数。每填一个新的数字d余数更新为(rem * 10 d) % K。ll f[20][100]; // 假设 K 100 int K; ll dfs(int pos, int rem, bool limit, bool lead) { if (pos 0) { return (rem 0) ? 1 : 0; } if (!limit !lead f[pos][rem] ! -1) { return f[pos][rem]; } int up limit ? digits[pos] : 9; ll ans 0; for (int d 0; d up; d) { ans dfs(pos - 1, (rem * 10 d) % K, limit (d up), lead (d 0)); } if (!limit !lead) f[pos][rem] ans; return ans; } ll solve(int n) { if (n 0) return 0; int len 0; while (n 0) { digits[len] n % 10; n / 10; } memset(f, -1, sizeof(f)); return dfs(len, 0, true, true); }注意两个细节第一dfs的边界直接判断rem 0因为数字 0 的余数本来就是 0所以这个写法实际上把数字0也计入了。如果题目统计的是[1, n]solve(n)的结果会多算一个0需要额外减1或者在拆位时特判。第二如果K很大比如K 1e9你不可能开一个f[20][1000000000]的数组这时候就需要用别的策略我放在第 6 章展开。前导零在这里其实不影响模运算rem * 10 0跟在真实数字后面补零的运算完全一致所以不需要特别处理前导零的“合法性”只要保持lead状态正确传递就行。这也是为什么模板统一带lead会省掉很多心智负担。4.3 多条件叠加的状态组合策略实际题目经常是多重条件叠加的比如“各位数字之和能被K整除且不含4”或者“二进制表示中不含连续1”。这时候你的状态可能就是多维的。我总结了一个简单的状态设计表能覆盖大多数情况条件类型需要记住的信息状态维度不含某个数字无需额外信息无直接剪枝不含连续模式如62上一位是谁last digit或压缩成关键位各位和满足条件当前数字和sum能否被K整除当前数模K的余数rem某个数字出现次数限制已出现次数cnt所有数字的奇偶/出现情况哪些数字出现过bitmask2^10设计状态的时候要想清楚两件事第一**决定下一位能不能填我需要记住哪些信息**第二这些信息有哪些取值范围能不能压得很小“62”问题里其实不需要记住完整的上一位只需要记住“上一位是不是6”所以状态压到一维0/1如果题目变成“不含连续质数相邻”你可能就得记住上一位具体是几状态变成10。状态越小记忆化数组越小跑得越快也越不容易写错。5. 模板实战中的坑limit、lead、越界的反直觉行为5.1 经典错误把 limit 状态也缓存了这是我见过最多的一个错误。有人图省事直接写if (f[pos][state] ! -1) return f[pos][state];完全不判断!limit !lead。表面上看好像没什么问题——状态一样、位数一样答案不是应该一样吗问题在于limit true意味着高位被 n 卡住了你面对的数字集合和limit false时根本不是同一个集合。比如n 325从高位递归到某个状态时limit true的情况只有沿着3 - 2 - 5这一条路径出现而limit false的情况却会出现无数次。如果不区分就直接返回缓存可能把受限路径的结果和某条不受限路径的结果混在一起答案时对时错极其阴间。正确的记忆化条件必须是if (!limit !lead f[pos][state] ! -1) { return f[pos][state]; }limit true的子树根本不去尝试读缓存每次现场计算。这样做的代价极小因为受限路径在整个搜索过程中出现的次数非常少。5.2 前导零导致的状态污染与统计偏差如果完全不管lead统计类题目会出大问题。我举个例子统计数字0在[1, 100]中出现的次数。正确答案里10有一个020有一个0一直到100有两个0总共是11个。但如果你的 DP 不区分前导零所有不足三位的数字都会在高位补出若干个无效0被计入答案最后结果会变成一个离谱的大数。另一个相关问题是记忆化时的lead条件。有人会把!lead从记忆化条件里去掉也就是在lead true的状态也写缓存。这么做不是绝对不可但很容易因为状态设计不完整而出错。更稳的做法是模板里一律只在!lead时缓存前导零阶段的高位都是0这种情况下子树形态相对简单重算几次也无所谓换来的是逻辑上的绝对安全。5.3 边界问题0、n 本身、区间的开闭数位DP的边界问题虽然不算难但出错的频率非常高。常见的几个细节如下solve(0)到底返回什么这取决于题目语义。统计[1, n]时数字0不在区间内所以solve(0)应当返回0最简单的做法是在solve开头加if (n 0) return 0;。统计[0, n]时0是否满足条件要看题面很多整除类题目里0是满足“能被K整除”的那就要保留它。区间减法solve(R) - solve(L-1)里当L 0时访问solve(-1)会出问题所以要么在solve里做n 0的特判要么在调用前特判。拆位时用while (n 0)那么n 0时len 0digits数组为空。如果你不小心直接dfs(len, ...)pos 0会立刻触发边界返回的可能是一个没经过任何剪枝的固定值同样会出错。建议不要随便让solve(0)走通用流程直接特判最省心。n本身的合法性不用额外担心因为dfs的上界约束limit会保证枚举到n就停下不会把n1之类的数算进去。5.4 常数优化与递归安全数位DP的常数优化大多数时候用不到因为状态数本身不大但几个习惯还是可以养成f数组初始化为-1因为有些状态的自然答案就是0用0当“未计算”标记会导致这些答案永远无法缓存。多组数据时直接memset(f, -1, sizeof(f))即可f通常撑死也就20 * 100个long long一点不心疼。剪枝判断尽量前置。比如上面“不含62”的代码里d 4的判断应该放在递归调用前能剪就剪不要等进去再判断虽然对常数影响不大但代码逻辑更清晰。递归深度最多等于位数通常不超过 19不用担心爆栈放心递归。6. 把模板抽象成自己的库参数化、打包与进阶方向6.1 通用接口设计条件与状态的解耦用多了之后你会发现每个数位DP题目只有三个地方是真正需要改的初始状态、状态转移、边界判定。拆数字、写solve、处理limit和lead的传递逻辑千篇一律。所以我建议把自己的模板按下面这个结构组织起来struct DigitDP { vectorint digits; // 定义状态维度比如 int state; // 定义转移函数从 state 和当前数字 d得到 next_state // 定义边界判定pos 0 时如何根据 state 返回 0/1 ll dfs(int pos, int state, bool limit, bool lead) { // 固定骨架 } ll solve(int n) { // 拆位、清空缓存、调用 dfs } };具体的trans、valid可以写成成员函数也可以直接用全局变量加静态函数。C 的std::function包装虽然优雅但竞赛场景下性能略差且容易引入心智负担我更推荐直接复制模板改三行的做法。框架化适合长期维护题库但对不起“模板”这个词的定位——模板要的就是快、准、稳。6.2 不能用普通数组开状态时怎么办遇到状态空间特别大的题目f[pos][state]这种二维数组就不适用了。常见应对方案有三种用哈希表缓存如果状态虽然多但实际访问到的很少可以用map或unordered_map存缓存键。但注意limit和lead也要合进键里或者继续沿用“只在自由状态写缓存”的策略。状态压缩2^10的 bitmask 完全可以开数组但如果状态是2^30级别的就得想办法压缩比如只保留必要的出现关系而不是完整集合。矩阵快速幂当len极大比如n是10^18甚至更高精度的大数且状态转移是线性的可以把状态转移看成矩阵乘法用快速幂把复杂度从O(len * state^3)优化到O(state^3 * log len)。这个方向比较进阶但理解了之后能解决一批“位数大到离谱”的题目。6.3 你可以继续扩展的几个方向数位DP的能力边界比很多人想象的宽得多。除了上面这些基础题型我实际用到的进阶方向至少有这几个第 K 大合法数字先solve(mid)二分答案找到最小的mid使得合法数字个数正好达到K。只需要额外实现一个“从高到低逐位复原合法数字”的过程本质还是 DFS 加计数。禁止出现若干模式串把模式串建成 AC 自动机状态变成“当前匹配在自动机的哪个节点”数位DP 加自动机一起用。这个组合在字符串计数题里很强。高精度大数的数位DP如果 n 不是二进制位数而是 1000 位的十进制高精度数len 1000也能跑数组改成f[1005][state]递归深度稍微大一点但思路完全一样。数位DP 二分 方案还原在合法数字里找满足附加条件的对象多一个记录“每个位置可填哪些数字”的过程复杂度仍然可控。最后再分享一点个人体会数位DP这套模板我用了好几年最大的心得其实不在代码而在“题型嗅觉”看到一个计数题先想清楚它能不能转化成逐位填数的决策过程再想清楚“决定下一步需要记住哪些信息”。这两步想明白了模板就是复制粘贴改三行的事。真正让我翻过车的地方永远都是边界0算不算、前导零要不要统计、limit的缓存条件有没有写齐。所以我再次建议任何数位DP代码写完先跟暴力对拍几百组再交这套动作能帮你省下至少好几次“看似 AC、实则 WA”的深夜debug时间。把这个模板吃透你在区间计数题上的底气会和以前完全不一样。