Programación dinámica explicada: cómo funciona, código y ejemplos

Qué problema resuelve la programación dinámica

Muchos problemas piden lo mejor, lo más barato o el número de formas: el menor número de monedas que suman una cantidad, la subsecuencia común más larga de dos cadenas, el conjunto más valioso de objetos que cabe en una mochila, el número de caminos en una cuadrícula. Una solución recursiva directa suele recalcular los mismos casos pequeños un número exponencial de veces. La DP elimina esa repetición.

El nombre viene de Richard Bellman, que desarrolló el método en la década de 1950. Aquí "programación" significa planificar o rellenar una tabla, no escribir código.

La idea en palabras sencillas

El Fibonacci recursivo ingenuo muestra el problema. fib(5) llama a fib(4) y a fib(3), y fib(4) vuelve a llamar a fib(3), y así sucesivamente: el número de llamadas crece de forma exponencial. Guardar cada resultado la primera vez que se calcula hace instantánea cualquier llamada posterior.

1. Define el estado: ¿cómo es un subproblema? Por ejemplo, best[a] = menor número de monedas que suman la cantidad a.
2. Escribe la recurrencia: ¿cómo se calcula un estado a partir de estados más pequeños? best[a] = 1 + min(best[a - c] for each coin c).
3. Fija los casos base: best[0] = 0.
4. Elige el orden: de arriba abajo con memoización, o de abajo arriba de modo que los estados más pequeños se rellenen siempre primero.
5. Lee la respuesta en el estado correcto y reconstruye la elección concreta si hace falta.

De arriba abajo: memoización con functools

En Python, functools.cache (Python 3.9+) o functools.lru_cache añaden memoización a una función con una sola línea:

from functools import cache

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

print(fib(80))  # 23416728348467685

Sin el decorador, fib(80) haría más de 10¹⁶ llamadas recursivas. Con él, cada valor de 0 a 80 se calcula una sola vez.

Ejemplo resuelto: cambio de monedas, de abajo arriba

Monedas de 1, 3 y 4; cantidad 6. Un enfoque voraz toma primero la de 4 y necesita 4 + 1 + 1 = 3 monedas, pero 3 + 3 usa solo 2. La DP encuentra el verdadero mínimo rellenando best[a] para a = 0 a 6:

def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1

print(min_coins([1, 3, 4], 6))  # 2
print(min_coins([2], 3))        # -1

Un ejemplo bidimensional: subsecuencia común más larga

Muchos problemas de DP sobre dos secuencias usan una cuadrícula: dp[i][j] es la respuesta para los primeros i caracteres de una cadena y los primeros j de la otra. Para la subsecuencia común más larga (LCS), si los caracteres coinciden, se extiende la diagonal; en caso contrario, se toma lo mejor entre descartar un carácter de una cadena o de la otra.

def lcs(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[len(a)][len(b)]

print(lcs("ABCBDAB", "BDCABA"))  # 4

Una LCS de longitud 4 es BCBA. La misma estructura de tabla resuelve la distancia de edición, que es como las herramientas de diff de texto miden cuánto se diferencian dos cadenas.

Complejidad temporal y espacial

La regla general: tiempo = número de estados × trabajo por estado; espacio = número de estados almacenados.

El O(n × W) de la mochila es pseudopolinómico: depende del valor numérico de W, no del tamaño de la entrada en bits, por lo que es lento cuando W es enorme.

Errores comunes y cuándo usar DP

• Estado incorrecto: si la recurrencia necesita información que el estado no contiene (por ejemplo, qué objetos ya se han usado), la respuesta es errónea. Añade esa información al estado.
• Orden de relleno incorrecto: un bucle de abajo arriba debe calcular cada estado antes de leerlo.
• Error de uno en el tamaño de la tabla: una cadena de longitud n necesita n + 1 filas para incluir el prefijo vacío.
• Recursión profunda: una recursión con memoización sobre 10 000 estados puede superar el límite de recursión de Python; cambia a la versión de abajo arriba.
• Argumentos no hashables: functools.cache necesita argumentos hashables, así que pasa tuplas en lugar de listas.

Usos típicos en entrevistas y en el mundo real: subir escaleras, house robber, subsecuencia creciente más larga, word break, caminos únicos en una cuadrícula, distancia de edición, mochila, multiplicación encadenada de matrices; en la práctica, alineamiento de secuencias en bioinformática, herramientas de diff, correctores ortográficos, reconocimiento de voz (el algoritmo de Viterbi) y caminos más cortos como Bellman-Ford.