Overview
Dado un conjunto de denominaciones de monedas, encuentra el número mínimo de monedas para hacer exactamente una cantidad objetivo.
Analogy
Como dar cambio con el mínimo de billetes y monedas — por ejemplo, para 11€ con {1,5,6}: dos monedas (5+6) es mejor que (1+1+1+1+1+1+5).
Step-by-step
- Crea dp[0..amount] inicializado a ∞, dp[0]=0
- Para cada cantidad de 1 a amount:
- Para cada denominación c: si c ≤ cantidad: dp[cantidad] = min(dp[cantidad], dp[cantidad-c]+1)
- dp[amount] es la respuesta (∞ significa imposible)
Visual
monedas=[1,5,6], amount=11
dp[0]=0,dp[1]=1,...,dp[5]=1,dp[6]=1
dp[11]=min(dp[10]+1,dp[6]+1,dp[5]+1)=2
Common mistakes
- Inicializar dp a 0 en lugar de ∞ (excepto dp[0])
- Confundir mínimo de monedas vs número de formas de hacer el cambio
Practice questions
- Modifica para contar el número de combinaciones en lugar del mínimo
- Reconstruye qué monedas se usan rastreando hacia atrás