Coin Change (Размен монет)
Описание: Даны номиналы монет и сумма. Верните минимальное количество монет, которым можно набрать сумму. Монеты можно брать многократно. Если набрать невозможно, верните -1.
Пример 1:
Вход: coins = [1,2,5], amount = 11
Выход: 3
Объяснение: 11 = 5 + 5 + 1
Пример 2:
Вход: coins = [2], amount = 3
Выход: -1
Объяснение: Нечётную сумму двойками не набрать
Ограничения:
1 <= coins.length <= 12
0 <= amount <= 10⁴
Рекомендуемая временная и пространственная сложность
Стремитесь к O(amount · количество монет) по времени.
Подсказка 1
Жадный подход (брать самую крупную монету) даёт неверный ответ. Проверьте на coins = [1,3,4], amount = 6.
Подсказка 2
Пусть dp[i] — минимум монет для суммы i. Через какие состояния можно прийти в i?
Подсказка 3
В i приходим из i − c для каждой монеты c. Значит dp[i] = min(dp[i − c]) + 1.