Coin Change

Hai una quantità illimitata di monete di alcuni valori diversi e vuoi pagare un importo esatto usando il minor numero possibile di monete.

Prendere la moneta più grande che ci sta sembra la scelta giusta, ma può non funzionare. Con le monete [1, 3, 4] e un importo di 6, scegliendo prima la moneta più grande si ottiene 4 + 1 + 1, cioè tre monete, mentre 3 + 3 ne richiede solo due.

Un metodo più sicuro consiste nel costruire la risposta a partire dagli importi più piccoli. Sia fewest[t] il minor numero di monete che sommano a t. Per pagare 0 non servono monete. Per ogni altro t, l'ultima moneta usata ha un certo valore c, e ciò che resta prima di usarla è t - c, quindi

fewest[t] = 1 + the smallest fewest[t - c] tra tutte le monete c il cui valore non supera t.

Per [1, 3, 4]: fewest[3] = 1 e fewest[6] = 1 + fewest[3] = 2. Se nessuna moneta porta a un importo raggiungibile, non è possibile pagare t.

Scrivi una funzione chiamata coinChange che riceva coins, un elenco di valori di monete distinti, e un intero amount, e restituisca il numero minimo di monete che totalizzano esattamente amount. Puoi usare ogni valore di moneta tutte le volte che vuoi. Restituisci -1 se non è possibile ottenere l'importo e 0 quando amount è 0.

Per esempio, coins = [2, 5, 10] e amount = 27 restituisce 4 (10 + 10 + 5 + 2), mentre coins = [4, 6] con amount = 7 restituisce -1.

Vincoli: 1 <= coins.length <= 12, 1 <= coins[i] <= 10^4, tutti i valori sono distinti, 0 <= amount <= 10^4.