数据结构与算法 / 系统课时
处理前导零与上界限制状态
处理前导零与上界限制状态
数位 DP 中最容易产生隐蔽错误的两个状态是 started 和 tight:前者决定高位补出的零是不是实际数字,后者决定当前位置能否自由取值。把这两个状态的转换规则理清后,包含数字、相邻关系等统计才能得到正确区间答案。
学习目标
- 判断什么时候必须使用
started区分前导零 - 正确维护
tight,避免构造出超过上界的整数 - 使用前缀计数相减统计任意闭区间
前导零不一定是真正的数字零
数位 DP 通常把所有候选数补成和上界相同的长度。例如上界是 500 时,整数 7 在搜索过程中可以表现为 007。这两个高位的零只是为了对齐数位,并不属于整数 7 的十进制表示。
如果问题只是统计数位和,前导零没有影响;但如果问题要求“包含至少一个数字 0”,把 007 的前导零也计入,就会错误地认为 7 包含数字 0。这时必须增加 started:它表示此前是否已经选择过第一个非零数字。
当 started 为假且当前仍选择 0 时,这一位继续属于前导零,不更新“出现过 0”之类的历史状态;一旦选择非零数字,started 变为真,此后的 0 才是整数表示中的真实数位。

tight 约束的是整个前缀
tight 不能理解成“当前这一位是否等于某个数字”,它描述的是已经构造出的整个前缀是否仍与上界前缀相等。
假设上界为 527。第一位选择 5 后仍然贴住上界,第二位最多只能选 2;如果第一位改选 4,那么构造出的任何三位后缀都不可能让结果超过 527,因此后续位置都可以自由选择 0 到 9。
转换规则可以浓缩为一个表达式:next_tight = tight and digit == digits[pos]。只有旧状态仍受上界限制,并且当前位置继续选择上界对应数字时,新状态才保持 tight。
started 与 tight 是相互独立的维度。以 500 为上界时,第一位选择前导零会令 started 保持假,同时因为 0 小于上界首位 5,tight 已经变为假。后续仍要分别按照两个状态的规则处理。
用前缀计数得到任意区间
设 F(N) 表示 [1, N] 中满足条件的正整数数量。闭区间 [L, R] 的答案仍然是:
这种写法把左右边界统一成同一个“统计不超过 N 的数”函数,避免同时维护下界约束和上界约束。对于 L = 1,只需让 F(0) 返回 0 即可。
如果搜索允许所有位置都选择前导零,那么最终会得到一个“从未开始”的路径,它代表数字 0。题目只统计正整数时,应在递归结束处要求 started 为真,而不是把这条路径误计入答案。
完整实现与验证
下面统计正整数中“十进制表示至少包含一个 0”的数量。has_zero 只在真正开始构造数字后更新,因此前导零不会污染结果。
from functools import lru_cache
def count_leq(n: int) -> int:
if n <= 0:
return 0
digits = tuple(map(int, str(n)))
@lru_cache(maxsize=None)
def dfs(pos: int, started: bool, has_zero: bool, tight: bool) -> int:
if pos == len(digits):
# 排除所有位置都是前导零的路径,也就是整数 0。
return int(started and has_zero)
upper = digits[pos] if tight else 9
total = 0
for digit in range(upper + 1):
next_tight = tight and digit == digits[pos]
if not started and digit == 0:
# 这个 0 只是补位,不应被视为数字中出现了 0。
total += dfs(pos + 1, False, False, next_tight)
else:
total += dfs(
pos + 1,
True,
has_zero or digit == 0,
next_tight,
)
return total
return dfs(0, False, False, True)
def count_range(left: int, right: int) -> int:
if left > right:
raise ValueError('left must not exceed right')
return count_leq(right) - count_leq(left - 1)
if __name__ == '__main__':
print('1..500:', count_range(1, 500))
print('105..500:', count_range(105, 500))预期输出
1..500: 86
105..500: 72第一个结果不会把 1 到 9 当成 001 到 009,所以这些数字不会因为补位零而被错误统计。第二个结果直接由 F(500) - F(104) 得到,不需要重新设计区间搜索。
判断何时需要 started
只要统计规则会区分“尚未出现有效数位”和“已经进入整数本体”,就应考虑 started。典型情况包括统计数字 0 的出现次数、限制首位、判断相邻数位关系,以及匹配某段数位模式。
如果前导零与真实零对答案完全等价,例如只计算普通数位和,started 往往可以省略。tight 则几乎是有上界数位 DP 的基础状态:它保证搜索空间只覆盖不超过 N 的数。设计状态时分别回答“这个位置是否已经属于数字本体”和“这个前缀是否还贴着上界”,就能避免大多数前导零与边界错误。