本教程详细介绍了如何使用数位动态规划（Digit DP）算法，高效地统计在给定范围 [1, n] 内，其各位数字之和小于或等于 x 的整数数量。针对 n 值可达 10^12 的大规模场景，传统遍历方法效率低下，数位DP通过递归分解与记忆化搜索，将问题转化为子问题求解，显著提升了计算性能。文章通过具体示例和Python代码，深入剖析了算法原理、实现细节及注意事项。
1. 问题背景与挑战
我们需要设计一个算法，用于统计在整数范围 [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）来解决。
2. 数位动态规划（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 长度相同的数字，我们从最高位开始构建。
- 当前位选择的数字 d 小于 D： 如果当前位选择的数字 d
- 当前位选择的数字 d 等于 D： 如果当前位选择的数字 d = D，那么后续的 L-1 位必须受到 limit_str 剩余部分的限制。我们递归调用 DS(limit_str[1:], max_digit_sum - d)。
记忆化搜索（Memoization）： 为了避免重复计算相同的子问题，我们需要使用一个缓存（字典或数组）来存储 (limit_str, max_digit_sum) 组合的计算结果。
3. 算法示例与推导
我们以计算 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 = 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 = 0: DS("9", 5-0) = DS("9", 5)
- d = 1: DS("9", 5-1) = DS("9", 4)
- d = 2: DS("9", 5-2) = DS("9", 3)
- d = 3: DS("9", 5-3) = DS("9", 2)
- d = 4: DS("9", 5-4) = DS("9", 1)
- d = 5: DS("9", 5-5) = DS("9", 0)
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 = 0: DS("9", 4-0) = DS("9", 4) (因为 0
- d = 1: DS("2", 4-1) = DS("2", 3) (因为 1 = D，后续位受 "2" 限制)
我们已经知道 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。
4. Python 代码实现
下面是基于上述原理的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}") # 预期输出 285. 注意事项与复杂度分析
- 范围定义： 上述 count_numbers_with_digit_sum_le_x(n, x) 函数计算的是在 [0, n] 范围内满足条件的数字数量。如果原始问题严格要求在 [1, n] 范围内，那么需要从结果中减去 1（因为 0 的数位和是 0，如果 x >= 0，0 总是会被计数）。
- 数位和预算： max_digit_sum 在递归过程中会逐渐减小。如果 max_digit_sum 变为负数，意味着不可能再找到满足条件的数字，此时应返回 0。在我们的实现中，min(max_digit_sum, int(limit_str[0])) 已经隐式处理了这种情况，如果 max_digit_sum 为负，min 的结果也会是负，range 会是空，从而返回 0。
- 大数处理： 由于 n 可以高达 10^12，直接使用整数进行位操作可能不方便。将 n 转换为字符串进行处理是数位DP的常见做法，这使得按位分解变得容易。
- 时间复杂度： 递归函数 D 的状态由 (limit_str, max_digit_sum) 决定。limit_str 的长度最多是 log10(N) (对于 10^12 是 13)。max_digit_sum 的最大值是 9 * log10(N) (对于 10^12 是 9 * 12 = 108)。因此，状态空间的大小约为 log(N) * (9 * log(N))。每个状态的计算涉及最多 10 次递归调用。所以，总的时间复杂度大致为 O(log(N) * log(N) * 10)，即 O((log N)^2)，这对于 N = 10^12 是非常高效的。
- Python递归深度： 对于非常大的 n (例如 10^100 级别)，limit_str 会很长，可能导致Python的默认递归深度限制。但对于 10^12 (长度13)，这通常不是问题。
6. 总结
数位动态规划是解决这类涉及数字范围和数位属性计数问题的强大工具。通过将大问题分解为结构相似的子问题，并利用记忆化搜索避免重复计算，它
