Coin Change

Masz nieograniczony zapas monet o kilku różnych nominałach i chcesz zapłacić dokładną kwotę, używając jak najmniejszej liczby monet.

Wydaje się, że najlepiej wziąć największą monetę, która jeszcze pasuje, ale to może się nie udać. Przy monetach [1, 3, 4] i kwocie 6 wzięcie najpierw największej monety daje 4 + 1 + 1, czyli trzy monety, podczas gdy 3 + 3 wymaga tylko dwóch.

Bezpieczniejszym sposobem jest budowanie rozwiązania od małych kwot. Niech fewest[t] oznacza najmniejszą liczbę monet, których suma wynosi t. Zapłacenie 0 nie wymaga żadnych monet. Dla każdego innego t ostatnia użyta moneta ma jakąś wartość c, a pozostała wcześniej kwota to t - c, więc

fewest[t] = 1 + the smallest fewest[t - c] spośród wszystkich monet c, których wartość nie przekracza t.

Dla [1, 3, 4]: fewest[3] = 1, a fewest[6] = 1 + fewest[3] = 2. Jeśli żadna moneta nie prowadzi do osiągalnej kwoty, nie da się zapłacić t.

Napisz funkcję o nazwie coinChange, która przyjmuje coins, listę różnych wartości monet, oraz liczbę całkowitą amount i zwraca najmniejszą liczbę monet, których suma wynosi dokładnie amount. Każdej wartości monety możesz użyć dowolną liczbę razy. Zwróć -1, jeśli nie da się uzyskać podanej kwoty, a 0, gdy amount wynosi 0.

Na przykład coins = [2, 5, 10] i amount = 27 zwraca 4 (10 + 10 + 5 + 2), a coins = [4, 6] przy amount = 7 zwraca -1.

Ograniczenia: 1 <= coins.length <= 12, 1 <= coins[i] <= 10^4, wszystkie wartości są różne, 0 <= amount <= 10^4.