🧮 Programación Dinámica

…

Pruébalo: Observa cómo se llena la tabla 1-D de izquierda a derecha — cada celda es solo la suma de las dos anteriores. Un valor que la recursión ingenua recalcularía miles de millones de veces se lee una sola vez de la celda vecina. Ese cambio — recalcular → consultar — es toda la idea.

Por qué importa

Un sorprendente número de problemas "exponenciales" son secretamente polinómicos — solo parecen exponenciales porque la recursión obvia resuelve el mismo subproblema millones de veces. La programación dinámica es la técnica de notar la repetición y almacenarla en caché. Una vez que ves el patrón, problemas que tardarían siglos colapsan a milisegundos.

En robótica es la base de la iteración de valor, la iteración de política, las recursiones de Bellman y los algoritmos de camino más corto que ya conociste. En cadenas de texto es el algoritmo de diferencias (diff) que usa git. En bioinformática es cómo funciona toda herramienta de alineamiento de secuencias.

La idea

Un problema con forma de DP (programación dinámica) tiene dos propiedades:

1. Subestructura óptima — la respuesta óptima al problema completo puede construirse a partir de las respuestas óptimas a versiones más pequeñas del mismo problema.
2. Subproblemas superpuestos — esas versiones más pequeñas se repiten. La recursión ingenua resolvería la misma muchas veces.

Cuando ambas se cumplen, el truco es resolver cada subproblema exactamente una vez y guardar el resultado. Dos variantes:

• Memoización (de arriba hacia abajo): mantén la recursión; almacena en caché el valor de retorno de cada llamada. La primera vez que llegas a f(7) lo calculas; en adelante lees la caché.
• Tabulación (de abajo hacia arriba): elimina la recursión por completo. Llena un arreglo (o una tabla 2D) desde los subproblemas más pequeños hasta el completo. El valor de cada celda es función de celdas que ya llenaste.

Ambas son O(estados × trabajo-por-estado). La memoización está más cerca de la recurrencia natural; la tabulación te da un control más fino sobre el espacio y el orden.

Puntos clave

• DP = recursión + una caché que asegura que cada subproblema se resuelva una sola vez.
• Lo más difícil es encontrar el estado — ¿qué necesita saber f(i, j, k…) para producir su respuesta?
• Una vez que la recurrencia es correcta, la complejidad temporal es (n.º de estados) × (trabajo por estado).
• Los problemas 1D a menudo colapsan de espacio O(n) a O(1) conservando solo las últimas celdas (técnica de "deslizamiento").
• Los problemas 2D a menudo colapsan de O(m·n) a O(min(m, n)) conservando solo una fila a la vez.

Profundizando

Reconocer una forma de DP

Cinco preguntas que hacerle a cualquier problema que sospeches que es DP:

1. ¿Puedo describir la respuesta recursivamente? "El costo mínimo para llegar al estado X es igual al mínimo, entre las opciones Y, de …"
2. ¿Cuál es el estado? ¿Un solo entero? ¿Un par (i, j)? ¿Un índice más una bandera?
3. ¿Cuál es la recurrencia? ¿Cómo se descompone f(estado) en f(estado-más-pequeño)?
4. ¿Cuáles son los casos base? Los estados más pequeños cuya respuesta se conoce sin recursión.
5. ¿En qué orden debo llenar la tabla? Cualquier orden donde las dependencias de cada celda estén llenas antes que ella.

Si puedes responder las cinco, puedes escribir la DP. Si no puedes, todavía no tienes un problema de DP — vuelve a reformularlo.

Memoización vs tabulación — cuándo elegir cuál

| | Memoización | Tabulación | |---|---|---| | Modelo mental | De arriba hacia abajo: confía en la recursión | De abajo hacia arriba: construye pieza por pieza | | Implementación | Función recursiva + caché | Bucle que llena un arreglo | | Subproblemas resueltos | Solo los alcanzables | Todos ellos | | Riesgo de pila | Recursión profunda → desbordamiento de pila | Ninguno | | Potencial de optimización de espacio | Más difícil | Fácil (filas deslizantes / "los dos últimos valores") |

Elige la memoización cuando el espacio de estados es disperso — existen muchos estados pero la respuesta solo depende de un pequeño conjunto alcanzable. Elige la tabulación cuando de todos modos tocarás la mayor parte del espacio de estados, o cuando necesitas optimizar el espacio.

Optimización de espacio — el truco del "deslizamiento"

La mayoría de las recurrencias de DP solo dependen de la fila inmediatamente anterior o de una cantidad constante de celdas previas. Así que no necesitas la tabla completa.

• Fibonacci necesita solo f(n-1) y f(n-2) → espacio O(1).
• La LCS sobre m × n solo depende de la fila anterior → espacio O(min(m, n)).
• La mochila (knapsack) necesita solo la columna de capacidad anterior → espacio O(W).

Observa la recurrencia: si f(i) solo usa f(i-1), f(i-2), …, f(i-k) para un k pequeño, puedes conservar solo esos k valores e ir deslizándote.

Anclaje en robótica — DP es Bellman es iteración de valor

La ecuación de Bellman en aprendizaje por refuerzo es literalmente una recurrencia de DP:

V*(s) = max over actions a of [ R(s, a) + γ · Σ P(s' | s, a) · V*(s') ]

El valor óptimo del estado s es igual a la recompensa inmediata más el valor futuro descontado del mejor estado siguiente. La iteración de valor no es más que tabular la recurrencia de Bellman sobre el espacio de estados, iterada hasta la convergencia. Todo solucionador de mundos de cuadrícula (gridworld), todo planificador de rutas que maneja costos, todo controlador MPC del libro de texto — son DP.

Cuándo falla la DP

La DP necesita subestructura óptima. Algunos problemas la violan:

• El camino simple más largo en un grafo general (no hay DP — es NP-difícil).
• Cualquier cosa donde las decisiones futuras dependan de toda la historia, no solo de un estado resumible.

Si no puedes encontrar un estado finito que capture todo lo que los pasos futuros necesitan saber, la DP no aplica.

En la práctica

• Algoritmos de diferencias (git diff, diff -u) calculan la subsecuencia común más larga en O(m·n) — exactamente el tercer problema de abajo.
• La planificación robótica bajo incertidumbre usa iteración de valor / iteración de política — ambas DP pura sobre el espacio de estados.
• El alineamiento de secuencias en biología computacional (Needleman-Wunsch, Smith-Waterman) es DP sobre una tabla de edición 2D.
• El algoritmo de Viterbi del reconocimiento de voz encuentra la secuencia más probable de estados ocultos — DP sobre un enrejado (trellis).
• La asignación de registros en compiladores usa DP sobre árboles de expresiones.
• Los protocolos de enrutamiento (OSPF, selección de rutas de BGP) — Bellman-Ford es DP sobre distancias en grafos.

Detalles matemáticos

Tiempo

O(estados × trabajo-por-estado) — una vez que has elegido una representación del estado, esto es exacto.

Espacio (tabla completa)

O(estados)

Espacio (deslizante)

A menudo O(d) donde d es la "profundidad de retroceso" de la recurrencia — usualmente una pequeña constante o una fila.

Sobrecarga de la memoización

Búsqueda en HashMap + pila de recursión — factor constante de 2-3× sobre un bucle de tabulación ajustado. Vale la pena para espacios de estados dispersos.

Implementación

El esqueleto — toda DP encaja en esta plantilla

def solve():
    memo = {}
    def f(state):
        if state in BASE_CASES: return base_answer
        if state in memo: return memo[state]
        result = combine(f(smaller_state_1), f(smaller_state_2), ...)
        memo[state] = result
        return result
    return f(initial_state)

O, tabulado:

def solve():
    dp = [base_answer for _ in range(N + 1)]
    for state in range(SMALLEST + 1, LARGEST + 1):
        dp[state] = combine(dp[smaller_1], dp[smaller_2], ...)
    return dp[LARGEST]

Formas clásicas de problemas

• 1D lineal: f(n) = combine(f(n-1), f(n-2)) — Fibonacci, subir escaleras, el ladrón de casas
• 1D no acotado: f(amount) = min over coins of f(amount - coin) + 1 — cambio de monedas, corte de varilla
• 2D: f(i, j) = combine(f(i-1, j), f(i, j-1), f(i-1, j-1)) — LCS, distancia de edición, caminos en cuadrícula
• Intervalos: f(i, j) = min over splits k of f(i, k) + f(k, j) + cost(i, j, k) — cadena de matrices, ABB óptimo
• DP en árboles: recorrido postorden, la respuesta de cada nodo compuesta a partir de las de sus hijos — diámetro, suma máxima de camino

Práctica

Tres problemas que afianzan las tres formas fundamentales de DP:

• Subir escaleras — fácil · forma 1D tipo Fibonacci; la progresión memoización → tabulación → espacio O(1)
• Cambio de monedas — medio · mochila no acotada 1D; recurrencia de "mínimo entre opciones"
• Subsecuencia común más larga — medio · tabla 2D; base de toda herramienta de diferencias (diff)

→ Explora todos los problemas de práctica