Coin Change

Du hast einen unbegrenzten Vorrat an Münzen mit einigen verschiedenen Werten und möchtest einen exakten Betrag mit möglichst wenigen Münzen bezahlen.

Die größte Münze zu nehmen, die noch passt, klingt sinnvoll, kann aber scheitern. Mit den Münzen [1, 3, 4] und einem Betrag von 6 ergibt die größte Münze zuerst 4 + 1 + 1, also drei Münzen, während 3 + 3 nur zwei benötigt.

Sicherer ist es, die Lösung ausgehend von kleinen Beträgen aufzubauen. Sei fewest[t] die kleinste Anzahl an Münzen, die zusammen t ergeben. Für die Bezahlung von 0 braucht man keine Münzen. Bei jedem anderen t hat die zuletzt verwendete Münze einen Wert c, und der Betrag, der davor noch übrig ist, beträgt t - c, also

fewest[t] = 1 + the smallest fewest[t - c] für jede Münze c, die nicht größer als t ist.

Für [1, 3, 4]: fewest[3] = 1 und fewest[6] = 1 + fewest[3] = 2. Wenn keine Münze zu einem erreichbaren Betrag führt, kann t überhaupt nicht bezahlt werden.

Schreibe eine Funktion namens coinChange, die coins, eine Liste unterschiedlicher Münzwerte, und eine ganze Zahl amount entgegennimmt und die geringstmögliche Anzahl an Münzen zurückgibt, deren Summe genau amount ergibt. Jeder Münzwert kann beliebig oft verwendet werden. Gib -1 zurück, wenn sich der Betrag nicht bilden lässt, und 0, wenn amount gleich 0 ist.

Zum Beispiel ergibt coins = [2, 5, 10] und amount = 27 den Wert 4 (10 + 10 + 5 + 2), und coins = [4, 6] mit amount = 7 ergibt -1.

Einschränkungen: 1 <= coins.length <= 12, 1 <= coins[i] <= 10^4, alle Werte sind unterschiedlich, 0 <= amount <= 10^4.