Programación dinámica y voracidad
Mapa conceptual
Los dos ingredientes
- Subestructura óptima: una solución óptima del todo se construye con soluciones óptimas de sus partes.
- Subproblemas traslapados: al resolver recursivamente, se recomputan las mismas piezas una y otra vez.
Programación dinámica
La programación dinámica (DP) explota ambos ingredientes: resuelve cada subproblema una vez y guarda su resultado. Se implementa por arriba (memoización, recursión con caché) o por abajo (tabulación, rellenar una tabla). Convierte un algoritmo exponencial en uno polinomial.
El ejemplo de Fibonacci
Calcular fib(n) = fib(n−1) + fib(n−2) por recursión pura es exponencial por recomputar. Con memoización es O(n): cada valor se calcula una vez. Es el ejemplo mínimo de DP: subproblemas traslapados y una recurrencia clara.
Estrategia voraz
La voracidad toma en cada paso la opción que parece mejor AHORA (máximo beneficio local) esperando llegar al óptimo global. Es simple y rápida, pero solo es válida cuando una elección local segura no arruina el futuro: cuando el problema tiene la propiedad de elección voraz.
| Problema | Voraz funciona | Hace falta DP | Por qué |
|---|---|---|---|
| Monedas canónicas | Si | — | cada moneda grande nunca estorba |
| Monedas arbitrarias | No siempre | Si | tomar la mayor puede no dar el mínimo |
| Mochila 0-1 | No | Si | lo mejor por unidad de peso puede no caber óptimo |
| Intervalos (agendar máx.) | Si | — | elegir el que termina antes es seguro |
¿Qué distingue a la programación dinámica de la simple recursión divide y vencerás?
El cambio de monedas, caso vivo
Con monedas 1, 3, 4 y objetivo 6: lo voraz toma la de 4 y luego dos de 1 (tres monedas). Lo óptimo son dos de 3. La voraz falla porque la moneda más grande no garantiza el mínimo total: hace falta DP sobre «mínimo monedas para cada importe».
Mochila
En la mochila 0-1, ordenar por valor/peso y meter lo más rentable (voraz) puede dejar un hueco caro. DP define «mejor valor con los ítems hasta i y capacidad w» y explora incluir o no en O(n·capacidad).
Si un problema no tiene subproblemas traslapados, la programación dinámica ofrece ventaja sobre la recursión directa.
Errores frecuentes
- Aplicar voracidad sin probar la propiedad de elección (o sin un argumento de intercambio).
- Definir mal el estado en DP: si los estados no capturan lo necesario, la recurrencia falla.
- Olvidar el orden de relleno en tabulación, leyendo valores aún no computados.
Cómo decidirse
- ¿Tiene subestructura óptima? Si no, ninguno de los dos sirve (busca otra vía).
- ¿Se puede justificar una elección local segura? Sí → voraz; es más simple y rápido.
- ¿Los subproblemas se traslapan y no hay garantía voraz? → DP, define el estado con cuidado.
Vocabulario de optimización
Wikipedia
Programación dinámica, ejemplos y comparación con voracidad.
Explica por qué «dar el cambio con el mínimo número de monedas» es resolvable voraz con monedas comunes pero requiere DP con un sistema arbitrario. Da un contraejemplo concreto.
VisuAlgo
Visualizaciones animadas de estructuras de datos y algoritmos.