Сколько раз можно выдать сдачу в n рублей, используя монеты достоинством 1, 2, 5 и 10 рублей? Общее количество монет

Вопрос: Количество способов выдать сдачу в n рублей с использованием монет достоинством 1, 2, 5 и 10 рублей?

Пояснение:
Для решения этой задачи мы можем использовать динамическое программирование. Пусть dp[i] представляет собой количество способов выдать сдачу в i рублей. Изначально, dp[0] = 1, так как единственный способ выдать 0 рублей - не выдавать ничего. Затем, мы перебираем все возможные монеты и для каждой монеты j, начиная с j = 1, до j = n, увеличиваем dp[i] на dp[i - j]. Это происходит потому, что для каждой монеты мы рассматриваем два случая: либо мы используем монету j, либо не используем ее. Таким образом, суммируя все эти варианты, мы получаем общее количество способов выдать сдачу в n рублей.

Пример использования:

Вход: n = 5

Выход: 9



Объяснение: Существует 9 способов выдать сдачу в 5 рублей с использованием монет достоинством 1, 2, 5 и 10 рублей.

Способы:

1, 1, 1, 1, 1

1, 1, 1, 2

1, 2, 2

1, 1, 3

2, 3

1, 4

5

2, 1, 2

2, 2, 1

Совет:
Для лучшего понимания можно попытаться создать таблицу, где каждая строка представляет собой сумму, а столбцы представляют монеты. Значение в каждой ячейке таблицы будет представлять количество способов выдать сдачу данной суммы с использованием монет представленных столбцом. Заполнение этой таблицы по шагам поможет лучше понять, как работает динамическое программирование для этой задачи.

Практика:
Каково количество способов выдать сдачу в 10 рублей с использованием монет достоинством 1, 2, 5 и 10 рублей?