Coin Change

Você tem uma quantidade ilimitada de moedas de alguns valores diferentes e quer pagar um valor exato usando o menor número possível de moedas.

Pegar a maior moeda que ainda cabe parece uma boa ideia, mas pode falhar. Com as moedas [1, 3, 4] e um valor de 6, pegar primeiro a maior moeda resulta em 4 + 1 + 1, três moedas, enquanto 3 + 3 precisa de apenas duas.

Uma maneira mais segura é construir a resposta a partir de valores pequenos. Seja fewest[t] o menor número de moedas que somam t. Para pagar 0, não são necessárias moedas. Para qualquer outro t, a última moeda usada tem algum valor c, e o que resta antes de usá-la é t - c, então

fewest[t] = 1 + the smallest fewest[t - c] entre todas as moedas c que não sejam maiores que t.

Para [1, 3, 4]: fewest[3] = 1, e fewest[6] = 1 + fewest[3] = 2. Se nenhuma moeda levar a um valor que possa ser pago, não será possível pagar t.

Escreva uma função chamada coinChange que recebe coins, uma lista de valores distintos de moedas, e um inteiro amount, e retorna o menor número de moedas que soma exatamente amount. Cada valor de moeda pode ser usado quantas vezes você quiser. Retorne -1 se não for possível obter o valor, e 0 quando amount for 0.

Por exemplo, coins = [2, 5, 10] e amount = 27 retornam 4 (10 + 10 + 5 + 2), e coins = [4, 6] com amount = 7 retorna -1.

Restrições: 1 <= coins.length <= 12, 1 <= coins[i] <= 10^4, todos os valores são distintos, 0 <= amount <= 10^4.