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.
Una subestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en su conjunto. En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:
Los subproblemas se resuelven a su vez dividiéndolos en subproblemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial.
Puedes encontrar más información aquí.
A continuación se muestran algunos ejemplos. Puedes acceder a ellos desde el menú de la parte superior.
Se trata de la implementación de una función que encuentra el n-ésimo término de la sucesión de Fibonacci basada directamente en la definición matemática de dicha sucesión, realizando llamadas recursivas, obteniéndose una complejidad exponencial.
Dado un conjunto de N tipos de monedas cada una de ellas con un valor determinado, este algoritmo calcula el número mínimo de monedas que necesitamos para devolver una cantidad C.
Se tiene una mochila con una capacidad máxima V y n objetos con volúmenes \(v=(v_1,v_2,\dots,v_n)\) y beneficios \(b=(b_1,b_2,\dots,b_n)\) . Los valores de los volúmenes son enteros. El objetivo de este problema es encontrar una selección de objetos cuya suma de volúmenes no supere la capacidad máxima de la mochila, y de forma que la suma de beneficios sea máxima. Por lo tanto, es un problema de optimización con restricciones.