Вам дан целочисленный массив 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.

ДФС

  1. сравните число с каждой монетой в каждом слое.
  2. если минус отрицательный, пропустить.
  3. найти 0 (кратчайший путь к 0)
  4. вернуть слой

Ага! Мы можем найти 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. создать список с длиной, равной количеству.
    #хитрость здесь в том, что я создаю список с количеством+1, поэтому я могу получить элемент с индексом
  2. заполните список MAX_VALUE, чтобы просто сравнить, что нам нужно
  3. цикл от 1 и найти мин. число при сравнении каждой монеты.
  4. список возврата [сумма] или
  5. если 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 миль…)