数位DP按位枚举与区间数字统计

可视化演示

展示数位DP核心机制：整数按位分解、limit上界约束与分支剪枝、记忆化搜索缓存复用、差分转化区间计数。支持步进切换四种模式。

数位DP概述：像破译保险箱一样逐位破解

想象你是一个专门破解古董保险箱的锁匠。保险箱的密码不是一串能直接读出的数字，而是四个独立的转轮，每个转轮从 0 转到 9。现在委托人说道：密码一定在 0000 到 2024 之间，而且密码中不能出现数字 7，请数出一共有多少组合法密码。如果按常规思路，你会从 0000 开始一个个拧到 2024，两千多次尝试，虽然可行，但若上限变成 10^18，这种暴力试锁将耗尽你的余生。

数位DP的思路完全不同：把那个巨大的范围丢到一边，只盯着“第一位能放几”这个问题。拨动千位转轮，如果拨到 0 或 1，后面三位完全可以自由发挥；如果拨到 2，因为和上界的首位 2 贴死了，百位就只能在 0 到 0 之间选。就这样，一位一位地把限制传下去，同时把已经算过的“剩余几位 + 是否贴死”的结果记在小本本上。整个过程的计算量不再随数字大小线性增长，而只和“位数”与“状态数”有关。

这就是数位DP：对数字的每一位做动态规划。它解决的核心问题，是形如“统计区间 [L,R] 内满足某数位条件的数字个数”的计数题，特别适合那些区间极大、条件与数字十进制表示有关的场景。你不再需要把每个数字都生成出来，而是像拨保险箱轮盘一样，逐位枚举并累加可能性。

那么，第一位应该如何拆开？贴死与自由之间如何切换？小本本上又要记哪些东西？接下来的每一节，都把这套“保险箱破解术”的零件逐一拆给你看。

按位拆解：把密码锁拆成一排独立的转轮

保险箱虽然是一整串数字，但锁匠只关心每个转轮的位置。同样，数位DP的第一步，是给数字“拆位”。比如密码上界 2024，拆开后就是千位 2、百位 0、十位 2、个位 4。这样，一个整数就变成了一张“转轮清单”。

这个表达式叫位权展开：每一位数字乘以它的十进制位权，再把所有项加起来，就还原了原来的整数。拆位之后，枚举一个数就变成了依次决定每一个转轮的数字。由于我们总是从高位往低位拨，前面已经拨下的数字就构成了“前缀”。前缀和上界前缀完全相等时，当前位就要小心；前缀一旦比上界小，后面就可以随便拨。

从数学角度看，记第 k 位数字为 d_k，则一个 m 位数 n 可以写为：

拆位是所有数位DP代码的第一步。一旦把数字变成数组 digits，剩下的过程就像把保险箱的每一颗螺丝卸下来，无论是上界限制还是统计逻辑，都能在这个数组上按顺序执行。

2024 = 2 × 10³ + 0 × 10² + 2 × 10 + 4

状态定义：三个变量描述“我现在在哪”

当锁匠拨到第三个转轮时，心里需要知道三件事：还剩几个转轮要拨？目前的前缀是否和上界完全一样？之前已经拨出的数字里有没有出现过某个特殊数字？这三件事，正好对应数位DP的三个核心状态。

首先是位置 pos，它表示当前正在处理数字的哪一位，也可以理解为“还剩多少位可以自由决策”。其次是 tight，它是一个布尔值，表示到目前为止，我们选择的前缀是否与上界的前缀“贴死”了。如果贴死，当前位只能取到上界对应位；如果之前任何一位已经选得比上界小，tight 就变成 false，后面不再受限。最后是 mask，它是一个位掩码，用于记录已经出现过的数字集合，通常在处理“每个数字最多出现一次”这类题目时使用。

这三个状态组合起来，就构成了一个子问题的完整描述：

状态定义是整个数位DP的地基。如果你能说出“此刻我在第几位、受不受上界限制、之前满足什么性质”，那么你已经把一个复杂的计数问题，拆分成了许多个可以独立求解的小问题。

约束处理：贴死时不能越线，前导零不能算数

继续用保险箱的例子：如果前两位已经拨成了 20，恰好和上界 2024 的前两位一致，那么第三位转轮只能在 0 到 2 之间转；如果拨成 19，第三位就可以从 0 转到 9。这就是 tight 带来的上界约束。翻译成代码就是：如果当前处于贴死状态，当前位的枚举上界不是 9，而是上界在这一位的数字。

另一类约束来自“前导零”。在数字 007 中，前两位的 0 只是占位符，它们不应该被当作真正的数字参与统计。比如统计“数字 0 出现了多少次”时，007 这个数只能贡献一次 0（在个位），而不能因为十进制表示有两位 0 就贡献两次。因此，我们通常还要维护一个 started（是否已经开始）状态：只有已经出现了非零位，之后的 0 才算作有效数字；否则 0 只是前导零，不能计入统计。

这两个约束看似繁琐，却正是数位DP能够在超大区间上精确计数的关键。限上界，保证我们统计的每个数字都不越界；处理前导零，保证计数规则和十进制表示的真实含义一致。如果把这两个约束写进状态，任何子问题都能正确地被描述。

记忆化搜索：小本本让破解速度起飞

锁匠拨锁时很快发现：无论千位拨成 0 还是 1，只要后面的状态相同——都是“还剩三位、tight=false、没有特殊数字记录”，那后续所有分支的方案数其实完全一样。既然如此，为什么不把第一次算出的结果记在小本本上，后面直接抄答案？

这就是记忆化搜索。我们用递归函数 dfs(pos, tight, mask, started) 表示从当前状态出发的合法方案数。函数内部枚举当前位所有可选数字，并递归求解下一层；当一个状态第一次算完，就把结果存入缓存数组，下次遇到相同状态直接返回。这样，原本可能在搜索树里爆炸的计算量，被压缩到状态数的规模。

数位DP的复杂度因此变得非常优雅：假设数字有 L 位，状态中可能记录的数字集合有 2^m 种，每个状态要枚举 10 个数字，总时间复杂度大约是：

写记忆化搜索时有个小技巧：当 tight=false 时，子问题的答案和上界无关，所以可以放心缓存；而 tight=true 的分支沿着上界的路径一路走下来，路径数很少，缓存收益不大。把缓存数组开成 dp[pos][tight][mask] 的维度，就能轻松实现秒出答案。

区间差分：要一段区间，先算两个前缀

委托人真正想统计的是 [L,R] 之间的合法数字数量，但数位DP最顺手的对象却是形如 [0,n] 的前缀区间。原因是 [0,n] 天然带一个明确的上界 n，让拆位枚举有了一个“最高限制”；而任意 [L,R] 有两个边界，会让状态图立刻复杂起来。那怎么办？用减法。

假设我们已经有一个函数 F(n)，能算出从 0 到 n 有多少个合法数字。那么区间 [L,R] 的答案就是 [0,R] 的答案减去 [0,L-1] 的答案。这就像想知道书架上从第 L 本到第 R 本之间有多少本书，先数从开头到第 R 本，再减去从开头到第 L-1 本，剩下的正好是目标区间。

差分思想几乎是所有区间统计题的通用套路。它把“区间”这个二维的困难问题，转化成两个“前缀”一维的简单问题。在数位DP中尤其重要，因为你只需要把一个“上界如何限制状态”的逻辑写好，然后调用两次、做一次减法，就拿到了任意区间的答案。

经典应用：从数字计数到数位性质统计

数位DP的价值不在于它本身花哨，而在于它像一把万能钥匙，能打开一大批看似不同、实则同构的数字统计问题。最常见的应用是统计区间内某个数字的出现次数。比如“0 到 2024 中数字 7 一共出现多少次”，你可以把每一位单独拿出来看：千位是 7 的数有多少个？百位是 7 的数有多少个？……每个位独立统计后相加，正是按位枚举的天然优势。

第二类应用是“不含特定数字”的计数。比如文章开头的不含 7 的密码数，状态里只要有一层限制，当前位枚举时跳过被禁止的数字即可。第三类是更复杂的数位性质数：每个数字的数位和满足某个模数、数字从左到右递增、或者每个数字最多出现一次（需要 mask 状态）。这些条件五花八门，但都能通过扩展状态和转移规则，嵌入到同一个递归框架里。

在实际工作中，这类问题经常以“数据校验”的面孔出现。例如在一批 ID 中统计不包含数字 4 的 ID 数量，在订单号段中统计可用的优惠码个数。只要条件的定义落在“数位”这个粒度上，数位DP几乎总能给出比逐条扫描高效得多的解法。它不关心数字本身的业务含义，只关心十进制表示的形状，这正是它强大的地方。

实现技巧：让破解流程更稳更快

最后，我们把整个保险箱破解流程整理成一套可落地的操作指南。第一步，将整数 n 按十进制拆位，得到从高位到低位的 digits 数组。这一步看似简单，但要记住：若 n 是 0，数组是 [0] 而不是空数组；拆位顺序务必从最高位开始，因为状态转移依赖于“前缀与上界比较”的方向。

第二步，写递归函数 dfs(pos, tight, started, ……)，在函数开头判断是否已经遍历完所有位，是则返回 1 或 0；然后根据 tight 计算 limit，枚举当前位。第三步，使用记忆化：当 tight=false 时，把结果存入缓存；这样同一个“自由状态”只需计算一次。实现时可以用一个多维数组，也可以用一个以 (pos, tight, mask) 为键的哈希表。

调试时有一个屡试不爽的方法：先写一个暴力函数检查小范围（比如 0 到 10000）的结果，再与数位DP的结果对比。如果小范围都对，再放开到大范围。边界情况尤其要测试 L=0、R=0、R 极大、n=10^k 这类值。只要把边界剪好、缓存键设计对，数位DP就能成为你处理数字区间统计问题的一把锋利刮刀。

AI 应用场景

Python 演示

class DigitDP:    def __init__(self, n, forbidden=None):        self.digits = []        self.forbidden = forbidden if forbidden else set()        n = max(n, 0)        if n == 0:            self.digits = [0]        else:            while n:                self.digits.append(n % 10)                n //= 10            self.digits.reverse()        self.L = len(self.digits)        self.memo = {}     def count_not_contain(self):        return self._dfs_not(0, True, False)     def _dfs_not(self, pos, tight, started):        if pos == self.L:            return 1 if started else 0        key = (pos, tight, started)        if key in self.memo:            return self.memo[key]        limit = self.digits[pos] if tight else 9        res = 0        for d in range(limit + 1):            if d in self.forbidden:                continue            res += self._dfs_not(pos + 1,                                 tight and (d == limit),                                 started or d != 0)        if not tight:            self.memo[key] = res        return res  def main():    L, R = 1, 2024    dp = DigitDP(R, forbidden={7})    total_R = dp.count_not_contain()    dp2 = DigitDP(L - 1, forbidden={7})    total_L = dp2.count_not_contain()    ans = total_R - total_L    print("区间 [1, 2024] 内不含数字 7 的整数个数:", ans)  if __name__ == "__main__":    main()

1. self.digits.append(n % 10)逐次取下一位数字，完成拆位；最后 reverse() 让它从高位到低位排列。
2. self.L = len(self.digits)位数 L 是 DFS 的终止条件，也是状态空间的长度。
3. _dfs_not(pos, tight, started)递归函数，返回从当前状态出发的合法方案数。
4. limit = self.digits[pos] if tight else 9这就是 tight 约束的代码化身：贴死时取上界位，否则放开到 9。
5. started or d != 0处理前导零：只有出现非零位后，之后的 0 才是有效数字。
6. if not tight: self.memo[key] = res只有不受上界限制的分支才缓存，因为 tight 分支沿上界路径走，复用价值低。
7. total_R - total_L区间差分的落地：两个前缀相减得到目标区间答案。

常见误区

面试题