Несколько десятилетей назад были в ходу монеты по 3 и 5 коп. Сколькими способами можно набрать ими сумму в 10 р.?

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

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

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

Далее, для каждой монеты по 3 и 5 копеек пройдемся по массиву dp и обновим значения сумм, которые можно набрать. Например, чтобы набрать сумму в 3 рубля, можно использовать 1 монету по 3 копейки и получить сумму 3 рубля, либо набрать 3 рубля из 0 рублей и добавить одну монету по 3 копейки.

После обновления всех значений в массиве dp, ответом на задачу будет dp[10] - количество способов набрать 10 рублей с монетами по 3 и 5 копеек.

Программный код для решения этой задачи в Python:

Ответ: 4 способа.