Programación dinámica
La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas. El matemático Richard Bellman inventó la programación dinámica en 1953.
Una subestructura óptima significa que soluciones óptimas de subproblemas pueden ser usadas para encontrar las soluciones óptimas del problema en su conjunto. En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:
1. Dividir el problema en subproblemas más pequeños.
2. Resolver estos problemas de manera óptima usando este proceso de tres pasos recursivamente.
3. Usar estas soluciones óptimas para construir una solución óptima al problema original.
Los subproblemas se resuelven a su vez dividiéndolos ellos mismos en subproblemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial.
Fuente: Apunte Análisis, diseño e implantación de algoritmos de la facultad de contaduría y administración, UNAM
