计算 [0,k] 范围内数字和等于 s 的整数个数

Question

计算

[0,k]

范围内的数字总和等于

s

的整数的个数。由于

k

可能是一个非常大的数，因此解不应该是

O(k)

。我尝试的

O(s log(k))

解决方案（

log(k)

与

k

中的位数成正比）：

我引入了一个新函数

cnt_sum

，它计算总和等于

n

的

s

位整数的数量。然而，由于前导零，似乎存在重复问题。这个问题有更简单的方法吗？

# pseudo code, without memoization and border case handling


# count number of integers with n digits whose sum of digits equals s
# leading zeros included
def cnt_sum(n:int,s:int):
    ans=0
    for i in range(0,9):
        ans+=cnt_sum(n-1,s-i)
    return 0

# suppose the number is 63069
def dp(loc:int, k:int, s:int):
    ans=0
    # Count the numbers starting with 6 and remaining digits less than k[1:](3069) who sum equals sum-k[0] (sum-6)
    ans+=dp(loc+1,k,s-k[loc])
    # For each number i in range [0,5], count all numbers with len(k)-loc digits whose sum equals sum-i
    # such as 59998, 49999
    for i in range(0,k[loc]):
        ans+=cnt_sum(len(k)-loc,s-i)
    return ans

def count(k:int,s:int):
    dp(0,k,s)

Answer 1

这是一个基于以下递归的简单 Python 解决方案：

T(k<0, s<0) = 0
T(0, 0) = 1
T(0, s>0) = 0 
T(k, s) = sum(T(k/10) for i in [0, k%10]) + sum(k/10-1) for i in [k%10+1, 9])

最后一个是最重要的，因为它编码了子问题之间的关系。以

T(12345, 20)

为例：

我们对这些案例感兴趣：

T(1234, 20) #xxxx0 (with xxxx <= 1234)
T(1234, 19) #xxxx1 (with xxxx <= 1234)
T(1234, 18) #xxxx2 (with xxxx <= 1234)
T(1234, 17) #xxxx3 (with xxxx <= 1234)
T(1234, 16) #xxxx4 (with xxxx <= 1234)
T(1234, 15) #xxxx5 (with xxxx <= 1234)
T(1233, 14) #yyyy6 (with yyyy <= 1233)
T(1233, 13) #yyyy7 (with yyyy <= 1233)
T(1233, 12) #yyyy8 (with yyyy <= 1233)
T(1233, 11) #yyyy9 (with yyyy <= 1233)

这是带有一些 Python 快捷方式的最终代码。

import functools

@functools.cache
def T(k, s):
    if k < 0 or s < 0: return 0
    if k == 0: return s == 0
    return sum(T(k//10-(i>k%10), s-i) for i in range(10))

print(T(12345, 25))