Более эффективный алгоритм определения количества различных разложений числа с использованием только повторных цифр. ⇐ Python

[Anonymous]

Это проблема прошлого семестра, которую я пытаюсь решить. Я пытаюсь решить задачу, связанную с общим количеством способов разложения числа, используя только повторяющиеся цифры. Повторная цифра — это положительное целое число, состоящее только из одной цифры, например. числа 1–9, 11, 22, 3333 и т. д.
Для иллюстрации предположим, что у нас n = 3:
1+1 +1
1+2
2+1
3
всего 4. Обратите внимание, что 1+2 и 2+1 здесь считаются разными.
Теперь у меня есть решение на Python, которое использует динамическое программирование. Я думал, что это будет достаточно эффективно, но, видимо, время все равно превышает установленный лимит (мы используем онлайн-судью, созданную университетом, для автоматической проверки кода). Пределы проблемы до n == 90000 с ограничением всего в 5 секунд. Мы можем использовать только Python. Для справки, вот мой код:

Код: Выделить всё

def count_repdigit_decompositions(n: int) -> int:
rep: list[int] = []
for digit in range(1, 10):
repdigit = digit
while repdigit 

Подробнее здесь: [url]https://stackoverflow.com/questions/78782621/a-more-efficient-algorithm-in-finding-the-number-of-distinct-decompositions-a-nu[/url]