Coin Change

Tienes una cantidad ilimitada de monedas de unos cuantos valores diferentes y quieres pagar una cantidad exacta usando tan pocas monedas como puedas.

Elegir la moneda más grande que todavía quepa parece una buena idea, pero puede fallar. Con monedas [1, 3, 4] y una cantidad de 6, elegir primero la moneda más grande da 4 + 1 + 1, tres monedas, mientras que 3 + 3 solo necesita dos.

Una forma más segura es ir construyendo la respuesta a partir de cantidades pequeñas. Sea fewest[t] la menor cantidad de monedas que suman t. Para pagar 0 no se necesitan monedas. Para cualquier otro t, la última moneda que usas tiene algún valor c, y lo que queda antes de usarla es t - c, así que

fewest[t] = 1 + the smallest fewest[t - c] entre todas las monedas c que no sean mayores que t.

Para [1, 3, 4]: fewest[3] = 1, y fewest[6] = 1 + fewest[3] = 2. Si ninguna moneda lleva a una cantidad alcanzable, no se puede pagar t.

Escribe una función llamada coinChange que reciba coins, una lista de valores de monedas distintos, y un entero amount, y devuelva la menor cantidad de monedas que suman exactamente amount. Puedes usar cada valor de moneda tantas veces como quieras. Devuelve -1 si no se puede obtener el importe y 0 cuando amount es 0.

Por ejemplo, coins = [2, 5, 10] y amount = 27 devuelve 4 (10 + 10 + 5 + 2), y coins = [4, 6] con amount = 7 devuelve -1.

Restricciones: 1 <= coins.length <= 12, 1 <= coins[i] <= 10^4, todos los valores son distintos, 0 <= amount <= 10^4.