Programación dinámica: memoización y tabulación explicadas

La programación dinámica es una forma de resolver problemas guardando respuestas de subproblemas más pequeños y reutilizándolas después. Ayuda cuando los mismos subproblemas vuelven a aparecer y la respuesta completa puede construirse a partir de esas respuestas más pequeñas.

Los dos estilos principales son la memoización y la tabulación. La memoización guarda respuestas durante una solución recursiva. La tabulación completa respuestas en un orden ascendente, normalmente con un arreglo o una tabla.

Cuándo funciona la programación dinámica

La programación dinámica es útil cuando se cumplen dos condiciones.

Primero, los subproblemas se solapan. Eso significa que el mismo resultado intermedio se necesita más de una vez. Segundo, las respuestas más grandes pueden construirse a partir de respuestas más pequeñas de una manera consistente.

Si esas condiciones no se cumplen, guardar resultados anteriores puede añadir coste de memoria sin ayudar demasiado.

Memoización vs. tabulación

Memoización: almacenamiento de arriba hacia abajo

La memoización empieza con la idea recursiva. Cuando el algoritmo resuelve un subproblema por primera vez, guarda el resultado. Las llamadas posteriores reutilizan el valor guardado en lugar de volver a calcularlo.

Este estilo suele ser más fácil cuando la recurrencia está clara pero el orden de todos los estados necesarios no lo está.

Tabulación: construcción de abajo hacia arriba

La tabulación empieza con los casos base y completa los estados en un orden que hace que las dependencias estén disponibles cuando se necesitan.

Este estilo suele ser más fácil cuando ya conoces un orden de iteración limpio y quieres un control explícito sobre la tabla.

Ejemplo de programación dinámica: Fibonacci

La sucesión de Fibonacci se define por

$$F(0) = 0, \quad F(1) = 1$$

y, para $n \ge 2$,

$$F(n) = F(n-1) + F(n-2)$$

Una solución recursiva simple repite trabajo. Por ejemplo, calcular $F(5)$ necesita $F(4)$ y $F(3)$, y luego calcular $F(4)$ necesita $F(3)$ otra vez. Esa llamada repetida a $F(3)$ es el tipo de desperdicio que la programación dinámica elimina.

Memoización en Fibonacci

Con memoización, la recurrencia sigue siendo la misma, pero cada valor se guarda después de calcularse por primera vez.

Para $F(5)$, la secuencia útil es:

• calcular y guardar $F(0)=0$
• calcular y guardar $F(1)=1$
• calcular y guardar $F(2)=1$
• calcular y guardar $F(3)=2$
• calcular y guardar $F(4)=3$
• calcular y guardar $F(5)=5$

La idea clave es que cada estado se calcula una sola vez. Las solicitudes posteriores leen el valor guardado.

Tabulación en Fibonacci

Con tabulación, construyes desde los casos base hacia arriba:

$$\begin{aligned} F(0) &= 0 \\ F(1) &= 1 \\ F(2) &= F(1) + F(0) = 1 \\ F(3) &= F(2) + F(1) = 2 \\ F(4) &= F(3) + F(2) = 3 \\ F(5) &= F(4) + F(3) = 5 \end{aligned}$$

Esta versión hace evidente el orden de dependencias: cada valor nuevo usa entradas que ya se conocen.

Por qué la programación dinámica puede ser más rápida

Si un problema solo tiene $k$ estados distintos que importan, la programación dinámica intenta resolver cada uno de esos $k$ estados una sola vez. Eso puede convertir un gran árbol recursivo en un cálculo mucho más pequeño.

La mejora exacta de velocidad depende del problema. La programación dinámica no es automáticamente rápida. Ayuda cuando el trabajo repetido es una parte real de la solución original.

Errores comunes en programación dinámica

Usarla cuando los subproblemas no se solapan

No todo problema recursivo es un problema de programación dinámica. Si casi todos los subproblemas son diferentes, almacenar resultados puede no ahorrar suficiente trabajo como para importar.

Definir mal el estado

El estado tiene que incluir toda la información necesaria para el siguiente paso. Si falta información importante, la recurrencia puede parecer válida pero producir respuestas incorrectas.

Equivocarse en los casos base

Los casos base sostienen todo el método. Si los valores iniciales son incorrectos, todos los estados posteriores construidos a partir de ellos también lo serán.

Llenar la tabla en el orden incorrecto

La tabulación solo funciona cuando cada estado se completa después de los estados de los que depende. Una recurrencia correcta aún puede fallar si el orden de llenado es incorrecto.

Suponer que la programación dinámica siempre significa optimización

Muchos ejemplos famosos maximizan o minimizan algo, pero la programación dinámica también se usa para problemas de conteo y de decisión. La señal real son los subproblemas reutilizables, no la palabra "mejor".

Dónde se usa la programación dinámica

La programación dinámica aparece en problemas como la distancia de edición, la subsecuencia común más larga, el conteo de caminos, la optimización de tipo mochila y algunos casos de caminos más cortos.

Cuando estés decidiendo si probarla, hazte dos preguntas:

• ¿se repiten los subproblemas más pequeños?
• ¿puede construirse la respuesta más grande a partir de esas respuestas más pequeñas?

Si ambas respuestas son sí, la programación dinámica es una candidata fuerte.

Prueba un problema similar

Prueba tu propia versión con el número de formas de subir $n$ escalones si cada movimiento es de $1$ escalón o de $2$ escalones. La recurrencia es simple, los subproblemas repetidos son fáciles de detectar y es un buen ejemplo siguiente después de Fibonacci.