利用数位DP高效计算指定范围内数位和小于等于X的整数数量

def digitsums_lower_than_x_naive(x_limit, n_upper_bound):
    """
    计算 [1, n_upper_bound] 范围内数位和小于等于 x_limit 的数字数量。
    此方法对于大 n_upper_bound 效率低下。
    """
    digit_sum_func = lambda y: sum(int(digit) for digit in str(y))
    count = 0
    for i in range(1, n_upper_bound + 1):
        if digit_sum_func(i) <= x_limit:
            count += 1
    return count

def count_with_digit_sum_limit(upper_bound_str, sum_limit, cache):
    """
    递归函数，计算小于或等于 upper_bound_str 且数位和小于等于 sum_limit 的数字数量。

    参数:
    upper_bound_str (str): 当前处理的上限数字的字符串表示。
    sum_limit (int): 允许的剩余数位和上限。
    cache (dict): 记忆化搜索的缓存，存储 (upper_bound_str, sum_limit) -> 结果。

    返回:
    int: 符合条件的数字数量。
    """

    # 基本情况：如果 sum_limit 小于 0，说明已经超出了允许的数位和，返回 0。
    if sum_limit < 0:
        return 0

    # 基本情况：如果只剩一位数字
    if len(upper_bound_str) == 1:
        # 这一位可以取 0 到 min(sum_limit, int(upper_bound_str[0]))
        # 例如，upper_bound_str='5', sum_limit=3, 那么可以取0,1,2,3 (4个)
        # 例如，upper_bound_str='2', sum_limit=5, 那么可以取0,1,2 (3个)
        return min(sum_limit, int(upper_bound_str[0])) + 1

    # 检查缓存，避免重复计算
    state = (upper_bound_str, sum_limit)
    if state in cache:
        return cache[state]

    # 获取当前最高位数字
    top_digit = int(upper_bound_str[0])
    # 构造一个由 '9' 组成的字符串，长度比当前数字少一位，用于表示“无上限”的子问题
    nines_suffix = '9' * (len(upper_bound_str) - 1)

    current_count = 0
    # 遍历当前位可能取的值 d
    # d 从 0 开始，直到 min(sum_limit, top_digit)
    for d in range(min(sum_limit, top_digit) + 1):
        if d < top_digit:
            # 如果当前位 d 小于 top_digit，则后续位可以取 0-9，不受 upper_bound_str 限制
            # 递归调用，处理由 '9' 组成的后缀，剩余数位和为 sum_limit - d
            current_count += count_with_digit_sum_limit(nines_suffix, sum_limit - d, cache)
        else: # d == top_digit
            # 如果当前位 d 等于 top_digit，则后续位仍受 upper_bound_str 的剩余部分限制
            # 递归调用，处理 upper_bound_str 的剩余部分，剩余数位和为 sum_limit - d
            current_count += count_with_digit_sum_limit(upper_bound_str[1:], sum_limit - d, cache)

    # 将结果存入缓存
    cache[state] = current_count
    return current_count

def calculate_digit_sum_count(n_upper_bound, x_limit):
    """
    主函数，计算 [0, n_upper_bound] 范围内数位和小于等于 x_limit 的数字数量。

    参数:
    n_upper_bound (int): 范围上限。
    x_limit (int): 允许的最大数位和。

    返回:
    int: 符合条件的数字数量。
    """
    # 将 n_upper_bound 转换为字符串以便按位处理
    n_str = str(n_upper_bound)
    # 初始化缓存
    cache = {}
    return count_with_digit_sum_limit(n_str, x_limit, cache)

# 示例调用
print(f"DS(112, 5) = {calculate_digit_sum_count(112, 5)}") # 预期输出 29
print(f"DS(9, 2) = {calculate_digit_sum_count(9, 2)}") # 预期输出 3 (0, 1, 2)
print(f"DS(19, 2) = {calculate_digit_sum_count(19, 2)}") # 预期输出 6 (0,1,2,10,11,12) -> 0(0),1(1),2(2),10(1),11(2),12(3) -> 0,1,2,10,11
                                                        # DS(9,2) + DS(9,1) = 3 + 2 = 5 (0-99) + DS(9,2) + DS(0,1)
                                                        # DS(9,2) = 3 (0,1,2)
                                                        # DS(9,1) = 2 (0,1)
                                                        # DS(19,2) = DS(9,2) + DS(9,1) = 3 + 2 = 5
                                                        # Let's re-verify DS(19,2) = DS(9,2) + DS(9,1)
                                                        # DS(19,2) = count_numbers('19', 2, cache)
                                                        # d=0: count_numbers('9', 2, cache) = 3 (0,1,2)
                                                        # d=1: count_numbers('9', 2-1=1, cache) = 2 (0,1) -> (10, 11)
                                                        # Total = 3 + 2 = 5. Correct for 0-19.