Programacion Dinamica

PROGRAMACIÓN DINÁMICA
Yanín arias torres
La programación dinámica así como la técnica de divide y vencerás es utilizada para resolver problemas dividiéndolos en diferentes subproblemas. Pero, adiferencia de la técnica divide y vencerás el algoritmo que use programación dinámica resolverá los problemas y guardara los resultados en una tabla de esta manera no realizara cálculos innecesariosmás adelante.
La programación dinámica tiene una mayor aplicación en la resolución de problemas de optimización, en los cuales se busca una solución con un valor óptimo (máximo o mínimo), entre lasmuchas soluciones con valor óptimo que pueden existir.
Existen dos condiciones para que deba ser utilizada esta técnica.
1. La solución al problema ha de ser alcanzada a través de una secuenciade decisiones, una en cada etapa.
2. Dicha secuencia de decisiones ha de cumplir el principio de óptimo.
El desarrollo de un algoritmo utilizando la técnica de programación dinámica es divididoen diferentes pasos
1. Caracterizar la estructura de una solución optima.
2. Definir recursivamente el valor de una solución optima.
3. Calcular el Valor de una solución óptima de maneraabajo hacia arriba (bottom-up).
4. Construir una solución optima a partir de la información calculada.

A continuación como resolver la serie fibonacci aplicando la técnica de programacióndinámica.

Sucesión de Fibonacci
Esta sucesión puede expresarse mediante la siguiente recurrencia:

Una implementación de una función que encuentre el n término de la sucesión de Fibonacci basadadirectamente en la definición matemática de la sucesión realizando llamadas recursivas hace mucho trabajo redundante, obteniéndose una complejidad exponencial:-------------------------------------------------
FUNC fib(↓n: NATURAL): NATURAL
-------------------------------------------------
INICIO
-------------------------------------------------...