数位DP模板详解：从记忆化搜索到前导零与边界处理

聊到数位dp模版，很多人第一反应是“背代码”。但我见过太多背了代码就上路的人，碰到一道把“不含连续相同的两位”改成“不含连续上升的三位”的题，直接歇菜。我自己最开始接触这玩意儿，也是在某个竞赛准备阶段，当时网上能找到的模板写法五花八门，抄了十几次才真正搞明白每个状态到底该不该存。这篇文章专门把数位dp模板的来龙去脉讲透：它适合什么问题、为什么记忆化搜索是主流、前导零和上限边界这两个难点怎么处理，以及完完整整的模板代码和改造成三类题的过程。想看结论直接抄模板的可以，想把它真正变成自己武器的，更欢迎跟着过一遍。

1. 数位DP模板到底在解决什么问题

1.1 从一个“大区间统计”场景说起

数位DP是动态规划里非常有标志性的一类，核心任务是：给你一个区间 [L, R]，统计这个区间里有多少个数字满足某个“和数位本身有关”的条件。例子随手就能举出一堆：数字里不包含数字4、所有数位加起来能被7整除、不存在连续相同的两位、第偶数位上不能出现奇数……这些描述的共同点是，它们只看数字的十进制写法，不看数字在数学意义上的大小、因式分解或者奇偶性，所以天然适合拆成一位一位来处理。

这类问题的范围通常很大。竞赛里常见的范围是 1 到 10^18，体现为 long long 级别的端点；面试里也可能出现 R 不超过 10^9 的版本，但如果只想单纯枚举，10^9 就已经能把一般的程序卡到超时。换一个思路：把上限值拆成十进制位，例如 R = 12345，我们就认为所有包含在 [0, R] 里的数都可以表示成一个“最多5位，高位可以补前导零”的数字串。然后从最高位开始，一个分支一个分支地往下填：第一位填 0 或 1 时，后面四位完全不受限制；第一位填 1 且第二位填 1 时，一样不受限制；一旦第一位填了 1、第二位填了 2 但第三位顶到了 3，后面的位上界就又被锁住了。

这种按位枚举会产生大量结构相同的子问题。比如“当前已经填到第3位，前面没有触发任何限制，剩余位数随便填，问合法方案数”这样的情况，无论前面实际填的是 123 还是 456，只要状态一致，算出来的结果就是同一个数。把这些重复结果缓存下来，就得到了数位DP。它本质上是在按数字字典序构建的一棵 10 叉树上做剪枝和记忆化。

1.2 判断一道题能不能套模板的“三看”

不是所有“统计数字个数”的题都能用数位DP。我用得多了之后，总结出三个条件，同时满足的题目几乎都可以套模板：

• 看范围。端点大概率超过 10^7，直接遍历会超时；如果范围只有几千，暴力枚举反而更省事。
• 看条件的“局部性”。判断一个数字是否合法，需要的状态能不能随着从高位到低位扫描逐步维护。比如记录上一位数字、数位累加和、是否已经出现过某个数字，这些都可以；但如果是“判断整个数是不是质数”“判断整个数是否为回文数”，回文虽然也能用数位DP做，但状态会特别复杂，需要记录一半数字，代价高。
• 看区间减法。题目要求 [L, R] 的答案，而模板通常只做 [0, X] 的答案，两者相减即可。大多数题目都满足，偶尔有涉及绝对值的题需要特判。

反面例子也能说明问题：统计 [L, R] 内“质数”的个数，数位DP就没法直接用，因为你无法在只观察当前位的情况下确定最终数是不是质数；统计“完全平方数”也一样，状态必需要等到拼出完整数字之后才能判断。这类题需要数论工具，别硬套数位DP。

2. 模板总体设计：为什么记忆化搜索成了默认选择

2.1 递推也能做，但大多数人该选记忆化

数位DP有两种实现路线：一种是纯递推，类似于背包那样写两层循环加边界；另一种是递归加记忆化，通常叫 DFS。纯递推在“是否顶到上界”这个维度上处理起来很绕，需要额外维护一个 tight 数组表示前缀是否和上限完全一致。我第一次写递推版时，状态转移顺序错乱，排了很久的 bug，后来干脆放弃，改用记忆化搜索。

记忆化搜索的思路是：直接按照“我在从高位往低位填数字”这个自然过程写递归，参数是谁都能看懂的当前位下标、前面填了什么、是否贴着上限、前面是否全是前导零。递归过程天然枚举每一种填法，遇到重复子问题就把结果存起来。调试的时候也容易，打印一下参数就能看到整个搜索过程。所以现在公开的模板十有八九是 DFS 版本，我也推荐用它做底子。

2.2 状态里的四个关键参数和一个缓存数组

一个通用的数位DP递归函数，参数基本可以模板化为这样：

• pos：当前正在填哪一位，一般从最高位的下标开始，填到 -1 结束。
• state：业务状态，可能是“上一位数字是多少”，也可能是“到目前为止数位和是多少”，还可能是一个压位后的标志，比如是否已经出现过某个数字。
• limit（也叫 tight / bound）：当前这一位是否被上限卡住。如果前面的位都顶着上限，那么当前位最大只能取 num[pos]；否则可以从 0 填到 9。
• lead：目前填过的位是不是全都是前导零。比如数字 7 在三位框架下写作 007，前面两个 0 不算真正的数字位，很多题目需要区分这一点。

dp 数组一般开到 dp[pos][state] 甚至更多维，里面存的是：在某种 pos 和 state 组合下，并且不受上限约束、也已经脱离前导零状态时，往下还有多少种合法填法。注意我特别强调“不受上限和不带前导零”，因为当 limit 或 lead 为真时，这个搜索分支是唯一的，不会被其他数字复用，缓存它没有意义。

用生活化的话说：limit 相当于一个“紧箍咒”，前缀已经顶到上限时，后面的枚举范围变小；lead 相当于“还没开始动真格”，填的 0 都只是占位符，不影响业务状态。这两个标志是数位DP模板里最容易理解错、也最容易写错的地方。

2.3 前导零必须单独处理吗

这个问题几乎每个学数位DP的人都会卡一次。先说结论：如果统计的是“0 到 X”之间满足条件的整数，0 本身也算一个数，这时候前导零不影响结果，因为 0 的每一位都是前导零，它对应的合法性与“没有填入有效数字”是一致的；如果题目说的是“1 到 X 之间”或者“所有位数的数字都必须有意义”，比如统计长度恰好为 m 的数，那前导零就必须显式处理。

常见技巧是用一个特殊值表示“空状态”。比如状态是“上一位数字是多少”，我们就可以用 pre = -1（或十进制下用 10）表示“前面还没有任何有效数字”。当前一位是空状态时，它不会和任何真实数字重复。这样，lead 参数和空状态表达的是一个意思，二选一也能写。

3. 一套通用模板的可执行代码

3.1 完整模板：统计区间内没有相邻相同数字的数字个数

为了不让记忆停留在抽象参数上，先给一套可以直接编译运行的最小模板。它统计 [L, R] 之间有多少数字，满足“任意相邻两位不相同”，0 被当作合法数字计入。这也是最经典的一道数位DP入门题。

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll f[20][11]; // f[pos][pre]，pre 的取值 0~9 表示上一位数字，10 表示空状态 int num[20]; ll dfs(int pos, int pre, bool limit, bool lead) { if (pos == -1) return 1; if (!limit && !lead && f[pos][pre] != -1) return f[pos][pre]; int up = limit ? num[pos] : 9; ll ans = 0; for (int i = 0; i <= up; i++) { if (lead && i == 0) { // 仍然全是前导零，pre 继续保持空状态 ans += dfs(pos - 1, 10, limit && i == up, true); } else { if (i == pre) continue; // 相邻两位相同，剪掉 ans += dfs(pos - 1, i, limit && i == up, false); } } if (!limit && !lead) f[pos][pre] = ans; return ans; } ll solve(ll x) { if (x < 0) return 0; int len = 0; while (x) { num[len++] = x % 10; x /= 10; } if (len == 0) { num[len++] = 0; // 单独处理 x == 0 } memset(f, -1, sizeof(f)); return dfs(len - 1, 10, true, true); } int main() { ll L, R; while (cin >> L >> R) { cout << solve(R) - solve(L - 1) << endl; } return 0; }

这个代码是完整可用的。解释几个细节：

• pre = 10 表示空状态；当 lead 为 true 时每次遇到 i == 0，仍然传入 pre = 10、lead = true，说明当前还是一个占位零。
• 当第一次填入非零数字时，pre 被设为该数字 i，lead 变 false。以后相邻相同判断就正常生效。
• 缓存条件是 !limit && !lead，也就是这种情况的状态数量最多、复用价值最大。

3.2 逐段拆解主干代码

先看终止条件。pos == -1 意味着所有位都已经填完，一路走过来没有被剪枝，所以返回 1，代表“当前构造的这一个数字合法”。很多人理解成“答案加一”的起点，其实更准确的说法是：这是一个递归基，它把前面每条合法路径都贡献成 1 个计数。

再看记忆化访问。!limit && !lead && f[pos][pre] != -1表示可以安全读取缓存。为什么必须去掉 limit 和 lead？因为只要 limit 为真，说明前面已经有一个前缀顶到了上限，这条分支是当前这个 X 特有的，其他数字不会用到；lead 为真同理，它是某个搜索分支的独有过程。只有两种标志都为假，状态才是“通用的”，才能被不同枚举路径共享。

枚举范围上，int up = limit ? num[pos] : 9是边界控制的核心。如果前缀已经被上限限制，这一位最多取到 X 的对应位；否则 0 到 9 随便取。注意这里用的 num[pos] 是倒序存好的数字位，所以 pos 越小表示位越低。

前导零分支里，lead && i == 0时我们不会进入任何业务判断，而是继续“什么都没填”的状态。在这套模板里，这个分支的意义是让数字 0 本身也能走进递归到最后，同时避免占位零被误判成“和上一位相同”。

缓存写入的一步经常被忽略。写入前判断!limit && !lead，写入的是“当前位置 pos、前驱 pre 时，剩余位置的合法方案数”。因为 limit 和 lead 为假时，这个值跟 X 是多少无关，后面再次遇到相同状态时能直接复用。

最后，main 函数里的区间减法solve(R) - solve(L - 1)是数位DP的标配。绝大多数模板能力只覆盖 [0, X]，要拿一个区间的答案就转换成两个前缀答案的差。涉及大数时，L - 1 的减法也要自己实现，这点后面会再说。

3.3 边界情况：X=0 和 L=0 的处理

我在这里专门停下来说一句：X = 0 是最容易被模板坑到的边界。上面代码的 solve 函数，如果 x = 0，while 循环一次都不会执行，len 保持为 0，然后 dfs 会拿到 pos = -1 直接返回 1，看起来好像结果还行。但如果你的模板在 while 之前给 len 一个固定初值或者访问 num[len-1]，就会出错。稳妥做法是显式判断，像代码里那样if (len == 0) num[len++] = 0;，让 0 也走一遍“只有一位是 0”的搜索过程，结果依然可控。

L = 0 的情况等于调用 solve(-1)。千万不要让 solve 内部访问 num 数组或者做取余操作，一句if (x < 0) return 0;放在函数开头，避免负数端点带来的未定义行为。竞赛里端点可能给 0，也可能给负数，这个保护几乎可以无脑加。

4. 模板实战：三道高频例题套模板

4.1 例题一：统计不含数字4的个数

这道题就是经典的“幸运数字”变体：给定 [L, R]，问有多少个数字在十进制表示中不含数字 4。模板里只需要把业务判断改成if (i == 4) continue;。同时因为不再关心上一位是谁，pre 这个业务状态可以删除，连带着 dp 数组也可以从二维缩成一维。

ll f[20]; ll dfs(int pos, bool limit, bool lead) { if (pos == -1) return 1; if (!limit && !lead && f[pos] != -1) return f[pos]; int up = limit ? num[pos] : 9; ll ans = 0; for (int i = 0; i <= up; i++) { if (i == 4) continue; ans += dfs(pos - 1, limit && i == up, lead && i == 0); } if (!limit && !lead) f[pos] = ans; return ans; }

这个简化版仍然正确地把 0 计入答案。如果题目要求“正整数且不带 0”，最后可以solve(R) - solve(L - 1)，L 保持题目给定值；如果 L 本身是 1，也可以solve(R) - 1，但我更推荐减法通用形式，因为改 L 时不容易出错。

4.2 例题二：数位之和能被K整除

题目变成：统计 [L, R] 内数字的数位和能被某个固定 K 整除的个数。这里业务状态从 pre 换成 sum，参数里带上当前数位和模 K 的结果。递归结束时要求 sum == 0。

int K; ll dp[20][128]; // K 需要根据题目调整上限 ll dfs(int pos, int sum, bool limit, bool lead) { if (pos == -1) return (sum == 0 ? 1 : 0); if (!limit && !lead && dp[pos][sum] != -1) return dp[pos][sum]; int up = limit ? num[pos] : 9; ll ans = 0; for (int i = 0; i <= up; i++) { ans += dfs(pos - 1, (sum + i) % K, limit && i == up, lead && i == 0); } if (!limit && !lead) dp[pos][sum] = ans; return ans; }

这里有个容易犯的错误：如果在 lead 为 true 时仍然把 i 加进 sum，前导零会把多个占位零也加进去，但占位零不影响数位和，因为加的也是 0，所以这个题目不受影响。反过来，如果统计的是数字的有效位数，就必须把前导零区别对待，别把这一套无脑搬过去。

4.3 例题三：不仅不能相邻重复位，也不能出现连续“13”

这道题把两个业务约束叠在一起，更能体现模板的价值。dp 数组需要开成dp[20][11]，因为要记住上一位数字，空状态仍然用 10 表示。判断修改成这样：

if (i == pre) continue; if (pre == 1 && i == 3) continue;

其他部分和 3.1 的模板完全一致。pre 为 10 时，第二个条件里的 pre == 1 不成立，所以前导零填的数字不会被误判为“13”的开头。到这里你应该看出来了，模板本身没有神奇之处，真正需要动脑筋的是：状态里需要维护哪些信息、哪些分支要剪掉。剪枝规则越多，代码也几乎不会膨胀。

如果题目卡得很紧，还可以把 pre 状态压缩。因为“不允许 13”只关心上一位是不是 1，把 pre 从 0~9 压成 0/1/空三个状态，判断时如果当前填了 1，则下一位的 pre 变成 1，否则是 0。状态压缩能减小 dp 数组规模，必要时值得用，但初学者第一版还是写完整 pre 最稳。

5. 模板扩展：进制、大数与多语言迁移

5.1 从十进制扩展到任意进制

数位DP并不限定十进制。把模板里所有% 10和x /= 10，以及枚举上限 9，都替换成目标进制 base，就是 K 进制版本。此时 num[pos] 存储的是每一位在 0~base-1 之间的值，pre 的空状态可以设为 base 而不是 10。二进制下的数位DP也常见，比如统计区间内二进制表示中不含连续1的个数，状态只有 0、1 和空状态，比十进制更简单。K 进制下要注意的是，进制一旦变大，比如十六进制，数字位上可能超过 9，通常直接用整数数组存，不要用字符处理，否则容易混。

5.2 大数端点：超过 long long 怎么办

如果 L、R 可能超过 long long，模板的 solve 函数就不能接受整型参数了。常见解决方案是用字符串读入，然后从字符串末尾往前逐位填进 num 数组。比如读入字符串 s，数字的最低位是 s[s.size()-1]，于是：

int len = s.size(); for (int i = 0; i < len; i++) num[i] = s[len - 1 - i] - '0';

区间减法还是原来的思路，只不过求 solve(L-1) 时必须实现字符串减一的函数。这也是一道小模拟题，从末尾开始，如果当前位不是 0 就直接减一，否则向前借位。注意字符串版本的数字没有 len == 0 的边界，因为空串不会作为输入，但减到负数时记得返回空统计 0。

5.3 语言迁移：Python 和 Java 怎么写

如果用 Python，记忆化可以直接用标准库缓存。把 dfs 写成嵌套函数，参数里 limit 和 lead 作为传入参数，但要小心缓存键导致状态膨胀；可以把 limit 和 lead 也设为参数，这样缓存会包含完整状态，但上限 X 不同时缓存也应该清掉，否则会串味。更稳妥的写法是用functools.lru_cache(None)，但每次 solve 前要清空dfs.cache_clear()。不过 Python 的递归深度上限默认只有 1000，而数位最多不过 20 位，完全够用。

Java 则用 long 数组外加一个 visited 标记，或者像 C++ 一样初始化成 -1。多语言迁移的难点不在语法，而在“状态必须可靠表达并且不串味”，所以基本结构别乱改。

6. 常见问题与调试技巧速查表

6.1 为什么 dp 数组要初始化为 -1，而不是 0

如果 dp[pos][state] 初始为 -1，那么 -1 表示“还没算过”；如果算出来的结果恰好是 0，也能正常保存。如果初始化为 0，就分不清“没算过”和“算出来是 0”，程序会少算很多分支。这几乎是所有新手都会踩的坑。

另一个相关的坑是 memset 的位置。模板在每次 solve 前都 memset 一次，是最安全的选择；如果题目多次调用 solve 且 X 各不相同，虽然理论上 limit=false 时缓存可以复用部分状态，但复用的前提是 num 数组不影响这些状态，很多新手判断不清楚，干脆每次都清，性能损失微乎其微。二十位以内的数字，dp 数组通常只有几千个格子，清一次的成本完全可以忽略。

6.2 几个经典 bug 的速查表

这个表里的问题，我在早期实现里全部踩过，逐条记录比背代码更有效。

6.3 调试模板时最有用的习惯

遇到一个不会写的数位DP题，不要急着套大模板。先把 R 改成 99、999 这种小数，手写枚举一下期望结果。例如统计 [0, 99] 内不含连续相同数字的数字个数，可以按两位、一位、零位分别数，很快能得到一个数。然后用程序跑出同样的结果，如果对不上，就在 dfs 里打印 pos、pre、limit、lead 和 ans，逐一核对。递归层数最多 20 层，打印不会很乱。我用这个办法救回过无数个状态维度改错的小问题。

另外一个习惯是：写模板时把业务约束和 DFS 框架分开。DFS 负责枚举和前导零/limit，业务约束只在循环里的 if continue 或终止条件处出现。这样后续换题，只需要改这些“业务点”。这也是为什么我一直建议保留一套像 3.1 那样的骨架，而不是每次从零写。

我个人实际操作中的体会是：数位DP模板更像一把可调节的瑞士军刀，而不是一把固定形状的扳手。状态怎么定、哪几个参数要留、哪几个可以删，完全取决于题目约束的局部性。与其硬背一份带一堆看着高级参数的模板，不如把“pos、limit、lead、业务状态”这四件事的职责分开，再遇到任何变种题，都先问自己三个问题：范围多大、条件能不能按位判断、答案是不是前缀相减。想清楚这三件事，模板自然就能在你手里改得又快又稳。