Coin Change

Tu as une quantité illimitée de pièces de quelques valeurs différentes, et tu veux payer un montant exact en utilisant le moins de pièces possible.

Prendre la plus grosse pièce qui convient semble être une bonne idée, mais cela peut échouer. Avec les pièces [1, 3, 4] et un montant de 6, prendre d’abord la plus grosse pièce donne 4 + 1 + 1, soit trois pièces, alors que 3 + 3 n’en nécessite que deux.

Une méthode plus sûre consiste à construire la réponse à partir des petits montants. Soit fewest[t] le nombre minimal de pièces dont la somme est t. Payer 0 ne nécessite aucune pièce. Pour tout autre t, la dernière pièce utilisée a une certaine valeur c, et le montant restant avant de l’utiliser est t - c, donc

fewest[t] = 1 + the smallest fewest[t - c] parmi toutes les pièces c dont la valeur n’est pas supérieure à t.

Pour [1, 3, 4] : fewest[3] = 1, et fewest[6] = 1 + fewest[3] = 2. Si aucune pièce ne permet d’atteindre un montant réalisable, t ne peut pas être payé.

Écrivez une fonction nommée coinChange qui reçoit coins, une liste de valeurs de pièces distinctes, et un entier amount, puis renvoie le nombre minimal de pièces dont la somme est exactement égale à amount. Chaque valeur de pièce peut être utilisée autant de fois que vous le souhaitez. Renvoyez -1 si le montant ne peut pas être obtenu, et 0 lorsque amount vaut 0.

Par exemple, coins = [2, 5, 10] et amount = 27 renvoient 4 (10 + 10 + 5 + 2), et coins = [4, 6] avec amount = 7 renvoient -1.

Contraintes : 1 <= coins.length <= 12, 1 <= coins[i] <= 10^4, toutes les valeurs sont distinctes, 0 <= amount <= 10^4.