Coin Change Problem pregunta: dado un conjunto de denominaciones de monedas y un monto objetivo, ¿cuál es el mínimo número de monedas necesario para alcanzar ese monto?
Es una variante de unbounded knapsack donde cada moneda puede usarse infinitamente. La versión que minimiza monedas usa DP; la versión que cuenta el número de formas también.
Cómo Funciona
- Inicializa
dp[0] = 0,dp[1..amount] = ∞. - Recurre para cada monto
ade 1 aamount:- “Para cada moneda
c: sia >= c,dp[a] = min(dp[a], 1 + dp[a - c]).”
- “Para cada moneda
- Resultado:
dp[amount](o -1 si es ∞).
Idea Clave
La optimal substructure es clara: si la solución óptima para monto a usa una moneda c, entonces el resto debe ser la solución óptima para a - c. Como las monedas son ilimitadas, puedes reutilizar la misma denominación.
Greedy no siempre funciona: con denominaciones [1, 3, 4] y monto 6, greedy toma 4 + 1 + 1 = 3 monedas, pero la óptima es 3 + 3 = 2.
Ejemplo Trabajado
Monedas: [1, 2, 5], monto: 11.
Tabla DP (monto 0..11):
dp[0] = 0
dp[1] = min(dp[0] + 1) = 1
dp[2] = min(dp[1] + 1, dp[0] + 1) = 1
dp[3] = min(dp[2] + 1, dp[1] + 1) = 2
dp[4] = min(dp[3] + 1, dp[2] + 1) = 2
dp[5] = min(dp[4] + 1, dp[3] + 1, dp[0] + 1) = 1
dp[6] = min(dp[5] + 1, dp[4] + 1, dp[1] + 1) = 2
dp[7] = min(dp[6] + 1, dp[5] + 1, dp[2] + 1) = 2
dp[8] = min(dp[7] + 1, dp[6] + 1, dp[3] + 1) = 3
dp[9] = min(dp[8] + 1, dp[7] + 1, dp[4] + 1) = 3
dp[10] = min(dp[9] + 1, dp[8] + 1, dp[5] + 1) = 2
dp[11] = min(dp[10] + 1, dp[9] + 1, dp[6] + 1) = 3Resultado: dp[11] = 3 (monedas: 5 + 5 + 1).
Casos Extremos y Trampas
- Imposible — si
dp[amount]permanece ∞, retorna -1. - Greedy — funciona para sistemas canónicos (USD, EUR) pero falla en general.
- Contar formas —
ways[a] = sum(ways[a - c] for c in coins)cuenta el número de combinaciones. - BFS — modela como shortest path en DAG donde cada arista consume una moneda.
Variantes
| Variante | Objetivo | Complejidad |
|---|---|---|
| Min coins | Minimizar número | O(n × amount) |
| Count ways | Contar combinaciones | O(n × amount) |
| Greedy | Aproximación canónica | O(n log n) |
Aplicaciones
- Sistemas de pago — cambio mínimo en cajeros
- Planificación de recursos — asignación mínima de recursos
- Enseñanza — introduce unbounded DP y límites de greedy
Trayectoria de Práctica
- Implementa DP para min coins; traza el ejemplo
[1,2,5], monto 11. - Muestra un contraejemplo donde greedy falla.
- Extiende para contar el número de formas.
- ¿Por qué BFS también resuelve este problema?
- Investiga coin systems canónicos: ¿cuándo greedy es óptimo?