Код Senior Динамическое программирование обновлено
Минимум монет
Условие
Минимальное число монет, чтобы набрать сумму. Нельзя - -1. Номиналы можно брать сколько угодно раз.
Примеры
coinChange([1, 2, 5], 11) // 3
coinChange([2], 3) // -1
coinChange([1], 0) // 0
Как подойти
Классическая динамика снизу вверх. Жадность (брать самые крупные) здесь неверна: для номиналов [1,3,4] и суммы 6 она даст 3 монеты вместо 2 - назови этот контрпример вслух, его любят.
Подсказки: 2
- dp[сумма] - минимум монет на эту сумму.
- Недостижимые суммы помечай бесконечностью, а не нулём.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.