Programación dinámica: DP y memoización

Al finalizar este tema

Podrás identificar situaciones en las que se requiere la programación dinámica y resolver problemas mediante dos enfoques: de arriba hacia abajo (memoización) y de abajo hacia arriba (tabulación).

Problemas con cálculos repetidos

Si implementamos la secuencia de Fibonacci utilizando la recursión:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(35))  # 9227465 — aproximadamente 4 segundos
print(fib(50))  # ... no termina

Al calcular fib(5), la función fib(3) se llama dos veces y la función fib(2) se llama tres veces. Si se cumple la condición fib(50), las llamadas duplicadas pueden llegar a ser de miles de millones.

fib(5)
├── fib(4)
│   ├── fib(3)        ← calculado aquí también
│   │   ├── fib(2)
│   │   └── fib(1)
│   └── fib(2)        ← calculado de nuevo
└── fib(3)            ← calculado de nuevo
    ├── fib(2)        ← calculado de nuevo
    └── fib(1)

Complejidad temporal: O(2^n). Si se almacenan las respuestas ya calculadas, este problema se resuelve.

Condiciones de la programación dinámica

Para aplicar la programación dinámica, se requieren dos condiciones:

1. Subproblemas superpuestos

El mismo subproblema pequeño se repite varias veces. Como en el caso de Fibonacci fib(3).

2. Estructura óptima

La solución óptima de un problema grande se compone de las soluciones óptimas de sus subproblemas más pequeños. Como en el caso de fib(n) = fib(n-1) + fib(n-2).

Si se cumplen ambas condiciones, se puede aplicar la programación dinámica. Si alguna no se cumple, se debe utilizar otro método (como el algoritmo voraz o el de divide y vencerás).

Enfoque de arriba hacia abajo: memoización

Se mantiene la recursión "de arriba hacia abajo", pero se almacenan los resultados calculados en un diccionario (o arreglo):

def fib(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print(fib(50))   # 12586269025 — completado inmediatamente
print(fib(100))  # 354224848179261915075

fib(50) cambia de 4 segundos a inmediatamente. Dado que cada fib(k) se calcula solo una vez, la complejidad temporal es O(n).

En Python, se puede escribir de forma más clara con functools.lru_cache:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Un solo decorador implementa la memoización.

Enfoque ascendente — Tabulación

Resolvemos los problemas más pequeños en orden, avanzando "de abajo hacia arriba":

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Dado que no se utiliza la recursión, no existe el riesgo de desbordamiento de pila. fib(10000) tampoco representa un problema.

Optimización del espacio: en el caso de Fibonacci, solo se necesitan los dos valores anteriores, por lo que:

def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Tiempo O(n), espacio O(1).

Enfoque descendente vs. enfoque ascendente

Por lo general, el enfoque ascendente es ligeramente más rápido (sin sobrecarga de llamadas a funciones) y facilita la optimización del espacio. Sin embargo, convertir una relación de recurrencia en un bucle no siempre resulta intuitivo, por lo que la elección depende del contexto.

Problema clásico: Subir escaleras

Hay n escalones y puedes subir 1 o 2 pasos a la vez. ¿De cuántas formas distintas se puede llegar a la cima?

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1  # 1 paso: 1 forma
    dp[2] = 2  # 2 pasos: 1+1 o 2, 2 formas
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(climb_stairs(5))   # 8
print(climb_stairs(10))  # 89

Para llegar a la casilla i, se puede avanzar una casilla desde (i-1) o dos casillas desde (i-2). dp[i] = dp[i-1] + dp[i-2] — Tiene una estructura similar a la secuencia de Fibonacci.

Problema representativo: Problema de la mochila 0-1

Capacidad de la mochila: W, número de objetos: n. Cada objeto se puede incluir o no (0-1). Maximizar la suma de los valores:

def knapsack(W, items):
    n = len(items)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight, value = items[i - 1]
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]  # caso de no incluir
            if w >= weight:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight] + value)

    return dp[n][W]

items = [(2, 3), (3, 4), (4, 5), (5, 6)]  # (peso, valor)
print(knapsack(8, items))  # 10

dp[i][w] representa el "valor máximo al llenar una capacidad w utilizando los primeros i objetos". Para cada objeto, se registra el valor máximo entre las dos opciones: "incluirlo" o "no incluirlo".

Patrón de resolución de problemas de programación dinámica (DP)

1. Definición del estado: Aclarar qué significa dp[i].
2. Derivación de la ecuación de recurrencia: Expresar dp[i] en términos de estados anteriores.
3. Configuración de los valores iniciales: Determinar las respuestas para el caso base (el problema más pequeño).
4. Determinación del orden: Decidir en qué orden llenar la tabla.
5. Extracción del resultado: Obtener la respuesta de dp[n] o max(dp).

En las pruebas de codificación, muchos problemas que preguntan por el "número de casos", el "mínimo/máximo" o la "posibilidad" son de programación dinámica. Si el tamaño de entrada es de cientos a miles, considere la posibilidad de una DP con complejidad O(n²).

Diferenciación de problemas que no son de DP

Tanto la DP como el algoritmo voraz aprovechan la "subestructura óptima", pero el algoritmo voraz avanza en una sola dirección sin retroceder, mientras que la DP registra los resultados de todas las opciones en una tabla.

Idea clave: La programación dinámica es la estrategia de "no repetir cálculos". Se implementa de dos maneras: memoización (de arriba hacia abajo, recursión + caché) y tabulación (de abajo hacia arriba, bucles + tabla), transformando O(2^n) en O(n) u O(n²).