Overview
Rendu de monnaie : trouve le nombre minimum de pièces nécessaires pour atteindre un montant cible.
Analogy
Comme rendre la monnaie avec le moins de pièces possible — utilise d'abord les plus grosses.
Step-by-step
- Crée un tableau dp de taille montant+1, initialisé à l'infini
- dp[0] = 0 (0 pièces pour 0)
- Pour chaque montant de 1 à cible : dp[i] = min(dp[i-c]+1) pour chaque pièce c ≤ i
- dp[montant] est la réponse (-1 si impossible)
Visual
pièces=[1,3,4], montant=6
dp: [0,1,2,1,1,2,2]
dp[6]=2 (3+3)
Common mistakes
- Utiliser l'approche gloutonne (pas toujours optimale)
- Initialiser dp[0] à 1 au lieu de 0
Practice questions
- Résous avec un ensemble de pièces différent
- Variante : compte le nombre de façons de faire le montant
Time
O(montant × nombre de pièces)