数据结构与算法 / 系统课时

处理前导零与上界限制状态

处理前导零与上界限制状态

数位 DP 中最容易产生隐蔽错误的两个状态是 started 和 tight:前者决定高位补出的零是不是实际数字,后者决定当前位置能否自由取值。把这两个状态的转换规则理清后,包含数字、相邻关系等统计才能得到正确区间答案。

学习目标

  • 判断什么时候必须使用 started 区分前导零
  • 正确维护 tight,避免构造出超过上界的整数
  • 使用前缀计数相减统计任意闭区间

前导零不一定是真正的数字零

数位 DP 通常把所有候选数补成和上界相同的长度。例如上界是 500 时,整数 7 在搜索过程中可以表现为 007。这两个高位的零只是为了对齐数位,并不属于整数 7 的十进制表示。

如果问题只是统计数位和,前导零没有影响;但如果问题要求“包含至少一个数字 0”,把 007 的前导零也计入,就会错误地认为 7 包含数字 0。这时必须增加 started:它表示此前是否已经选择过第一个非零数字。

当 started 为假且当前仍选择 0 时,这一位继续属于前导零,不更新“出现过 0”之类的历史状态;一旦选择非零数字,started 变为真,此后的 0 才是整数表示中的真实数位。

started 与 tight 的数位状态转换

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] 的答案仍然是:

F(R)−F(L−1)F(R)-F(L-1)

这种写法把左右边界统一成同一个“统计不超过 N 的数”函数,避免同时维护下界约束和上界约束。对于 L = 1,只需让 F(0) 返回 0 即可。

如果搜索允许所有位置都选择前导零,那么最终会得到一个“从未开始”的路径,它代表数字 0。题目只统计正整数时,应在递归结束处要求 started 为真,而不是把这条路径误计入答案。

完整实现与验证

下面统计正整数中“十进制表示至少包含一个 0”的数量。has_zero 只在真正开始构造数字后更新,因此前导零不会污染结果。

python
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))

预期输出

text
1..500: 86
105..500: 72

第一个结果不会把 1 到 9 当成 001 到 009,所以这些数字不会因为补位零而被错误统计。第二个结果直接由 F(500) - F(104) 得到,不需要重新设计区间搜索。

判断何时需要 started

只要统计规则会区分“尚未出现有效数位”和“已经进入整数本体”,就应考虑 started。典型情况包括统计数字 0 的出现次数、限制首位、判断相邻数位关系,以及匹配某段数位模式。

如果前导零与真实零对答案完全等价,例如只计算普通数位和,started 往往可以省略。tight 则几乎是有上界数位 DP 的基础状态:它保证搜索空间只覆盖不超过 N 的数。设计状态时分别回答“这个位置是否已经属于数字本体”和“这个前缀是否还贴着上界”,就能避免大多数前导零与边界错误。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

处理前导零与上界限制状态

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通