Cómo funciona la programación dinámica

Resolver lo mismo otra vez

La recursión resuelve un problema grande partiéndolo en problemas más pequeños, y Fibonacci es el ejemplo perfecto.
fib(5) llama a fib(4) y a fib(3), y fib(4) llama a fib(3) y a fib(2). Pero si te fijas bien, fib(2) aparece una y otra vez en una rama tras otra.
Toca un nodo del árbol de abajo para comprobarlo.

El mismo problema pequeño aparece por todo el árbol. (toca un nodo → se resaltan todos los que tienen el mismo valor)

El mismo fib(2) se resuelve no una vez, sino varias, y lo mismo pasa con fib(3).
Cuando n crece, esta repetición se infla de forma alarmante.
Resolver una y otra vez una respuesta que ya tienes es, a todas luces, un desperdicio.

Apuntar las respuestas

La solución es sorprendentemente sencilla: apuntar en una nota cada respuesta una vez resuelta.
La próxima vez que necesites lo mismo, no lo vuelvas a calcular; tómalo de la nota. Calcula solo lo que ves por primera vez y reutiliza lo que ya has visto.
Toca el botón para atender las llamadas una a una.

Lo nuevo se calcula y se apunta; lo ya visto se toma de la nota. Esto es la memoización.

Cada valor se calcula una sola vez, la primera. Todo lo demás sale directamente de la nota, así que resolver lo mismo dos veces desaparece por completo.
Apuntar las respuestas resueltas y reutilizarlas así se llama memoización.
El nombre suena pomposo, pero en el fondo es solo «apuntarlo».

Llenar una tabla de abajo arriba

También se puede aplicar la misma idea al revés. En vez de partir de arriba abajo, se llena una tabla hacia arriba, empezando por los valores más pequeños de abajo.
fib(0) y fib(1) se conocen sin más. Sumándolos sale fib(2), y sumando fib(1) y fib(2) sale fib(3).
Como las casillas de abajo ya están escritas, cada casilla de arriba es solo una suma.

Llena hacia arriba casilla por casilla, empezando por 0 y 1. (siguiente casilla = suma de las dos casillas justo debajo · de abajo arriba)

De esta forma ni siquiera hace falta una nota aparte, porque la tabla misma es la nota.
Basta con recorrerla una vez de abajo arriba, en orden, y nunca hay nada que volver a resolver.
Si la memoización es «apuntar cuando hace falta», esto es «apuntarlo todo de antemano». La idea de fondo es la misma.

Muchísimo más rápido

¿Y cuánto más rápido se vuelve? Solo con apuntar las cosas, la diferencia es enorme.
La recursión pura resuelve incluso los repetidos, así que su trabajo explota a medida que crece n. Con memoización, cada casilla se resuelve exactamente una vez, y el trabajo crece solo en proporción a n.
Si haces crecer n y comparas las dos, la diferencia salta a la vista.

Número de veces que se resuelve con el mismo n. (recursión pura = explota de forma exponencial · memo = lineal, proporcional a n)

Con que n crezca un poco, la barra de la recursión pura se dispara como si fuera a atravesar la pantalla, mientras que la de la memo apenas se mueve.
No volver a resolver la misma respuesta: esa sola cosa separa lo lento de lo rápido.

Resumen

La programación dinámica tiene un nombre difícil, pero en el fondo son tres pasos.
Darse cuenta de que se resuelve lo mismo otra vez, apuntar cada respuesta una vez resuelta y reutilizarla, con lo que todo se vuelve muchísimo más rápido.
Toca las tarjetas de abajo una a una para resumir los tres pasos.

Resolver lo mismo otra vez → apuntarlo → muchísimo más rápido. También recuerda por qué en divide y vencerás, cuyos trozos nunca se superponen, no hacía falta apuntar nada.

En divide y vencerás, que vimos antes, los trozos partidos no se superponían, así que no había nada que apuntar.
Ahí está justamente la bifurcación. Cuando los trozos se superponen, es decir, cuando el mismo problema pequeño reaparece una y otra vez, la sencilla jugada de apuntar lo cambia todo.