Programación Dinámica

PROGRAMACION DINAMICA
DEFINICION
Es una técnica que parte del principio de no calcular dos veces la misma información, por lo tanto se utilizan estructuras de almacenamiento como vectores, tablas,arreglos, archivos, con el fin de almacenarlos resultados parciales, que contribuyan a la solución final.
Este algoritmo evita calcular dos veces la misma información, manteniendo una tabla deresultados conocidos, la cual se va llenando a medida que se resuelven los sub-casos. Es una técnica ascendente que normalmente, empieza por los sub-casos más pequeños y más sencillos. Combinando sussoluciones, obtenemos las respuestas para los sub-casos cada vez mayores, hasta que llegamos a la solución del caso original.
La programación dinámica se aplica no solo por razones de eficiencia, sinoporque permite resolver de manera eficiente problemas que no se pueden resolver por otras metodologías.
El mayor número de aplicaciones se encuentra en problemas que requieren optimización, ya que sepueden hallar múltiples soluciones y así evaluarlas para hallar la óptima.
 
FORMA GENERAL
La forma general de las soluciones desarrolladas mediante programación dinámica requiere de los siguientespasos:
1. planteamiento de la solución, mediante una serie de decisiones que garanticen que la solución será óptima.
2. Encontrar una solución recursiva de la definición.
3. Calcular la soluciónteniendo en cuenta una tabla en la que se almacenen soluciones a problemas parciales para su reutilización y así evitar el nuevo cálculo.
4. Encontrar la solución óptima utilizando la informaciónpreviamente calculada y almacenada en las tablas.
PROBLEMAS CLASICOS
Programación Dinámica
CALCULAR EL FACTORIAL DE UN NÚMERO

Que se implementa fácilmente con un ciclo así: Que se implementafácilmente con un ciclo así:

Algoritmo factorial(n)
Inicio
 
 
Fac ← 1
Para x desde 1 hasta n haga
 
 
 
Fac ←fac * x
 
 
Finpara
Regresar Fac
 
Fin
 
 
cuya implementación en...