Python 3) Giving change. There is an unlimited number of coins in denominations of 1, 2, 5, 10 rubles. Determine

Marat

46

Чтобы решить эту задачу, мы можем использовать динамическое программирование. Для начала создадим список dp, размер которого будет n+1. Каждый элемент списка будет хранить количество способов дать сдачу для соответствующей суммы. То есть элемент dp[i] будет содержать количество способов дать сдачу для i рублей.

Теперь заполним список dp с помощью следующего алгоритма:

1. Изначально все элементы списка dp будут равны 0, кроме dp[0], который будет равен 1 (потому что есть один способ не давать сдачу).

2. Затем перебираем каждую монету в порядке возрастания (1, 2, 5, 10) и обновляем значения списка dp.

3. Для каждой монеты j, начиная с j-го элемента списка dp, увеличиваем его значение на dp[i - j]. То есть dp[i] = dp[i] + dp[i - j]. Это означает, что мы учитываем все способы составить оставшуюся сумму без учета текущей монеты.

После завершения алгоритма значение последнего элемента списка dp будет содержать число способов дать сдачу для заданной суммы n. Выведем это число в качестве ответа.

Вот решение задачи на языке Python:

python

n = int(input())



dp = [0] * (n + 1)

dp[0] = 1



coins = [1, 2, 5, 10]



for coin in coins:

    for i in range(coin, n + 1):

        dp[i] += dp[i - coin]



print(dp[n])

Таким образом, представленный код решает задачу о количестве способов дать сдачу для заданной суммы n рублей. Количество способов будет напечатано как ответ.