Cómo funciona la programación dinámica

Resolver lo mismo de nuevo

La recursión resuelve un problema grande
partiéndolo en chicos.
Fibonacci es justo eso.
fib(5) llama a fib(4) y fib(3),
fib(4) vuelve a llamar a fib(3) y fib(2).
Pero mira de cerca,
y fib(2) sigue apareciendo
en esta rama y en aquella.
En el árbol de abajo,
toca uno de los nodos.

El mismo problema chico aparece por todo el árbol. (Clic en un nodo → todos los mismos valores se resaltan)

¿Lo ves?
El mismo fib(2) se resuelve
no una vez sino varias.
Lo mismo con fib(3).
A medida que n crece,
esta duplicación se dispara.
Resolver una respuesta que ya tienes
una y otra vez
es claramente un desperdicio.

Anota la respuesta

El arreglo es sorprendentemente simple.
Anota una respuesta resuelta
en un bloc de notas.
Cuando la misma se necesita otra vez,
no la recalcules,
solo sácala de la nota.
Calcula solo las nuevas,
saca de nuevo las ya vistas.
Pulsa el botón
para atender las llamadas una a una.

Calcula y anota lo nuevo, saca lo visto de la nota. (Esto es memoización)

El cálculo ocurre solo la primera vez.
Todo lo demás
se saca de la nota,
así que resolver lo mismo dos veces
desaparece por completo.
Anotar una respuesta resuelta
y reúsala así
se llama memoización.
El nombre suena elegante,
pero por dentro es solo "anotarlo".

Llenar la tabla desde abajo

Puedes voltear la misma idea
al revés.
En vez de partir desde arriba,
llena la tabla hacia arriba
desde los valores chicos de abajo.
fib(0) y fib(1) simplemente los sabemos.
Súmalos para fib(2),
suma fib(1) y fib(2) para fib(3).
Las celdas de abajo ya están escritas,
así que la de arriba es solo una suma.

Llena hacia arriba una celda desde 0 y 1. (Celda siguiente = suma de las dos de abajo · de abajo hacia arriba)

Esta vía ni siquiera necesita
un bloc de notas.
La tabla misma es la nota.
Ve de abajo hacia arriba
en una sola pasada,
y no hay nada que volver a resolver.
Si la memoización es
"anótalo cuando haga falta,"
esto es "anótalo todo de antemano."
Ambas significan lo mismo por dentro.

Se vuelve mucho más rápido

¿Y cuánto más rápido es?
La diferencia de un solo gesto,
anotarlo, es enorme.
La recursión pura
resuelve también todos los duplicados,
así que a medida que n crece
el trabajo explota hacia arriba.
El memo resuelve cada celda una sola vez,
solo en proporción a n.
Aumenta n y compara ambos.

Resoluciones al mismo n. (Recursión pura = estallido exponencial · memo = lineal en n)

¿Ves la diferencia?
Con apenas un poco más de n,
la barra de recursión pura
se dispara fuera de la pantalla.
La barra del memo
se queda casi plana.
No resolver la misma respuesta otra vez,
esa sola cosa
es lo que separa lo lento de lo rápido.

Para cerrar

La programación dinámica
tiene un nombre que asusta
pero por dentro son tres pasos.
Nota que resuelves lo mismo,
anota una respuesta resuelta,
reúsala y se vuelve mucho más rápido.
Toca las tarjetas de abajo una a una
para repasar los tres pasos.

Resolver de nuevo → anotar → mucho más rápido. (Recuerda que el divide y vencerás no se traslapaba, sin necesidad de memo)

En el divide y vencerás de la vez pasada,
las piezas partidas no se traslapaban,
así que no había nada que anotar.
Ese es justo el cruce de caminos.
Cuando las piezas se traslapan,
es decir, cuando el mismo problema chico
sigue regresando,
ahí es cuando el solo gesto
de anotarlo lo cambia todo.