Algoritmia/Programación dinámica

La programación dinámica puede verse como una optimización de otros métodos algorítmicos (Divide y vencerás, Vuelta atrás, ...) en los que una solución a un problema puede implicar la repetición continua de subproblemas. En concreto, la programación dinámica suele implicar la utilización de una tabla auxiliar donde almacenar las soluciones a los subproblemas ya calculados, de tal forma que cada subsolución se calcule una única vez, reduciendo así el coste en tiempo a cambio de coste en espacio (almacenamiento en memoria de la tabla).

El término dinámico proviene de que la tabla auxiliar se rellena en tiempo de ejecución. No debe confundirse la programación dinámica en el ámbito algorítmico con los lenguajes de programación dinámicos, como Scheme o Lisp.