Programación dinámica (DP – Dynamic Programming) es una técnica de programación que se puede utilizar en problemas que presentan las siguientes características: el problema puede ser resuelto de manera óptima si sus partes son resueltas de manera óptima, y para resolver el problema necesitamos recalcular una misma parte en varias ocasiones.

La idea básica de la programación dinámica es guardar los resultados de los subproblemas para no tener que volverlos a calcular después. Con esta simple técnica, podemos transformar algoritmos que corren en tiempo exponencial a tiempo polinomial. Este ahorro en tiempo se refleja en un costo en memoria.

Los problemas más comunes que se resuelven mediante esta técnica son los de optimización, donde podemos encontrar muchas soluciones pero requerimos únicamente la mejor (posiblemente la menor o la mayor, según lo que estemos buscando). Como pueden existir varias combinaciones que resulten en la mejor solución, decimos que encontramos una respuesta óptima, y no la respuesta óptima.

Para crear un algoritmo basado en Programación Dinámica, debemos seguir cuatro pasos:

•   Identificar y comprobar que el problema puede ser resuelto de forma óptima mediante la solución de subproblemas.
•    Encontrar la relación recursiva entre el problema y los subproblemas.
•    Calcular el problema mediante tablas (generalmente un arreglo o una matriz). Esto se puede hacer de dos formas: empezando con el problema general y descomponiéndolo en subproblemas (enfoque “arriba-abajo” o “top-down”), o comenzando con los subproblemas base e ir construyendo a partir de estos la solución del problema (enfoque “abajo-arriba” o “bottom-up”).
•    Construir la solución óptima a través de las tablas. Esto no es necesario cuando sólo queremos la solución, y no requerimos saber como se obtuvo.

A continuación mencionaremos los elementos que identifican a los algoritmos de programación dinámica.

•    Subestructura óptima: Esto implica que para poder resolver el problema de forma óptima, cualquier subparte del problema también necesita ser resuelto de forma óptima. Si está condición se cumple, también existe la posibilidad de que un algoritmo ávido sea útil (sección 11.6).
•    Empalme de subproblemas: La ventaja principal de la programación dinámica es que al tener los resultados de los subproblemas en una tabla, podemos buscarlos en tiempo constante. Para poder aprovechar esto, necesitamos que al resolver los subproblemas sea preciso emplear resultados anteriores, y que la cantidad de subproblemas no sea excesivamente grande (para poder crear las tablas).
•    Memorización (“Memoization”): Esto se utiliza para pasar de un algoritmo recursivo a uno de programación dinámica. Lo que hacemos es utilizar el mismo algoritmo, y agregamos el uso de la tabla. Cuando requerimos un valor, primero lo buscamos en la tabla, y en caso de que no lo tengamos, lo buscamos recursivamente (este sería el enfoque arriba-abajo).

Un enfoque “abajo-arriba” es más efectivo cuando toda (o casi toda) la tabla va a ser utilizada, mientras que el enfoque “arriba-abajo” es más útil cuando sólo algunos subproblemas guardados en la tabla necesitan ser resueltos. El uso de estos enfoques no cambian la complejidad del algoritmo, simplemente son más eficientes por un valor constante.

Un ejemplo sencillo de lo eficiente de la programación dinámica se puede observar al calcular los números de Fibonacci (sección 5.6). Aunque en este caso no es un problema de optimización, aprovecha el uso de tablas para transformar la solución recursiva de un tiempo exponencial a uno lineal.