Los algoritmos DyC parten el problema en subproblemas disjuntos, los resuelven y luego los combinan para resolver el problema original. En cambio, los algortimos de programación dinámica son especialmente útiles cuando los subproblemas comparten subsubproblemas (es decir, solapan entre sí). Los algoritmos de programación dinámica resuelven cada subproblema una única vez y guardan su resultado en una estructura de memoización.

Los algoritmos de programación dinámica utilizan memoria adicional para ahorrarse tiempo de cómputo, son un ejemplo del trade-off complejidad-memoria.

Cómo desarrollamos un algoritmo de programación dinámica

1. Caracterizamos la estructura de una solución óptima

2. Definimos recursivamente el valor de una solución óptima

   Este paso suele dividirse en dos partes: primero hacemos una función recursiva naive y luego, de ser posible, la mejoramos para generar la mínima cantidad de subproblemas.

3. Computamos el valor de una solución óptima

4. Construimos una solución óptima en base a lo computado anteriormente (reconstrucción de la solución)

Enfoques top-down y bottom-up

Existen dos enfoques al implementar un algoritmo de programación dinámica:

• Top-down: Escribimos la función recursiva de la manera tradicional, pero en vez de devolver el resultado lo guardamos en una estructura de datos. Cada vez que el procedimiento es llamado con un set de argumentos, primero se fija si el resultado ya fue computado anteriormente. Si lo fue devuelve el valor que tiene guardado, sino lo computa. A esta estrategia de guardar los resultados previamente computados la llamamos memoización.
• Bottom-up: Esta forma suele depender de una noción de tamaño de los subproblemas, tal que resolver una instancia particular sólo depende de resolver intancias “más chicas”. Entonces, ordenamos los subproblemas de acuerdo a esta noción de orden y los resolvemos de menor a mayor. Al momento de resolver un subproblema dado, ya resolvimos todos los subproblemas necesarios para resolverlo y guardamos sus soluciones. De esta manera sólo resolvemos cada subproblema una vez.

En la gran mayoría de los casos, ambos enfoques tienen la misma complejidad temporal asintótica. En general, las implementaciones bottom-up tienen factores constantes más pequeños gracias a que se ahorran el overhead de las múltiples llamadas recursivas.

Si todos los subproblemas deben ser resueltos al menos una vez el enfoque bottom-up es preferible, ya que los factores constantes en su complejidad temporal son más pequeños. Por el contrario, si algunos de los subproblemas en el espacio de subproblemas no necesitan ser resueltos, el enfoque top-down nos asegura que sólo resolveremos los subproblemas que necesitamos para construir una solución óptima al problema general.

Grafo de subproblemas

Para analizar un algoritmo de programación dinámica podemos mirar su grafo de subproblemas: