Сколькими способами можно разменять 100 рублей монетами по 1 ; 2 ; 5 рублей??

Предыдущий
вопрос Следующий
вопрос

Для решения данной задачи можно воспользоваться методом динамического программирования.

Сначала создадим таблицу размером 101x3 (так как у нас есть 3 типа монет: 1, 2 и 5 рублей), заполним нулями и пометим первую строку единицами, так как сумма 0 может быть разменяна только одним способом - никак.

Затем начнем заполнять таблицу, используя следующее рекуррентное соотношение:
dp[i][j] = dp[i][j-1] + dp[i - coins[j]][j], где i - сумма, которую мы хотим разменять, j - тип монеты, coins[j] - стоимость этой монеты.

После того как заполним таблицу, сумма всех значений в последнем столбце будет общим количеством способов разменять 100 рублей монетами по 1, 2 и 5 рублей.

Таким образом, общее количество способов разменять 100 рублей монетами по 1, 2 и 5 рублей составит значение в ячейке dp[100][2].