Подсчитайте количество целых чисел в диапазоне [0,k], сумма цифр которых равна s
Подсчитайте количество целых чисел в диапазоне [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)
Если у вас есть структура под названием dp, это убедительно свидетельствует о том, что вы занимаетесь динамическим программированием снизу вверх. Но вы, кажется, делаете сверху вниз. Я рекомендую выбрать один и быть последовательным. Кроме того, вопрос границ имеет своего рода вопрос.
Ответы 1
Вот простое решение Python, основанное на следующем повторении:
T(k<0, s<0) = 0
T(0, 0) = 1
T(0, s>0) = 0
T(k, s) = sum(T(k/10, s-i) for i in [0, k%10]) + sum(k/10-1, s-i) 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, 20))
«Кажется, есть проблемы с дублированием»: что это означает конкретно? Как узнать, что это псевдокод? Как мы можем воспроизвести проблему?