Coin Change

Q: Quelle est la complexité temporelle du problème du rendu de monnaie ?

La solution de programmation dynamique prend O(amount × coins) en temps et O(amount) en espace : une entrée de table par montant, et chaque pièce est vérifiée pour chaque entrée. La récursion simple sans mémoïsation est exponentielle par rapport au montant.

Q: La méthode descendante ou ascendante est-elle préférable pour le problème de rendu de monnaie ?

Les deux effectuent le même travail en O(amount × coins) . La récursion descendante peut s’imbriquer jusqu’à atteindre la valeur du montant, ce qui provoque un débordement de la pile d’appels pour 10^4 dans plusieurs langages. L’approche ascendante remplit le tableau à l’aide d’une boucle : elle n’a donc aucune limite de profondeur et constitue le choix le plus sûr lors d’un entretien.

MoyenProgrammation dynamique

+10

Vous recevez une liste coins de différentes valeurs de pièces et un amount cible. Vous pouvez utiliser chaque valeur de pièce autant de fois que vous le souhaitez. Renvoyez le plus petit nombre de pièces dont les valeurs totalisent exactement amount, ou -1 si aucune combinaison de pièces ne permet de l’atteindre. Un montant de 0 nécessite 0 pièce.

Fonction

coinChange(coins: integer-array, amount: integer) → integer

coinsinteger-array: les différentes valeurs de pièces, chacune utilisable autant de fois que nécessaire
amountinteger: le montant total à payer exactement
Renvoieinteger: le nombre minimum de pièces nécessaire, ou -1 lorsque le montant ne peut pas être composé

Contraintes

1 ≤ coins.length ≤ 12
1 ≤ coins[i] ≤ 10⁴
0 ≤ amount ≤ 10⁴
Toutes les valeurs des pièces sont différentes.

Exemples

Entrée: coins = [2, 5, 10]amount = 27
Sortie: 4
Explication: 10 + 10 + 5 + 2 font 27 avec quatre pièces. Trois pièces ne suffisent pas : 27 est impair, donc il faut exactement une pièce de 5, et les deux autres totalisent au maximum 20, ce qui est inférieur à 22.

Pour aller plus loin

Peux-tu compter combien de combinaisons différentes de pièces permettent d’obtenir amount, au lieu de chercher le nombre minimal de pièces ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Prendre la plus grande pièce qui convient échoue : avec des pièces de 1, 3 et 4, on paie 6 avec 4 + 1 + 1, alors que 3 + 3 nécessite deux pièces. Le nombre minimal de pièces pour un montant dépend uniquement du nombre minimal de pièces pour les montants inférieurs, donc tu résous une fois chaque montant de 0 à amount.

Essaie toutes les combinaisons avec la récursion

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Si la dernière pièce que tu paies vaut c, les pièces qui la précèdent paient remaining - c de la manière la plus économique possible. Donc fewest(remaining) est égal à un de plus que la meilleure valeur de fewest(remaining - c) parmi toutes les pièces qui conviennent. Cette méthode essaie toutes les séquences de pièces dont la somme ne dépasse pas le montant demandé, elle ne peut donc pas passer à côté de la meilleure.

Elle résout les mêmes montants encore et encore. Avec des pièces de 2, 5 et 10, le montant 27 atteint 15 après avoir payé 10 + 2, 2 + 10, 5 + 5 + 2 et d'autres ordres, et calcule 15 depuis le début à chaque fois. Le nombre d'appels croît de manière exponentielle avec le montant.

Algorithme

Écris une fonction auxiliaire fewest(remaining) qui renvoie le nombre minimal de pièces pour remaining, ou -1 si aucune solution n’existe.
Si remaining vaut 0, renvoie 0.
Pour chaque pièce qui ne dépasse pas remaining, appelle la fonction auxiliaire avec ce qu’il reste après avoir payé cette pièce.
Garde le plus petit résultat différent de -1, plus un pour la pièce payée.
Renvoie ce nombre, ou -1 si aucune pièce ne mène à une solution. La réponse est fewest(amount).

def coinChange(coins, amount):
    def fewest(remaining):
        # The fewest coins that add up to remaining, or -1 if no mix does
        if remaining == 0:
            return 0
        best = -1
        for coin in coins:
            if coin <= remaining:
                rest = fewest(remaining - coin)
                if rest != -1 and (best == -1 or rest + 1 < best):
                    best = rest + 1
        return best

    return fewest(amount)

Récursion avec mémoïsation

Correcte, mais ne termine pas sur les plus gros tests

Intuition

La récursion ne porte que sur les montants de 0 à amount. Stockez chaque réponse dans un tableau la première fois que vous la calculez, et renvoyez la valeur stockée lorsque ce montant se présente à nouveau. Chaque montant est résolu une seule fois à l’aide d’une boucle sur les pièces : O(amount × coins) opérations.

Les appels continuent de s’imbriquer à raison d’un niveau par pièce utilisée. Avec une pièce d’une valeur de 1, cela peut atteindre 10^4 niveaux, soit plus que ce que la pile d’appels par défaut autorise dans de nombreux langages.

Algorithme

Créez un tableau memo pouvant contenir chaque montant de 0 à amount, avec un marqueur indiquant que le calcul n’a pas encore été effectué.
Dans fewest(remaining), renvoyez 0 pour 0, et renvoyez memo[remaining] si cette case contient déjà une réponse.
Sinon, essayez chaque pièce qui convient, comme dans la récursion simple, et conservez le plus petit résultat augmenté de un.
Enregistrez le résultat, y compris -1, dans memo[remaining] avant de le renvoyer.
Renvoyez fewest(amount).

def coinChange(coins, amount):
    # memo[r] holds the answer for r once it is worked out; None means not yet
    memo = [None] * (amount + 1)

    def fewest(remaining):
        # The fewest coins that add up to remaining, or -1 if no mix does
        if remaining == 0:
            return 0
        if memo[remaining] is not None:
            return memo[remaining]
        best = -1
        for coin in coins:
            if coin <= remaining:
                rest = fewest(remaining - coin)
                if rest != -1 and (best == -1 or rest + 1 < best):
                    best = rest + 1
        memo[remaining] = best
        return best

    return fewest(amount)

Programmation dynamique ascendante sur les montants

Intuition

Remplissez une table fewest en partant de 0 et en avançant. Lorsque vous atteignez un total t, tous les totaux inférieurs sont réglés, donc fewest[t] vaut un de plus que le plus petit fewest[t-c] parmi les pièces c qui conviennent.

Les totaux qu’aucune combinaison de pièces ne permet d’atteindre contiennent le marqueur amount + 1. Chaque pièce vaut au moins 1, donc une réponse réelle n’utilise jamais plus de amount pièces, et le marqueur perd toutes les comparaisons. Une boucle remplace la récursion, donc la profondeur de la pile d’appels n’a jamais d’importance.

Algorithme

Créez fewest avec amount + 1 entrées, toutes initialisées à la valeur marqueur amount + 1, puis définissez fewest[0] à 0.
Pour chaque total t de 1 à amount, examinez chaque pièce c telle que c ≤ t.
Si fewest[t-c] + 1 est inférieur à fewest[t], stockez-le dans fewest[t].
Après la boucle, renvoyez -1 si fewest[amount] contient toujours la valeur marqueur, et fewest[amount] sinon.

def coinChange(coins, amount):
    impossible = amount + 1
    fewest = [0] + [impossible] * amount
    for total in range(1, amount + 1):
        for coin in coins:
            if coin <= total and fewest[total - coin] + 1 < fewest[total]:
                fewest[total] = fewest[total - coin] + 1
    return fewest[amount] if fewest[amount] != impossible else -1

Pièges et cas limites

Prendre d’abord la plus grande pièce. Avec les pièces 3 et 5 et un montant de 9, on utilise 5 et 3, on se retrouve bloqué à 1 et on renvoie -1, alors que 3 + 3 + 3 fonctionne.
Utiliser le plus grand entier comme marqueur. Lui ajouter 1 provoque un dépassement qui le transforme en nombre négatif, lequel remporte alors toutes les comparaisons. Utilisez amount + 1.
Ajouter 1 à une impasse. Une branche qui renvoie -1, plus la pièce utilisée, donne 0 et remporte toutes les comparaisons. Ignorez les résultats -1.
Récursivité sur amount niveaux. Avec une pièce de valeur 1 et un montant de 10^4, Python s’arrête à sa limite par défaut de 1000 niveaux, et JavaScript, Dart, Ruby et R manquent aussi de pile.
Lire fewest[t-c] pour une pièce plus grande que t, avant le début de la table.

Questions fréquentes3

Pourquoi l’approche gloutonne échoue-t-elle pour le problème de rendu de monnaie ?

Prendre la plus grande pièce qui convient n’est sûr que pour certains systèmes monétaires, comme la plupart des monnaies réelles. Avec des pièces de 1, 3 et 4, il faut 6 avec trois pièces au lieu de deux, et avec des pièces de 3 et 5, il est impossible de faire 9. La programmation dynamique compare tous les choix : aucun système monétaire ne peut donc la tromper.

Quelle est la complexité temporelle du problème du rendu de monnaie ?

La solution de programmation dynamique prend O(amount × coins) en temps et O(amount) en espace : une entrée de table par montant, et chaque pièce est vérifiée pour chaque entrée. La récursion simple sans mémoïsation est exponentielle par rapport au montant.

La méthode descendante ou ascendante est-elle préférable pour le problème de rendu de monnaie ?

Les deux effectuent le même travail en O(amount × coins). La récursion descendante peut s’imbriquer jusqu’à atteindre la valeur du montant, ce qui provoque un débordement de la pile d’appels pour 10^4 dans plusieurs langages. L’approche ascendante remplit le tableau à l’aide d’une boucle : elle n’a donc aucune limite de profondeur et constitue le choix le plus sûr lors d’un entretien.

def coinChange(coins, amount):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

coins = [2, 5, 10]
amount = 27

Résultat attendu

Coin Change

Fonction

Contraintes

Exemples

Indices

Solution

Essaie toutes les combinaisons avec la récursion

Récursion avec mémoïsation

Programmation dynamique ascendante sur les montants

Pièges et cas limites

Questions fréquentes3

Problèmes similaires