Algoritmos

PD – Algoritmos Voraces
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
Elmatemático Richard Bellman inventó la programación dinámica en 1953 que se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados
La programación toma normalmenteuno de los dos siguientes enfoques:
Top-down: El problema se divide en subproblemas, y estos se resuelven recordando las soluciones por si fueran necesarias nuevamente. Es una combinaciónde memorización y recursión.
En el modelo Top-down se formula un resumen del sistema, sin especificar detalles. Cada parte del sistema se refina diseñando con mayor detalle. Cada parte nueva es entonces redefinida,cada vez con mayor detalle, hasta que la especificación completa es lo suficientemente detallada para validar el modelo. El modelo "Top-down" se diseña con frecuencia con la ayuda de "cajas negras"que hacen más fácil cumplir requerimientos aunque estas cajas negras no expliquen en detalle los componentes individuales.
Bottom-up: Todos los problemas que puedan ser necesarios se resuelven deantemano y después se usan para resolver las soluciones a problemas mayores. Este enfoque es ligeramente mejor en consumo de espacio y llamadas a funciones, pero a veces resulta poco intuitivo encontrartodos los subproblemas necesarios para resolver un problema dado.
En contraste, en el diseño Bottom-up las partes individuales se diseñan con detalle y luego se enlazan para formar componentes másgrandes, que a su vez se enlazan hasta que se forma el sistema completo. Las estrategias basadas en el flujo de información "bottom-up" se antojan potencialmente necesarias y suficientes porque se basanen el conocimiento de todas las variables que pueden afectar los elementos del sistema.
Sucesión de Fibonacci
Coeficientes binomiales
El viaje más barato por el río
Problema de las monedas...