5.1. Método general.
La programación dinámica se basa en el Principio de Optimalidad de Bellman: cualquier subsecuencia de una secuencia óptima debe ser, a su vez, una secuencia óptima.
Ejemplo. Si tenemos un camino mínimo de A a B pasando por C, entonces los trozos de camino de A a C, y de C a B deben ser también mínimos.
Este principio no es aplicable en todos los problemas.
Contraejemplo. Si el camino simple más largo de A a B pasa por C, los trozos de A a C y de C a B no tienen por qué ser soluciones óptimas.
Para cada problema debemos comprobar si es aplicable el principio de optimalidad.
Aspectos a estudiar en un algoritmo de programación dinámica:
- ¿Qué parámetros determinan el tamaño del problema?
- Ecuación recurrente (con casos base), para calcular la solución de los problemas grandes en función de los problemas más pequeños.