Intermédiaire
🧠 Fondamentaux
20 XP
0 personnes ont réussi
Rendu de monnaie (Coin Change)
Imagine que tu es caissier et que tu dois rendre la monnaie avec le moins de pieces possible. Tu as des pieces de differentes valeurs et tu cherches la combinaison minimale.
C'est un problème classique de programmation dynamique. L'idee : on construit un tableau dp ou dp[i] représente le nombre minimum de pieces pour atteindre le montant i.
Pour chaque montant de 1 jusqu'au montant cible, on essaie chaque piece disponible et on prend le minimum.
Exemples : coin_change([1, 5, 10], 15) renvoie 2 (une piece de 10 + une de 5) coin_change([2], 3) renvoie -1 (impossible avec des pieces de 2) coin_change([1, 2, 5], 11) renvoie 3 (5 + 5 + 1)
Écris une fonction coin_change(pieces, montant) qui retourne le nombre minimum de pieces, ou -1 si c'est impossible.
Tests (2/4)
Exemple classique
assert coin_change([1, 2, 5], 11) == 3
Impossible
assert coin_change([2], 3) == -1
+ 0 tests cachés
Indices (3 disponibles)
Solution officielle
def coin_change(pieces, montant):
dp = [montant + 1] * (montant + 1)
dp[0] = 0
for i in range(1, montant + 1):
for piece in pieces:
if piece <= i:
dp[i] = min(dp[i], dp[i - piece] + 1)
return dp[montant] if dp[montant] <= montant else -1