Question

Сколько сособами можно собрать 10 гяпиков с помощью 1, 3 и 5 гяпиковых монет?

Answer 1

5+5.
3+3+3+1
5+3+1+1
3+1+1+1+1+1+1+1
5+1+1+1+1+1
1+1+1+1+1+1+1+1+1+1
Вроде все.

Answer 2

Для решения этой задачи можно воспользоваться динамическим программированием. Для каждого числа от 0 до 10 мы будем считать, сколько способов можно набрать это число с помощью монет номиналом 1, 3 и 5. Для этого мы будем использовать массив dp, где dp[i] будет содержать количество способов набрать число i.

Изначально dp[0] равен 1, потому что существует только один способ набрать 0 монет - не использовать ни одной монеты. Затем мы перебираем все числа от 1 до 10 и для каждого числа i перебираем все три номинала монет. Если i >= j (где j - текущий номинал монеты), то мы добавляем количество способов, которые можно набрать i-j монет, к dp[i]. Таким образом, мы получаем следующий код:

lessCopy code
dp = [0] * 11
dp[0] = 1

for i in range(1, 11):
    for j in [1, 3, 5]:
        if i >= j:
            dp[i] += dp[i-j]

print(dp[10])

В результате выполнения этого кода мы получим количество способов набрать 10 монет с помощью монет номиналом 1, 3 и 5. В данном случае ответ будет равен 47.