0Pricing
Coding Interview Prep · Leçon

Rendu de monnaie et escalier au coût minimal

Formulez les récurrences de coin-change et min-cost-climbing-stairs, choisissez la bonne direction pour la DP et suivez manuellement le remplissage du tableau.

Rendu de monnaie et escalier au coût minimal est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.

Rendu de monnaie : le problème

Rendu de monnaie (LeetCode #322) vous fournit des valeurs de pièces et un montant cible. Trouvez le nombre minimal de pièces nécessaires pour obtenir exactement ce montant. Vous disposez d'un nombre illimité de pièces de chaque valeur. Il s'agit d'une variante du problème du sac à dos illimité : chaque élément, ici une pièce, peut être utilisé autant de fois que nécessaire. C'est l'un des problèmes de DP les plus importants, car il évalue votre capacité à formuler une récurrence à partir de zéro.

# Problem examples:
# coins=[1,5,6,9], amount=11 -> 2 (5+6 or 2+9? no: 5+6=11 YES)
# coins=[2],       amount=3  -> -1 (impossible)
# coins=[1,2,5],   amount=11 -> 3 (5+5+1)
# coins=[186,419,83,408], amount=6249 -> 20

# Key choices:
# - Try each coin denomination at each step
# - Minimum coins = 1 + minimum(coins to make amount - coin)
# - If amount < 0: impossible
# - If amount = 0: done (0 coins)

print('Coin change: unbounded knapsack, find minimum count')

Rendu de monnaie : dérivation de la récurrence

Définissez dp[i] comme le nombre minimal de pièces nécessaires pour obtenir le montant i. Pour chaque montant i, essayez d'utiliser chaque pièce c : si i >= c, alors dp[i] = min(dp[i], 1 + dp[i-c]). Le « 1 » correspond à la pièce que vous venez d'utiliser ; dp[i-c] est la solution optimale pour le montant restant. Cela suppose que le nombre de pièces est illimité. Cas de base : dp[0] = 0. Initialisez toutes les autres entrées à l'infini pour représenter les montants « pas encore réalisables ».

def coin_change(coins, amount):
    # dp[i] = min coins to make amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # base: 0 coins for amount 0

    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], 1 + dp[i - coin])

    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 5, 6, 9], 11))  # 2
print(coin_change([2], 3))             # -1
print(coin_change([1, 2, 5], 11))      # 3

# Trace dp for coins=[1,5] amount=6:
# dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=4, dp[5]=1, dp[6]=2

Rendu de monnaie : pourquoi l'approche gloutonne échoue

L'approche gloutonne, qui consiste à toujours choisir la plus grande pièce possible, échoue pour le rendu de monnaie. Exemple : avec les pièces [1, 3, 4] et le montant 6, elle choisit 4 puis 1 + 1, soit 3 pièces. La solution optimale est 3 + 3, soit 2 pièces. L'approche gloutonne fonctionne avec les valeurs courantes (1, 5, 10 et 25 centimes), car celles-ci satisfont par chance la propriété gloutonne. Mais pour des ensembles de pièces arbitraires, la DP est nécessaire. C'est un point classique des entretiens : indiquer que l'approche gloutonne échoue et expliquer pourquoi témoigne d'une solide capacité d'analyse.

# Greedy failure example:
# coins=[1,3,4], amount=6
# Greedy: 4 (rem=2), 1 (rem=1), 1 (rem=0) -> 3 coins
# Optimal: 3 (rem=3), 3 (rem=0) -> 2 coins

def coin_change_greedy_wrong(coins, amount):
    coins_sorted = sorted(coins, reverse=True)
    count = 0
    for coin in coins_sorted:
        while amount >= coin:
            amount -= coin
            count += 1
    return count if amount == 0 else -1

print('Greedy:', coin_change_greedy_wrong([1,3,4], 6))  # 3 (WRONG)
print('DP:    ', coin_change([1,3,4], 6))               # 2 (CORRECT)

Rendu de monnaie II : compter les possibilités

Rendu de monnaie II (LeetCode #518) demande le nombre de façons d'obtenir le montant, et non le nombre minimal de pièces. La récurrence change : au lieu de prendre le minimum, on fait une somme. Utilisez dp[i] += dp[i-coin] pour chaque pièce. L'ordre de remplissage est important : pour compter chaque combinaison une seule fois, parcourez les pièces dans la boucle externe et les montants dans la boucle interne. Inverser les boucles compte les permutations au lieu des combinaisons, ce qui correspond à un autre problème.

def coin_change_ii(coins, amount):
    # dp[i] = number of ways to make amount i
    dp = [0] * (amount + 1)
    dp[0] = 1  # one way to make amount 0: use no coins

    # Outer loop: coins -- ensures each coin type processed once
    for coin in coins:
        # Inner loop: amounts
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

print(coin_change_ii([1, 2, 5], 5))   # 4: [1,1,1,1,1],[1,1,1,2],[1,2,2],[5]
print(coin_change_ii([2], 3))          # 0: impossible
print(coin_change_ii([10], 10))        # 1

# Key: coin outer, amount inner = COMBINATIONS (unordered)
# Reverse (amount outer, coin inner) = PERMUTATIONS (ordered)

Escalier à coût minimal : le problème

Escalier à coût minimal (LeetCode #746) vous fournit un escalier dont chaque marche a un coût. Vous pouvez monter 1 ou 2 marches à la fois. Trouvez le coût minimal pour atteindre le sommet, c'est-à-dire une marche au-delà de la dernière. Vous pouvez commencer gratuitement à la marche 0 ou à la marche 1. Ce problème combine élégamment la récurrence de l'escalier avec le schéma de minimisation des coûts du rendu de monnaie, ce qui en fait un lien naturel entre les deux.

# cost = [10, 15, 20]
# Pay cost[i] to leave step i
# You can step to i+1 or i+2
# Goal: reach top (index 3) with minimum cost

# Path options:
# Start at 0: cost 10, go to 2: cost 20, done -> 30
# Start at 1: cost 15, go to 3: done -> 15  <- OPTIMAL
# Start at 0: cost 10, go to 1: cost 15 -> 25

cost = [10, 15, 20]
# Optimal: start at step 1, pay 15, jump to top -> cost = 15
print('Expected:', 15)

Escalier à coût minimal : récurrence

Définissez dp[i] comme le coût minimal pour atteindre la marche i. Vous arrivez à la marche i en payant cost[i-1] depuis la marche i-1, ou cost[i-2] depuis la marche i-2. Ainsi, dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). Cas de base : dp[0] = 0, car le départ se trouve avant l'escalier et est gratuit ; dp[1] = 0, car vous pouvez également commencer gratuitement à la marche 1. La réponse est dp[n], où n = len(cost).

def min_cost_climbing_stairs(cost):
    n = len(cost)
    # dp[i] = minimum cost to reach step i
    # Steps 0 to n; step n is the top (goal)
    dp = [0] * (n + 1)
    # dp[0] = 0 (free to start here)
    # dp[1] = 0 (free to start here)
    for i in range(2, n + 1):
        dp[i] = min(dp[i-1] + cost[i-1],   # step from i-1
                    dp[i-2] + cost[i-2])    # jump from i-2
    return dp[n]

print(min_cost_climbing_stairs([10, 15, 20]))      # 15
print(min_cost_climbing_stairs([1,100,1,1,1,100,1,1,100,1]))  # 6

Escalier à coût minimal : optimisation de l'espace

Puisque dp[i] ne dépend que de dp[i-1] et dp[i-2], nous pouvons réduire l'espace à O(1) à l'aide de deux variables, comme pour Fibonacci. Remplacez le tableau par prev2 et prev1. Mettez-les à jour à chaque étape. Il s'agit d'une optimisation standard en une seule ligne que les recruteurs attendent après la présentation de la solution avec tableau en O(n). Mentionnez-la toujours spontanément : « Nous pouvons réduire l'espace à O(1), puisque nous n'avons besoin que des deux dernières valeurs. »

def min_cost_optimised(cost):
    n = len(cost)
    prev2, prev1 = 0, 0  # dp[0] and dp[1]
    for i in range(2, n + 1):
        curr = min(prev1 + cost[i-1], prev2 + cost[i-2])
        prev2, prev1 = prev1, curr
    return prev1

print(min_cost_optimised([10, 15, 20]))  # 15
print(min_cost_optimised([1,100,1,1,1,100,1,1,100,1]))  # 6

# Alternative: directly use cost array as rolling storage
def min_cost_v2(cost):
    n = len(cost)
    for i in range(2, n):
        cost[i] += min(cost[i-1], cost[i-2])
    return min(cost[-1], cost[-2])

from copy import deepcopy
cost_test = [10,15,20]
print(min_cost_v2(deepcopy(cost_test)))  # 15

Formulation DP alternative

Certains problèmes admettent plusieurs formulations DP valides. Pour l'escalier à coût minimal, vous pouvez définir dp[i] comme le coût minimal pour LEAVE la marche i, en payant cost[i] et en choisissant d'aller à i+1 ou i+2. Dans ce cas, dp[i] = cost[i] + min(dp[i+1], dp[i+2]) en remplissant de droite à gauche, et la réponse est min(dp[0], dp[1]). Les deux formulations sont correctes. Entraînez-vous à expliquer quelle formulation vous avez choisie et pourquoi : cela démontre votre aisance en DP.

def min_cost_alternative(cost):
    n = len(cost)
    # dp[i] = min cost when starting FROM step i
    # Fill right to left
    dp = cost[:] + [0]  # dp[n] = 0 (already at top)
    for i in range(n - 1, -1, -1):
        # Pay cost[i], then choose i+1 or i+2
        if i + 2 <= n:
            dp[i] = cost[i] + min(dp[i+1], dp[i+2])
        else:
            dp[i] = cost[i] + dp[i+1]
    # Can start at step 0 or step 1
    return min(dp[0], dp[1])

print(min_cost_alternative([10, 15, 20]))  # 15
print(min_cost_alternative([1,100,1,1,1,100,1,1,100,1]))  # 6

Relier le rendu de monnaie et l'escalier

Le rendu de monnaie et l'escalier à coût minimal sont deux instances du même schéma de DP : à chaque étape, vous choisissez une option parmi un ensemble fini, puis optimisez un objectif sur la séquence de choix. Les différences sont superficielles : le rendu de monnaie suit un nombre, en ajoutant 1 par pièce, tandis que l'escalier suit un coût, en ajoutant cost[i] par étape. Reconnaître cette structure commune vous permet de résoudre de nouveaux problèmes de DP en les associant à des modèles familiers.

# Shared pattern:
# dp[state] = optimise(dp[prev_state_1] + cost_1,
#                      dp[prev_state_2] + cost_2, ...)

# Coin change:  dp[amount] = min(1 + dp[amount - coin] for coin in coins)
# Min stair:    dp[step]   = min(cost[step-1]+dp[step-1], cost[step-2]+dp[step-2])
# Max path sum: dp[cell]   = max(dp[top], dp[left]) + grid[cell]
# House robber: dp[house]  = max(dp[house-1], dp[house-2] + value[house])

# All four are the SAME pattern with different:
# - State representation
# - Number of choices per state
# - Objective (min/max)
# - Transition cost
print('DP pattern: state + choices + objective + cost = template')

Nombre minimal de carrés parfaits

Carrés parfaits (LeetCode #279) demande le nombre minimal de carrés parfaits (1, 4, 9, 16, ...) dont la somme vaut n. C'est exactement le problème du rendu de monnaie, où les « pièces » sont des carrés parfaits. Générez tous les carrés parfaits jusqu'à n, puis appliquez le rendu de monnaie. La DP s'exécute en O(n * sqrt(n)) time. Le théorème des quatre carrés de Lagrange nous indique que la réponse est au plus égale à 4, ce qui permet également une approche mathématique en O(sqrt(n)), mais la solution attendue est la DP.

import math

def num_squares(n):
    # Generate all perfect squares up to n
    squares = [i*i for i in range(1, int(math.sqrt(n)) + 1)]
    # Coin change with squares as 'coins'
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        for sq in squares:
            if i >= sq:
                dp[i] = min(dp[i], 1 + dp[i - sq])
    return dp[n]

print(num_squares(12))  # 3: 4+4+4
print(num_squares(13))  # 2: 4+9
print(num_squares(1))   # 1: 1

Débogage de DP : erreurs courantes

Erreurs courantes en DP : cas de base incorrect (dp[0] mal initialisé), ordre de remplissage incorrect (accès à une valeur qui n'a pas encore été calculée), erreur de décalage d'une unité dans la définition de l'état (dp[i] représente le coût pour atteindre i ou le coût pour LEAVE i), et absence de retour de -1 lorsqu'il reste l'infini (cas impossibles). Testez toujours les cas les plus simples, comme une entrée vide, un seul élément ou une cible égale à 0, avant de tester des entrées plus grandes.

# Common DP debugging checklist:
# 1. Base case: what is dp[0]? dp[1]? Are they correct?
# 2. State definition: write it in English before coding
# 3. Recurrence: trace manually on a 3-element example
# 4. Fill order: dependency arrows point left/up? Fill left/up first
# 5. Infinity check: return -1 or 0 when dp[target] == inf?
# 6. Array bounds: dp has size n+1 for 0..n, or n for 0..n-1?

# Quick test template:
def test_coin_change():
    assert coin_change([1], 0) == 0     # base case
    assert coin_change([1], 1) == 1     # single coin
    assert coin_change([2], 3) == -1    # impossible
    assert coin_change([1,5,6,9], 11) == 2
    print('All tests passed!')

test_coin_change()

Vérification rapide

Évaluez votre compréhension des concepts de Structures de données et algorithmes — Préparation aux entretiens de programmation abordés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris : la DP du rendu de monnaie avec nombre minimal de pièces, c'est-à-dire le sac à dos illimité, et pourquoi l'approche gloutonne échoue ; le rendu de monnaie II pour compter les combinaisons avec les pièces dans la boucle externe et les montants dans la boucle interne ; ainsi que l'escalier à coût minimal avec ses formulations de gauche à droite et de droite à gauche. Ensuite, nous explorerons les schémas de DP 1D avec le voleur de maisons, l'algorithme de Kadane et la segmentation de mots.

Questions Fréquemment Posées

La leçon « Rendu de monnaie et escalier au coût minimal » est-elle gratuite ?

Oui — le texte complet de « Rendu de monnaie et escalier au coût minimal » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Rendu de monnaie et escalier au coût minimal » ?

Formulez les récurrences de coin-change et min-cost-climbing-stairs, choisissez la bonne direction pour la DP et suivez manuellement le remplissage du tableau. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?

Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.

Combien de temps prend la leçon « Rendu de monnaie et escalier au coût minimal » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?

Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Reconnaître la DP : sous-problèmes qui se recouvrent
  2. DP descendante avec mémoïsation
  3. DP ascendante avec tabulation
  4. Rendu de monnaie et escalier au coût minimal
← Retour à Coding Interview Prep