本教程详细介绍了如何使用数位动态规划（Digit DP）算法，高效地统计在给定范围 [1, n] 内，其各位数字之和小于或等于 x 的整数数量。针对 n 值可达 10^12 的大规模场景，传统遍历方法效率低下，数位DP通过递归分解与记忆化搜索，将问题转化为子问题求解，显著提升了计算性能。文章通过具体示例和Python代码，深入剖析了算法原理、实现细节及注意事项。
我们需要设计一个算法，用于统计在整数范围 [1, n] 内，有多少个整数 i 满足其各位数字之和（digit_sum(i)）小于或等于一个给定的值 x。其中，n 的值可能非常大，例如高达 10^12。
传统的暴力迭代方法，即遍历 1 到 n 的每一个数，计算其数位和并进行判断，对于 n 较大的情况（如 10^12）是不可行的，因为它会导致巨大的时间开销。例如，以下Python代码虽然逻辑正确，但效率极低：
def digitsums_lower_than_x_naive(x, n):
"""
暴力方法：计算1到n中数位和小于等于x的数字数量。
对于大n值效率低下。
"""
digit_sum = lambda y: sum(int(digit) for digit in str(y))
count = 0
for i in range(1, n + 1):
if digit_sum(i) <= x:
count += 1
return count为了解决这一效率瓶颈，我们需要一种更优的算法，通常这类问题可以通过数位动态规划（Digit DP）来解决。
数位DP是一种用于解决统计在某个区间 [A, B] 内满足特定条件的数字个数的问题。这类问题通常可以转化为计算 f(B) - f(A-1)，其中 f(N) 表示在 [0, N] 范围内满足条件的数字个数。
对于本问题，我们定义一个函数 DS(limit_str, max_digit_sum)，它表示在 [0, int(limit_str)] 范围内，所有数字的数位和小于或等于 max_digit_sum 的数字个数。limit_str 是上限数字的字符串表示，max_digit_sum 是允许的最大数位和。
核心思想： 我们将 limit_str 从最高位开始分解。对于当前正在考虑的位，我们可以选择一个数字 d。这个选择会影响后续位的可选范围以及剩余的数位和预算。
考虑 DS(limit_str, max_digit_sum)： 设 limit_str 的最高位数字为 D，其长度为 L。
处理位数小于 L 的数字： 如果 limit_str 允许的最高位是 D，那么我们可以考虑所有长度小于 L 的数字。这些数字的最高位可以是 0 到 9，且没有 limit_str 的限制。这类情况通常在递归的内部通过对 99...9 形式的数字进行计算来覆盖。
处理位数等于 L 的数字： 对于与 limit_str 长度相同的数字，我们从最高位开始构建。
记忆化搜索（Memoization）： 为了避免重复计算相同的子问题，我们需要使用一个缓存（字典或数组）来存储 (limit_str, max_digit_sum) 组合的计算结果。
我们以计算 DS(112, 5) 为例（即在 [0, 112] 范围内，数位和小于等于 5 的数字数量）。
DS(112, 5) 的 limit_str 是 "112"，max_digit_sum 是 5。 最高位 D 是 1。
我们可以选择的最高位 d 可以是 0 或 1（因为 d 不能超过 D，也不能超过 max_digit_sum）。
当最高位 d = 0 时： 这表示我们正在构建 0xx 形式的数字。由于 0 < D，后续两位 xx 可以是 00 到 99 中的任意组合。 问题转化为 DS("99", 5 - 0)，即 DS("99", 5)。 DS("99", 5) 统计的是 [0, 99] 范围内数位和小于等于 5 的数字。
当最高位 d = 1 时： 这表示我们正在构建 1xx 形式的数字。由于 1 = D，后续两位 xx 必须受到 112 剩余部分 "12" 的限制。 问题转化为 DS("12", 5 - 1)，即 DS("12", 4)。 DS("12", 4) 统计的是 [0, 12] 范围内数位和小于等于 4 的数字。
所以，DS(112, 5) = DS("99", 5) + DS("12", 4)。
接下来，我们继续分解这些子问题：
分解 DS("99", 5)：limit_str 是 "99"，max_digit_sum 是 5。最高位 D 是 9。 最高位 d 可以是 0, 1, 2, 3, 4, 5 (因为 d <= D 且 d <= max_digit_sum)。
DS("9", k) 统计的是 [0, 9] 范围内数位和小于等于 k 的数字。对于单个数位，数位和就是它本身。 DS("9", 5) 统计 0, 1, 2, 3, 4, 5 (共6个)。 DS("9", 4) 统计 0, 1, 2, 3, 4 (共5个)。 ... DS("9", 0) 统计 0 (共1个)。
所以，DS("99", 5) = 6 + 5 + 4 + 3 + 2 + 1 = 21。
分解 DS("12", 4)：limit_str 是 "12"，max_digit_sum 是 4。最高位 D 是 1。 最高位 d 可以是 0, 1 (因为 d <= D 且 d <= max_digit_sum)。
我们已经知道 DS("9", 4) = 5。 DS("2", 3) 统计的是 [0, 2] 范围内数位和小于等于 3 的数字。这些数字是 0, 1, 2 (共3个)。
所以，DS("12", 4) = 5 + 3 = 8。
最终结果：DS(112, 5) = 21 + 8 = 29。
下面是基于上述原理的Python实现。D 函数是核心的递归函数，DS 函数是入口，负责将 n 转换为字符串并初始化缓存。
def D(limit_str: str, max_digit_sum: int, cache: dict) -> int:
"""
递归函数，计算在 [0, int(limit_str)] 范围内，数位和小于等于 max_digit_sum 的数字数量。
参数:
limit_str (str): 当前处理的数字上限的字符串表示。
max_digit_sum (int): 允许的最大数位和。
cache (dict): 记忆化搜索的缓存，存储 (limit_str, max_digit_sum) -> 结果。
返回:
int: 满足条件的数字数量。
"""
# 基础情况：如果 limit_str 只有一个数字
if len(limit_str) == 1:
# 统计从 0 到 min(max_digit_sum, int(limit_str[0])) 的所有数字
# 例如，DS("5", 3) -> 0, 1, 2, 3 (共4个)
# DS("2", 5) -> 0, 1, 2 (共3个)
return min(max_digit_sum, int(limit_str[0])) + 1
# 检查缓存，避免重复计算
if (limit_str, max_digit_sum) in cache:
return cache[(limit_str, max_digit_sum)]
top_digit = int(limit_str[0]) # 当前最高位数字
remaining_digits_str = limit_str[1:] # limit_str的剩余部分
nines_str = '9' * (len(limit_str) - 1) # 由9组成的同长度字符串，用于表示无上限限制的后续位
current_count = 0
# 遍历当前位可以选择的数字 d
# d 的范围是 0 到 min(max_digit_sum, top_digit)
for d in range(min(max_digit_sum, top_digit) + 1):
if d < top_digit:
# 如果当前位 d 小于 top_digit，则后续位可以取 0 到 9，
# 相当于后续位构成的数字上限是 '99...9' (nines_str)
current_count += D(nines_str, max_digit_sum - d, cache)
else: # d == top_digit
# 如果当前位 d 等于 top_digit，则后续位必须受到 remaining_digits_str 的限制
current_count += D(remaining_digits_str, max_digit_sum - d, cache)
# 将结果存入缓存
cache[(limit_str, max_digit_sum)] = current_count
return current_count
def count_numbers_with_digit_sum_le_x(n: int, x: int) -> int:
"""
计算在 [0, n] 范围内，数位和小于等于 x 的数字数量。
参数:
n (int): 范围上限。
x (int): 允许的最大数位和。
返回:
int: 满足条件的数字数量。
"""
# 如果 n 或 x 为负数，或 x 为0但n小于0，则无意义或结果为0
if n < 0 or x < 0:
return 0
# 0的数位和是0，如果x>=0，则0总是被计数
# 如果 n=0，且 x>=0，则只有0满足，返回1
if n == 0:
return 1 if x >= 0 else 0
return D(str(n), x, {})
# 示例用法
print(f"DS(112, 5) = {count_numbers_with_digit_sum_le_x(112, 5)}") # 预期输出 29
# 如果问题要求的是 [1, n] 的范围，则需要减去 0 的计数（如果 0 被计数且满足条件）
# 0 的数位和是 0。如果 x >= 0，0 总是满足条件。
# 那么对于 [1, n] 范围，结果是 count_numbers_with_digit_sum_le_x(n, x) - 1
print(f"在 [1, 112] 范围内，数位和小于等于 5 的数字数量为: {count_numbers_with_digit_sum_le_x(112, 5) - 1}") # 预期输出 28数位动态规划是解决这类涉及数字范围和数位属性计数问题的强大工具。通过将大问题分解为结构相似的子问题，并利用记忆化搜索避免重复计算，它
以上就是使用数位DP高效计算指定范围内数位和小于等于X的整数数量的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
广告Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
714
收藏
