Toda solución de programación dinámica evita usar una solución top-down recursiva que directamente traduzca a un algoritmo la ecuación recurrente correspondiente al problema. Esto es así porque, normalmente, el coste en tiempo de esa solución es extremadamente alto pues resuelve muchas veces los mismos subproblemas.

Para evitar resolver muchas veces los mismos subproblemas, un algoritmo de programación dinámica utiliza siempre una tabla auxiliar, en la que se almacenan las soluciones de los subproblemas conforme se van resolviendo.

Dicho esto, hay dos formas distintas de implementar la solución de programación dinámica:

• Solución de abajo arriba (bottom-up) iterativa, en la que se van resolviendo todos los subproblemas y rellenando la tabla en un cierto orden, iterativamente, en primer lugar resolviendo los casos base de la recursión y después el resto de los casos aplicando la ecuación recurrente “ordenadamente”, de manera que cuando se necesiten las soluciones de ciertos subproblemas (en cierto sentido, “más pequeños”) para resolver otros, éstas hayan sido resueltas y almacenadas en la tabla con anterioridad en el(los) bucle(s) correspondiente(s) del algoritmo. Ejemplos de estas soluciones son las de los problemas de la mochila 0-1, el camino de coste mínimo en un grafo multietapa o la multiplicación de una secuencia de matrices, vistas ya en clase.
• Solución (recursiva) de arriba abajo (top-down) con memorialización (memoization), en la que se aplica directamente la ecuación recurrente, como en la solución top-down recursiva (mencionada antes y descartada por muy ineficiente), pero cada vez que se resuelve un subproblema, se almacena su solución en la tabla auxiliar para evitar volver a resolverlo de nuevo más adelante. De esta forma, lo primero que hace el algoritmo es averiguar si el subproblema ha sido ya resuelto consultando la tabla, y sólo si no se ha resuelto todavía, se aplica la ecuación recurrente para resolverlo (de forma recursiva). Un ejemplo de este tipo de solución es la del problema del viajante de comercio, vista ya en clase.

El coste asintótico de ambos métodos suele ser el mismo, salvo en algunos casos (poco frecuentes) en los que la solución de arriba abajo no necesita resolver todos los subproblemas de la tabla. En general, la solución de abajo arriba ofrece mejores resultados prácticos al tener constantes multiplicativas más pequeñas, pues se evita el sobrecoste provocado por las llamadas recursivas. Por eso recomendamos, siempre que sea posible, plantear una solución de abajo arriba iterativa.

Lectura adicional (acceso restringido): ejemplo del recorte óptimo de varillas y sus dos soluciones de programación dinámica (arriba abajo con memorialización versus abajo arriba iterativa), del libro [CLRS09].