Вам дан целочисленный массив
coins
, представляющий монеты разного номинала, и целочисленный массивamount
, представляющий общую сумму денег.
Верните наименьшее количество монет, необходимое для получения этой суммы. Если эту сумму денег нельзя компенсировать ни одной комбинацией монет, верните
-1
.
Вы можете предположить, что у вас есть бесконечное количество монет каждого вида.
Пример:
Ввод: монеты = [1,2,5], сумма = 11
Вывод: 3
Объяснение: 11 = 5 + 5 + 1
Грубая сила
При решении этого вопроса в уме быстро приходит метод грубой силы.
For example: target = 11, result = 0; 11>5: result=1, target=11–5 =6 6>5: result=2, target=6–5=1 1<5: skip 1<2:skip 1≤1: Result=3, target=1–1=0 target = 0, return result //result=3
Однако этот метод не работает при решении некоторых тестовых случаев: монеты = [1,3,4,5], сумма = 7. В результате будет считаться до 5+1+1=7 вместо подсчета 3+4=7.
Это означает, что мы должны просмотреть монеты для каждого числа, и необходим подход DFS.
ДФС
- сравните число с каждой монетой в каждом слое.
- если минус отрицательный, пропустить.
- найти 0 (кратчайший путь к 0)
- вернуть слой
Ага! Мы можем найти 2 пути с этим подходом во 2-м слое. Итак, решаем кейс с правильным ответом. Решение принуждения Брюса происходит в 3-м слое, который в этот раз не будет учитываться.
Однако что, если вопрос не может быть решен и мы должны вернуть -1? это означает, что мы должны пройти к нижней части дерева, и может возникнуть TLE, поскольку ограничения могут достигать 2³¹-1.
1 <= coins.length <= 12 1 <= coins[i] <= 2³¹-1 0 <= amount <= 10⁴
Динамическое программирование — снизу вверх
Из нашей последней попытки использовать DFS мы заметили, что мы должны искать его снизу. Итак, представлен подход динамического программирования с восходящим подходом.
Глубоко зациклив график из DFS, когда 3 и 2 появляются во 2-м слое, мы можем решить его, используя результат слоя 1. Мы можем улучшить функцию с запоминанием. Но мы также можем решить вопрос следующим образом:
- создать список с длиной, равной количеству.
#хитрость здесь в том, что я создаю список с количеством+1, поэтому я могу получить элемент с индексом - заполните список MAX_VALUE, чтобы просто сравнить, что нам нужно
- цикл от 1 и найти мин. число при сравнении каждой монеты.
- список возврата [сумма] или
- если list[amount] по-прежнему равно MAX_VALUE, вернуть -1
list[1] = 1+[(1–1 = 0), (1–3 <0), (1–4 < 0), (1–5 < 0)] =1 list[2] = 1+[(2–1 = 1 = list[1]), (2–3 <0), (2–4 < 0), (2-5 < 0)] =2 list[3] = 1+[(3–1 = 2 = list[2]), (3–3 = 0), (3–4 <0), (3–5 <0)] =1 …
КОД — Javascript
n = количество
m = длина монет
Временная сложность: O(nm)
Пространственная сложность: O(n)
Спасибо за то, что читаете, новичок в leetcode и medium, пожалуйста, прокомментируйте и помогите мне стать лучше~
НАПРАВЛЯЕМСЯ В FAANG (еще около 10000000 миль…)