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

用数位状态统计区间答案

用数位状态统计区间答案

当区间上界大到无法逐个枚举整数时,可以把整数看成从高位到低位依次选择的数位序列,只记录会影响后续答案的状态。这样,原本与区间长度相关的遍历,就能压缩成与数位数量和状态规模相关的动态规划。

学习目标

  • 把整数区间计数改写为前缀计数问题
  • 使用当前位置、历史统计量和上界约束设计数位 DP 状态
  • 用记忆化搜索实现一个可运行的数位统计程序

从枚举整数改成构造数位

假设要统计区间 [1, 1000] 中十进制数位和等于 10 的整数。直接做法是枚举 1000 个数;如果右端点变成 101810^{18},逐数检查就不可行了。

数位 DP 不再询问“下一个整数是什么”,而是从最高位开始询问“当前位置可以填哪个数字”。对于上界 N,定义 F(N) 为 [0, N] 中满足条件的整数数量,那么任意闭区间都可以转化为:

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

因此核心问题只剩一个:怎样高效计算不超过某个上界的所有合法数位序列。

数位 DP 将按整数枚举压缩为按状态搜索

设计足够而不过量的状态

对于“数位和等于目标值”这个问题,一个子问题可以写成 dfs(pos, sum, tight)。

pos 表示当前处理到第几个数位;sum 是已经选择的数字之和;tight 表示此前选择的前缀是否仍与上界前缀完全相同。如果 tight 为真,当前位置最多只能取上界对应数位;一旦选择了更小的数字,后面的数位就可以自由取 0 到 9。

搜索到数位末尾时,只需判断累计和是否等于目标值。若 sum 已经超过目标值,也可以立即停止当前分支。不同路径只要到达相同的 (pos, sum, tight),其后续答案完全一致,因此可以直接复用记忆化结果。

这里没有加入 started 状态,因为前导零不会改变数位和。例如把 7 看成 007,数位和仍然是 7。状态是否需要记录,取决于它会不会改变未来的合法选择或最终统计结果。

用记忆化搜索计算区间答案

下面的程序统计闭区间内数位和等于指定值的整数数量。代码会先计算两个前缀答案,再做一次相减。

python
from functools import lru_cache


def count_leq(n: int, target: int) -> int:
    if n < 0:
        return 0

    digits = tuple(map(int, str(n)))

    @lru_cache(maxsize=None)
    def dfs(pos: int, digit_sum: int, tight: bool) -> int:
        if digit_sum > target:
            return 0
        if pos == len(digits):
            return int(digit_sum == target)

        upper = digits[pos] if tight else 9
        total = 0
        for digit in range(upper + 1):
            # 只有此前贴住上界且本位继续取上界数字,下一位才仍受限制。
            next_tight = tight and digit == digits[pos]
            total += dfs(pos + 1, digit_sum + digit, next_tight)
        return total

    return dfs(0, 0, True)


def count_range(left: int, right: int, target: int) -> int:
    if left > right:
        raise ValueError('left must not exceed right')
    return count_leq(right, target) - count_leq(left - 1, target)


if __name__ == '__main__':
    print(count_range(1, 1000, 10))

预期输出

text
63

结果 63 来自所有不超过 1000 且数位和为 10 的整数。程序没有生成这些整数本身,而是直接累加每个状态能够形成的合法后缀数量。

看懂复杂度和适用边界

设十进制上界有 D 位,目标数位和为 T。状态数量最多约为 D × (T + 1) × 2,每个状态尝试至多 10 个数字,因此时间复杂度可写成 O(DT×10)O(DT\times10),空间复杂度主要由记忆化状态决定。它与 [L, R] 实际包含多少个整数没有直接关系。

如果统计条件还依赖“是否已经出现某个数字”“前一个数字是什么”“出现次数是多少”,就把这些真正影响后续决策的信息加入状态。反过来,不影响未来的完整前缀内容不应保存,否则状态会重新膨胀成近似枚举。数位 DP 的关键不是固定背诵状态模板,而是证明:具有相同状态的所有前缀,从当前位置开始拥有完全相同的后续计数。

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

目录与阅读设置

阅读设置

17

记录一个想法

用数位状态统计区间答案

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

登录哪都通