Programación dinámica: de la recursión a la memorización

La programación dinámica (DP) transforma algoritmos exponenciales O(2ⁿ) en polinomiales O(n²) guardando resultados intermedios. Es la técnica más valorada en entrevistas de alto nivel.

El problema: Fibonacci exponencial

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

# fib(40) tarda segundos. fib(50) tarda minutos.
# Recalcula los mismos valores millones de veces.

Solución 1: Memoización (Top-Down)

from functools import lru_cache

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

# fib(1000) es instantáneo

Solución 2: Tabulación (Bottom-Up)

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

El problema de la mochila (Knapsack)

def mochila(pesos, valores, capacidad):
    n = len(pesos)
    dp = [[0] * (capacidad + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacidad + 1):
            dp[i][w] = dp[i-1][w]
            if pesos[i-1] <= w:
                dp[i][w] = max(dp[i][w], 
                               dp[i-1][w - pesos[i-1]] + valores[i-1])
    
    return dp[n][capacidad]

Cuándo usar DP

El problema debe tener:

1. Subestructura óptima: la solución se construye a partir de subproblemas óptimos
2. Subproblemas solapados: los mismos subproblemas se resuelven múltiples veces

Problemas clásicos: Fibonacci, Knapsack, Longest Common Subsequence, Edit Distance, Coin Change.