Даны номиналы монет (каждого номинала — сколько угодно штук) и сумма amount.
Нужно вернуть минимальное количество монет, которыми можно набрать ровно эту
сумму, или -1, если набрать её нельзя.
// MinCoins возвращает минимальное число монет с суммой ровно amount или -1.
func MinCoins(coins []int, amount int) int
Примеры
coins = [20, 12, 8, 4, 1], amount = 58 → 6 (20+20+12+4+1+1)
coins = [1, 3, 4], amount = 6 → 2 (3+3; жадный 4+1+1 даёт 3)
coins = [2], amount = 3 → -1
coins = [5], amount = 0 → 0
Ограничения
0 ≤ len(coins) ≤ 100, 1 ≤ coins[i] ≤ 10⁶, номиналы могут повторяться,
порядок произвольный.0 ≤ amount ≤ 10⁵.- Срез
coins менять нельзя.
- Ожидается O(len(coins)·amount) по времени. Перебор всех разложений
экспоненциален и на больших суммах не проходит.
Устно: почему «берём самую крупную монету, пока влезает» здесь не работает?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.