mini

Desarrollo
¿Qué es la Programación Dinámica?

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 comovectores, tablas, arreglos, archivos, con el fin de almacenarlos resultados parciales, que contribuyan a la solución final.
Es una técnica ascendente que normalmente, empieza por los sub-casos máspequeños y más sencillos. Combinando sus soluciones, obtenemos las respuestas para los sub-casos cada vez mayores, hasta que llegamos a la solución del caso original.
El mayor número de aplicaciones seencuentra en problemas que requieren optimización, ya que se pueden hallar múltiples soluciones y así evaluarlas para hallar la óptima

Es un enfoque general para la solución de problemas en los quees necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura de un sistema, afectando a las situaciones en las que el sistema se encontraraen el futuro denominadas estados y a las decisiones que se plantearan en el futuro.

Conviene resaltar que a diferencia de la programación lineal, el modelado de problemas no sigue una formaestándar. Así, para cada problema Será necesario especificar cada uno de los componentes que caracterizan un problema de programación dinámica.

El procedimiento general de resolución de estas situacionesse divide en el análisis recursivo de cada una de las etapas del problema, en orden inverso, es decir comenzando por la última y pasando en cada iteración a la etapa antecesora.

La programacióndinámica es un método ascendente. Se resuelven primero los subejemplares más pequeños y por tanto más simples. Combinando las soluciones se obtienen las soluciones de ejemplares sucesivamente más grandeshasta llegar al ejemplar original.
Ejemplo:

    Consideremos el cálculo de números combinatorios. El algoritmo sería:

    funcion C(n, k)
        si  k=0 o k=n entonces devolver 1
       ...