Fundamentos de programación dinámica

Qué cubre este capítulo

Divide y vencerás daba por hecho que los subproblemas eran independientes. Muchos problemas importantes rompen esa suposición: sus subproblemas se traslapan, la misma instancia pequeña se necesita una y otra vez, y la recursión simple la vuelve a resolver una cantidad exponencial de veces. La programación dinámica es la solución, y toda su idea cabe en una frase: calcula cada subproblema distinto una sola vez y recuerda la respuesta. Ese único movimiento — una tabla, o un cache — convierte algoritmos exponenciales en polinomiales. Este capítulo construye el paradigma sobre el cambio con el mínimo de monedas (justo el problema donde greedy falló el capítulo pasado — con monedas {1,3,4}, greedy arma 6 como 4+1+1 mientras que el óptimo es 3+3), mostrando la misma recurrencia de tres formas: recursión ingenua (exponencial), memoización top-down y tabulación bottom-up. Medimos la explosión que la programación dinámica evita — con monto 20, la versión ingenua hizo 641 veces más llamadas que unidades de trabajo hace la DP — y animamos la tabla llenándose, la imagen que vuelve concreto eso de "recuerda tus subproblemas".

Un poco de historia

Richard Bellman acuñó "programación dinámica" en los años cincuenta en RAND, y el nombre es, célebremente, una cortina de humo. Bellman trabajaba bajo un Secretario de Defensa que, según escribió, "tenía un miedo y un odio patológicos a la palabra 'investigación'"; así que Bellman eligió un nombre que sonara impresionante e imposible de objetar — "programación" en los cincuenta significaba planeación/calendarización (como en programación lineal), y "dinámica" transmitía decisiones multietapa que varían en el tiempo. Las matemáticas de fondo son su principio de optimalidad: la cola de una solución óptima es a su vez óptima para el subproblema que enfrenta, que es exactamente la "subestructura óptima" que hace válida la recurrencia. Bellman-Ford (el algoritmo de caminos más cortos de dos niveles atrás) es suyo, y es programación dinámica sobre grafos. El paradigma resultó ser uno de los más ampliamente aplicables en computación — alineamiento de secuencias en biología, reconocimiento de voz, teoría de control, reinforcement learning (la ecuación de Bellman es la base de Q-learning) — todo derivado de la idea de que los subproblemas traslapados deben resolverse una vez y recordarse.

La intuición

Piensa en calcularlo a la mala. Para encontrar el mínimo de monedas para un monto a, pruebas cada moneda c y buscas recursivamente el mínimo de monedas para a − c, quedándote con el mejor. La recursión es correcta pero catastróficamente desperdiciada, porque los mismos submontos se repiten en ramas distintas: calcular la respuesta para 6 necesita la respuesta para 5, 3 y 2; calcular la de 5 también necesita 2; y así. La ilustración clásica es Fibonacci — fib(n) = fib(n-1) + fib(n-2) — donde fib(5) calcula fib(3) dos veces, fib(2) tres veces, fib(1) cinco veces, y el recálculo se multiplica hasta que el algoritmo ingenuo es exponencial, O(φⁿ), para un problema que en el fondo es lineal. Los subproblemas se traslapan, y la recursión ingenua es ciega a eso.

La programación dinámica le quita la venda. Hay dos caminos equivalentes. La memoización top-down conserva la recursión natural pero le agrega un cache: antes de resolver un subproblema, revisa si ya lo resolviste, y si sí, regresa la respuesta guardada. Cada subproblema distinto se calcula una vez; el resto son consultas. La tabulación bottom-up invierte la dirección: en lugar de bajar recursivamente desde la meta, llenas una tabla empezando por los subproblemas más chicos y construyendo hacia arriba, donde cada entrada usa solo entradas ya calculadas. Para el cambio de monedas, dp[a] = 1 + min sobre monedas c de dp[a-c], llenado desde dp[0] = 0 hacia arriba. Ambos calculan cada uno de los amount subproblemas una vez, dando O(amount × número de monedas) — polinomial donde la recursión ingenua era exponencial. Los dos estilos tienen su trade-off: top-down se parece más a la recurrencia y solo calcula subproblemas alcanzables; bottom-up evita el overhead de la recursión y hace explícito el orden. Mismas respuestas, misma complejidad, y la transformación desde la versión ingenua es puramente agregar memoria.

Complejidad: cómo escala

La DP del cambio de monedas es O(amount × número de monedas): cada uno de los amount subproblemas se resuelve una vez, y cada uno prueba todas las monedas. El espacio es O(amount) por la tabla. La recursión ingenua, en cambio, es exponencial en el monto, porque vuelve a explorar los mismos submontos por cada camino. El enfrentamiento cuenta el trabajo directamente — llamadas recursivas de la versión ingenua contra unidades de trabajo de la DP, conforme crece el monto:

En escala logarítmica la línea ingenua es una subida recta — crecimiento exponencial — mientras que la línea de la DP es casi plana, creciendo linealmente con el monto. Con un objetivo de 20 y tres monedas, la recursión ingenua hizo unas 38,000 llamadas; la DP hace 60 unidades de trabajo — una diferencia de 640× con un monto minúsculo, y la brecha explota conforme el monto crece (con monto 40 la versión ingenua haría miles de millones de llamadas mientras la DP hace 120). Esta es la firma de la programación dinámica: no solo acelera las cosas por un factor constante, cambia la clase de complejidad, de exponencial a polinomial, negándose a calcular lo mismo dos veces. Y resuelve lo que greedy no pudo — en estos sistemas de monedas aleatorios, greedy regresó una peor respuesta que la DP en cerca del 13% de las instancias, en silencio, porque greedy no tiene forma de reconsiderar una elección localmente buena que resulta globalmente mala.

En qué es buena y en qué no

La programación dinámica es la herramienta correcta cuando un problema tiene subestructura óptima y subproblemas traslapados — lo que describe un rango enorme de problemas de optimización y conteo. Caminos más cortos con decisiones (Bellman-Ford y Floyd-Warshall son DP), problemas de secuencias (distancia de edición, subsecuencia común más larga, alineamiento de secuencias en bioinformática — los siguientes dos capítulos), la familia knapsack, multiplicación de cadenas de matrices, árboles binarios de búsqueda óptimos, parsing (el algoritmo CYK), justificación de texto, y un sinfín de problemas de calendarización y recursos. También es el núcleo computacional del reinforcement learning (value iteration resuelve la ecuación de Bellman) y del reconocimiento de voz y escritura (el algoritmo de Viterbi es DP sobre un modelo oculto de Markov). Cada vez que greedy falla porque una elección localmente óptima puede ser globalmente mala, y los subproblemas se traslapan, la DP suele ser la respuesta.

Donde es la herramienta equivocada es en problemas sin subproblemas traslapados (usa divide y vencerás — la tabla de la DP solo guardaría valores de un solo uso) o sin subestructura óptima (la recurrencia de la DP sería inválida, como en caminos simples más largos o muchos problemas de grafos). También la puede derrotar el número de subproblemas distintos: si el espacio de estados es exponencial — como en el agente viajero, donde un estado de la DP es un subconjunto de ciudades, dando O(2ⁿ · n) — la DP ayuda (le gana a la fuerza bruta O(n!)) pero sigue siendo exponencial, viable solo para n chica. Y las tablas de la DP pueden consumir memoria considerable; cuando el espacio de estados es enorme pero cada estado depende de pocos otros, eso es una restricción real, a veces aliviada con el truco del rolling array. La DP es poderosa pero no es magia — exige las dos propiedades, y su costo es el tamaño del espacio de estados.

Los datos, o las entradas

El enfrentamiento cuenta las llamadas recursivas que hace la recursión ingenua del cambio de monedas contra el trabajo fijo O(amount × coins) de la DP, para monedas {1,3,4} conforme crece el monto objetivo — exponencial contra lineal. La corrección se verifica cruzando las cuatro implementaciones — ingenua, memo top-down, tabla bottom-up y functools.lru_cache — entre sí sobre cientos de sistemas de monedas aleatorios, confirmando que el conjunto de monedas reconstruido suma el monto, y contando qué tan seguido el algoritmo greedy regresa una peor respuesta (76 de 600 instancias). La animación llena la tabla bottom-up para monedas {1,3,4} hasta el monto 11, mostrando cada dp[a] calculado a partir de las entradas más chicas de las que depende.

Constrúyelo, una función a la vez

La recursión ingenua — correcta, pero exponencial por recalcular subproblemas traslapados:

def coin_change_naive(coins, amount, calls=None):
    """The direct recursion: the fewest coins for `amount` is 1 plus the best over all coins c of
    the fewest coins for `amount - c`. Correct, but with NO memory it re-solves the same
    subamounts exponentially many times — the overlapping-subproblems disaster. `calls` counts
    invocations to expose the blowup."""
    if calls is not None:
        calls[0] += 1
    if amount == 0:
        return 0
    if amount < 0:
        return float("inf")
    best = float("inf")
    for c in coins:
        best = min(best, 1 + coin_change_naive(coins, amount - c, calls))
    return best

Programación dinámica top-down — la misma recursión con un cache de memo:

def coin_change_topdown(coins, amount):
    """Top-down dynamic programming (memoization): the same recursion, but cache each subamount's
    answer the first time it's computed and return the cache on every reuse. Each of the `amount`
    distinct subproblems is solved once, so O(amount · len(coins)). Returns the fewest coins, or
    inf if the amount can't be made."""
    memo = {0: 0}

    def best(a):
        if a < 0:
            return float("inf")
        if a in memo:                            # already solved this subproblem — reuse it
            return memo[a]
        memo[a] = min((1 + best(a - c) for c in coins), default=float("inf"))
        return memo[a]

    return best(amount)

Programación dinámica bottom-up — llena una tabla desde los montos más chicos, y reconstruye las monedas:

def coin_change_bottomup(coins, amount):
    """Bottom-up dynamic programming (tabulation): fill a table dp[0..amount] from small amounts
    up, each entry using only already-computed smaller ones — dp[a] = 1 + min over coins of
    dp[a-c]. No recursion, no stack. Also track the coin chosen at each amount so the actual coin
    set can be reconstructed. Returns (fewest_coins, coins_used)."""
    dp = [0] + [float("inf")] * amount           # dp[a] = fewest coins to make a
    pick = [None] * (amount + 1)                 # which coin was used to reach dp[a]
    for a in range(1, amount + 1):
        for c in coins:
            if a - c >= 0 and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                pick[a] = c
    if dp[amount] == float("inf"):
        return float("inf"), []
    used, a = [], amount                         # walk the choices back to list the coins
    while a > 0:
        used.append(pick[a])
        a -= pick[a]
    return dp[amount], sorted(used, reverse=True)

Míralo funcionar

Aquí está la tabla bottom-up para monedas {1,3,4}, llenándose desde el monto 0 hasta el 11. Cada celda dp[a] guarda el mínimo de monedas para armar el monto a; arranca en ∞ (oscuro) y se vuelve un número (gris) una vez calculada. Fíjate en una celda llenándose (naranja): para calcular dp[a], el algoritmo mira las celdas ya calculadas dp[a-1], dp[a-3] y dp[a-4] (resaltadas en azul) — los montos alcanzables al quitar una moneda — y toma la más chica, más uno. Como cada celda que consulta está a su izquierda y ya está lista, la tabla se llena de izquierda a derecha sin recursión y sin recálculo. Para el monto 11 la respuesta es 3 monedas (4+4+3). Y nota que dp[6] = 2 (3+3) — exactamente donde greedy se equivocó el capítulo pasado con 4+1+1; la tabla consideró todas las opciones de primera moneda, así que encontró la combinación que la regla "la más grande primero" de greedy se saltó:

El código completo

La pestaña from-scratch trae las tres versiones — ingenua, top-down, bottom-up — para que veas que la transformación es puramente agregar memoria; la pestaña de librería trae el contraste con greedy (equivocado el 13% de las veces) y la versión con functools.lru_cache que consigue DP top-down con un decorador de una línea. Cámbiate entre ellas.

"""Dynamic programming — solve a problem whose subproblems OVERLAP by computing each subproblem
once and remembering the answer. Divide and conquer assumed independent subproblems; when they
overlap instead — the same smaller instance needed over and over — plain recursion re-solves it
exponentially many times. Dynamic programming fixes that with one idea: a table. Compute each
distinct subproblem a single time, store it, and look it up on every reuse.

The example is minimum-coin change: given coin denominations and a target amount, use the FEWEST
coins to make it. This is exactly the problem greedy couldn't solve — for coins {1,3,4}, greedy
makes 6 as 4+1+1 (three coins) while the optimum is 3+3 (two). It has the two properties every DP
needs: OPTIMAL SUBSTRUCTURE (the best way to make n uses the best way to make some smaller amount)
and OVERLAPPING SUBPROBLEMS (making 6 and making 5 both need the answer for making 2). This chapter
shows the same recurrence three ways — naive (exponential), top-down memoized, and bottom-up
tabulated — the classic progression that turns an exponential algorithm into a linear one.
"""


# region: naive
def coin_change_naive(coins, amount, calls=None):
    """The direct recursion: the fewest coins for `amount` is 1 plus the best over all coins c of
    the fewest coins for `amount - c`. Correct, but with NO memory it re-solves the same
    subamounts exponentially many times — the overlapping-subproblems disaster. `calls` counts
    invocations to expose the blowup."""
    if calls is not None:
        calls[0] += 1
    if amount == 0:
        return 0
    if amount < 0:
        return float("inf")
    best = float("inf")
    for c in coins:
        best = min(best, 1 + coin_change_naive(coins, amount - c, calls))
    return best
# endregion


# region: topdown
def coin_change_topdown(coins, amount):
    """Top-down dynamic programming (memoization): the same recursion, but cache each subamount's
    answer the first time it's computed and return the cache on every reuse. Each of the `amount`
    distinct subproblems is solved once, so O(amount · len(coins)). Returns the fewest coins, or
    inf if the amount can't be made."""
    memo = {0: 0}

    def best(a):
        if a < 0:
            return float("inf")
        if a in memo:                            # already solved this subproblem — reuse it
            return memo[a]
        memo[a] = min((1 + best(a - c) for c in coins), default=float("inf"))
        return memo[a]

    return best(amount)
# endregion


# region: bottomup
def coin_change_bottomup(coins, amount):
    """Bottom-up dynamic programming (tabulation): fill a table dp[0..amount] from small amounts
    up, each entry using only already-computed smaller ones — dp[a] = 1 + min over coins of
    dp[a-c]. No recursion, no stack. Also track the coin chosen at each amount so the actual coin
    set can be reconstructed. Returns (fewest_coins, coins_used)."""
    dp = [0] + [float("inf")] * amount           # dp[a] = fewest coins to make a
    pick = [None] * (amount + 1)                 # which coin was used to reach dp[a]
    for a in range(1, amount + 1):
        for c in coins:
            if a - c >= 0 and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                pick[a] = c
    if dp[amount] == float("inf"):
        return float("inf"), []
    used, a = [], amount                         # walk the choices back to list the coins
    while a > 0:
        used.append(pick[a])
        a -= pick[a]
    return dp[amount], sorted(used, reverse=True)
# endregion

"""The contrast and a cross-check. Two references here:

- `greedy_change` is the greedy algorithm from the previous chapter — take the largest coin that
  fits, repeat. It's fast and optimal for 'canonical' coin systems (like real currency) but WRONG
  in general, and it's the contrast that motivates dynamic programming. The trace generator counts
  how often it returns a suboptimal (or impossible) answer that DP gets right.
- Python's `functools.lru_cache` turns the naive recursion into top-down DP automatically by
  memoizing calls — the standard-library way to get memoization for free, and a cross-check that
  our hand-written memo agrees.

    from functools import lru_cache
    @lru_cache(maxsize=None)
    def best(a): ...
"""
from functools import lru_cache


# region: greedy
def greedy_change(coins, amount):
    """Largest-coin-first greedy: repeatedly take the biggest coin that fits. Optimal for currency-
    like systems, but for {1,3,4} making 6 it takes 4+1+1 (3 coins) where the optimum is 3+3 (2).
    Returns the coin count, or inf if it gets stuck (greedy can even fail to make an amount that
    IS makeable). The cautionary contrast to DP."""
    count, a = 0, amount
    for c in sorted(coins, reverse=True):
        while a >= c:
            a -= c
            count += 1
    return count if a == 0 else float("inf")
# endregion


# region: lru
def coin_change_lru(coins, amount):
    """Top-down DP via functools.lru_cache — memoization the standard-library way. A cross-check
    that our hand-rolled memo table matches Python's automatic one."""
    coins = tuple(coins)

    @lru_cache(maxsize=None)
    def best(a):
        if a == 0:
            return 0
        if a < 0:
            return float("inf")
        return min((1 + best(a - c) for c in coins), default=float("inf"))

    return best(amount)
# endregion

Desde cero contra librería

Las tres versiones desde cero cuentan la historia completa: ingenua, top-down y bottom-up producen respuestas idénticas, y la única diferencia entre la exponencial y las polinomiales es memoria. Esa es la esencia del paradigma, y replantea la programación dinámica: de una técnica intimidante a una disciplina simple — escribe la recurrencia (esa es la parte difícil y creativa: definir el estado y la transición), luego agrega un cache. El functools.lru_cache de Python deja el punto casi demasiado claro: decoras la recursión ingenua y se convierte en DP top-down eficiente sin ningún otro cambio. La parte genuinamente difícil de la DP nunca es la memoización; es reconocer que un problema tiene subestructura óptima y encontrar el estado correcto — la misma intuición que hace a greedy demostrablemente correcto o revela que no lo es. La continuidad del cambio de monedas desde el capítulo pasado es deliberada: greedy falló aquí porque una elección localmente óptima puede ser globalmente mala, y la DP tiene éxito precisamente porque considera todas las opciones para cada subproblema pagando solo una vez por subproblema. Cuando el argumento de intercambio de greedy no cierra, esta es la herramienta.

Dónde te la vas a encontrar de verdad

La programación dinámica está por toda la computación. El ruteo de caminos más cortos (Bellman-Ford, Floyd-Warshall y el algoritmo de Viterbi en códigos correctores de errores y reconocimiento de voz) es DP. La bioinformática alinea secuencias de ADN y proteínas con ella (Needleman-Wunsch, Smith-Waterman — la distancia de edición de los próximos capítulos, generalizada). El control de versiones y diff calculan subsecuencias comunes más largas con ella. Los compiladores la usan para selección óptima de instrucciones y para parsing (el algoritmo CYK). El value iteration y el policy iteration del reinforcement learning resuelven directamente la ecuación de Bellman. El procesamiento de lenguaje natural, los correctores ortográficos (distancia de edición), el acomodo de texto (el salto de línea de TeX es DP), la valuación de opciones financieras (árboles binomiales) y la calendarización de recursos se apoyan en ella. También es uno de los temas más comunes en entrevistas, precisamente porque reconocer la estructura de DP en un problema disfrazado es la habilidad clave. Donde sea que un problema de optimización se descomponga en subproblemas traslapados, es probable que haya programación dinámica debajo.

Puntos clave

La programación dinámica resuelve problemas con subestructura óptima y subproblemas traslapados calculando cada subproblema una vez y recordándolo — top-down con un cache de memo, o bottom-up llenando una tabla desde los subproblemas más chicos. Convierte la recursión ingenua exponencial en tiempo polinomial (641× menos trabajo con monto 20, y la brecha solo crece), y resuelve los problemas de optimización que greedy no puede, porque considera cada opción para cada subproblema en vez de comprometerse con la localmente óptima. La transformación desde la recursión ingenua es puramente agregar memoria; la habilidad real es definir el estado y reconocer la subestructura.

Los siguientes dos capítulos ponen a trabajar la programación dinámica en sus problemas más famosos. La familia knapsack (el que sigue) — escoger el subconjunto de máximo valor bajo un límite de peso — es la DP que greedy demostrablemente no puede resolver, e introduce la distinción importante entre problemas cuya DP es polinomial y aquellos (como el knapsack 0/1) que son solo pseudopolinomiales. Después, la distancia de edición y la subsecuencia común más larga llevan la DP a las secuencias, las tablas bidimensionales detrás de los correctores ortográficos, diff y el alineamiento de ADN.