Задача о размене монет
Урок 8 из 15 курса Основы динамического программирования на Coddy.
Задача о размене монет — это классическая задача динамического программирования. Дан набор монет разного номинала и общая сумма денег; задача состоит в том, чтобы найти минимальное количество монет, необходимых для составления данной суммы.
Например, предположим, что у нас есть монеты номиналом [1, 5, 10] и мы хотим составить сумму 15. Минимальное количество необходимых монет будет равно 2 (монета номиналом 10 и монета номиналом 5).
Чтобы решить эту задачу с помощью динамического программирования, мы можем создать таблицу, где строки представляют номиналы монет, а столбцы — суммы от 0 до заданной общей суммы. Затем мы заполняем таблицу снизу вверх, вычисляя минимальное количество монет, необходимых для составления каждой суммы с использованием монет каждого номинала.
Задание
СреднеНапишите программу, которая принимает два входных параметра: список номиналов монет и целевую сумму, и возвращает минимальное количество монет, необходимых для составления целевой суммы.
Например, для номиналов [1, 5, 10] и целевой суммы 15, результат должен быть 2.
Попробуйте сами
def min_coins(coins, target):
# Напишите здесь кодВсе уроки раздела Основы динамического программирования
1Введение в динамическое программирование
Что такое динамическое программирование?Почему это важно?Применение в различных областях3Алгоритмы динамического программирования
Наибольшая общая подпоследовательностьЗадача о рюкзакеЗадача о размене монетРасстояние редактирования