Рынок: скупой меняла
Динамическое программирование
Средняя
Меняла выдаёт сдачу amount монетами номиналов coins (запас каждого номинала неограничен), но страшно не любит расставаться с монетами - их должно уйти как можно меньше. Верните минимальное число монет или -1, если сумму не набрать. Внимание: номиналы произвольные, жадный подход 'бери самую крупную' здесь ошибается - нужна динамика.
Сигнатура функции
min_coins_for_amount(coins: list[int], amount: int) -> int
Примеры
| Вход | Ожидаемый результат |
|---|
| [[1, 2, 5], 11] | 3 |
| [[2], 3] | -1 |
1решили
1пытались
100%успешность
Войдите, чтобы решить →