Контест Middle Задачи на Kotlin обновлено
Размен минимальным числом монет
Условие
Даны номиналы монет (каждой сколько угодно) и сумма s. Найди минимальное число монет, которыми можно набрать ровно s.
Ввод. k s (1 ≤ k ≤ 10, 0 ≤ s ≤ 10^5), затем k различных номиналов от 1 до 10^5.
Вывод. Минимальное число монет или -1, если набрать нельзя.
Жадный выбор самой крупной монеты здесь не работает: для номиналов 1 3 4 и суммы 6 он даст 3 монеты вместо 2.
Как подойти
Подсказки: 2
- dp[v] = минимум монет для суммы v.
- Аккуратно с «бесконечностью» + 1.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.