Programación dinámica: memoización, tabulación y problemas clásicos

Muchos problemas se pueden resolver dividiéndolos en subproblemas más pequeños, como en divide y vencerás. Pero a veces esos subproblemas se repiten una y otra vez, y resolverlos cada vez desde cero dispara el tiempo de forma exponencial. La programación dinámica guarda el resultado de cada subproblema la primera vez que se calcula y lo reutiliza. Con esa idea tan simple, problemas que tardarían siglos se resuelven en milisegundos.

Lo que vas a aprender

Cuándo se puede aplicar programación dinámica.
La diferencia entre memoización y tabulación.
Cómo plantear el estado y la recurrencia de un problema.
Cómo reconstruir la solución, no solo su valor.
Los problemas clásicos: monedas, mochila, subsecuencia común y distancia de edición.

Fundamentos teóricos

Cuándo se aplica

Un problema se presta a programación dinámica si tiene:

Subestructura óptima: la solución óptima se construye a partir de soluciones óptimas de subproblemas.
Subproblemas solapados: los mismos subproblemas aparecen muchas veces.

Si los subproblemas no se repiten, basta con divide y vencerás. Si además se puede decidir en cada paso sin mirar atrás, puede bastar un algoritmo voraz.

Ejemplo: Fibonacci

F(n) = F(n-1) + F(n-2)

. La recursión directa recalcula lo mismo muchísimas veces:

F(50)

hace unos

4\cdot10^{10}

llamadas. Guardando los resultados, solo hay 51 subproblemas distintos.

Memoización (de arriba abajo)

Se escribe la recursión normal y se guarda cada resultado en una tabla:

from functools import lru_cache

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

Tabulación (de abajo arriba)

Se rellena la tabla empezando por los casos más pequeños, sin recursión:

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

	Memoización	Tabulación
Estilo	Recursivo	Iterativo
Calcula	Solo los subproblemas necesarios	Todos
Riesgo	Desbordar la pila con mucha profundidad	Ninguno
Ahorro de memoria	Difícil	Fácil: a menudo basta con la fila anterior

Cómo plantear un problema

Estado: ¿qué parámetros definen un subproblema? Por ejemplo, $dp[i][w]$ : el mejor valor con los $i$ primeros objetos y capacidad $w$ .
Recurrencia: ¿cómo se obtiene un estado a partir de otros más pequeños?
Casos base.
Orden de cálculo: que cada estado se calcule después de aquellos de los que depende.
Respuesta: ¿qué estado contiene la solución?

El coste es (número de estados) × (trabajo por estado).

Problemas clásicos

Problema	Estado	Recurrencia	Coste
Cambio de monedas (mínimo de monedas)	$dp[x]$	$dp[x] = 1 + \min_c dp[x - c]$	$O(X\cdot k)$
Mochila 0/1	$dp[i][w]$	$\max(dp[i-1][w],\ v_i + dp[i-1][w - p_i])$	$O(n\,W)$
Subsecuencia común más larga (LCS)	$dp[i][j]$	$dp[i-1][j-1] + 1$ si coinciden; si no, $\max(dp[i-1][j], dp[i][j-1])$	$O(n\,m)$
Distancia de edición	$dp[i][j]$	$\min$ de borrar, insertar o sustituir	$O(n\,m)$
Caminos mínimos (Floyd-Warshall)	$d[k][i][j]$	$\min(d[i][j],\ d[i][k] + d[k][j])$	$O(V^3)$

Ejemplos resueltos

Ejemplo 1 · Cambio de monedas

Mínimo de monedas para pagar 11 con monedas de 1, 5 y 6.

def monedas(x, valores):
    INF = float("inf")
    dp = [0] + [INF] * x
    for v in range(1, x + 1):
        for c in valores:
            if c <= v:
                dp[v] = min(dp[v], dp[v - c] + 1)
    return dp[x]

print(monedas(11, [1, 5, 6]))   # 2  (5 + 6)

El algoritmo voraz (coger siempre la moneda más grande) daría 6 + 1 + 1 + 1 + 1 + 1 = 6 monedas.

Ejemplo 2 · Mochila 0/1

Capacidad 7; objetos (peso, valor): (1, 1), (3, 4), (4, 5), (5, 7).

def mochila(W, pesos, valores):
    dp = [0] * (W + 1)
    for p, v in zip(pesos, valores):
        for w in range(W, p - 1, -1):     # de mayor a menor: cada objeto una vez
            dp[w] = max(dp[w], dp[w - p] + v)
    return dp[W]

print(mochila(7, [1, 3, 4, 5], [1, 4, 5, 7]))   # 9

La mejor opción es llevar los objetos de peso 3 y 4 (valor 9). Recorrer

w

hacia atrás permite usar una sola fila.

Ejemplo 3 · Subsecuencia común más larga

Entre "ABCBDAB" y "BDCABA":

def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 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[n][m]

print(lcs("ABCBDAB", "BDCABA"))   # 4, por ejemplo "BCBA"

Es lo que usa diff para comparar ficheros, y se usa también para alinear secuencias de ADN.

Ejemplo 4 · Distancia de edición (Levenshtein)

Mínimo de inserciones, borrados y sustituciones para pasar de "gato" a "pato": 1. De "casa" a "calle": 3.

def edicion(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1): dp[i][0] = i
    for j in range(m + 1): dp[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            coste = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1,         # borrar
                           dp[i][j - 1] + 1,         # insertar
                           dp[i - 1][j - 1] + coste) # sustituir
    return dp[n][m]

Es la base de los correctores ortográficos.

Ejemplo 5 · Reconstruir la solución

Para saber qué objetos van en la mochila, se guarda la tabla completa

dp[i][w]

y se recorre hacia atrás: si

dp[i][w] \ne dp[i-1][w]

, el objeto

i

está dentro y se pasa a

w - p_i

Errores frecuentes

No identificar bien el estado. Si falta información en el estado, la recurrencia no es correcta.
Calcular estados en un orden equivocado en la tabulación, usando valores aún no calculados.
En la mochila 0/1 con una fila, recorrer $w$ hacia delante: cada objeto se usaría varias veces (eso es la mochila ilimitada).
Aplicar un algoritmo voraz donde no funciona, como el cambio de monedas con valores arbitrarios.
Usar memoización con mucha profundidad en lenguajes con pila limitada.

Preguntas frecuentes

¿Por qué se llama 'dinámica'?

Richard Bellman eligió el nombre en los años 50, según contó, porque sonaba bien y ocultaba que hacía investigación matemática a un secretario de Defensa que la detestaba. “Programación” significaba planificar, no escribir código.

¿Dónde se usa en la práctica?

En el GPS y los mapas (caminos mínimos), en la bioinformática (alineamiento de secuencias), en el reconocimiento de voz (algoritmo de Viterbi), en el control óptimo, en los compiladores y en finanzas (valoración de opciones).

Temas relacionados

Recursión en C

La pila de llamadas paso a paso.

Divide y vencerás

Cuando los subproblemas no se repiten.

Notación asintótica

Medir el coste de los algoritmos.

Matemáticas

Física

Química

Electrónica

Programación

Inglés

Infantil

Programación dinámica: memoización, tabulación y problemas clásicos

Lo que vas a aprender

Fundamentos teóricos

Cuándo se aplica

Ejemplo: Fibonacci

Memoización (de arriba abajo)

Tabulación (de abajo arriba)

Cómo plantear un problema

Problemas clásicos

Ejemplos resueltos

Errores frecuentes

Preguntas frecuentes

Temas relacionados

Recursión en C

Divide y vencerás

Notación asintótica

​Lo que vas a aprender

​Fundamentos teóricos

​Cuándo se aplica

​Ejemplo: Fibonacci

​Memoización (de arriba abajo)

​Tabulación (de abajo arriba)

​Cómo plantear un problema

​Problemas clásicos

​Ejemplos resueltos

​Errores frecuentes

​Preguntas frecuentes

​Temas relacionados

Recursión en C

Divide y vencerás

Notación asintótica

Lo que vas a aprender

Fundamentos teóricos

Cuándo se aplica

Ejemplo: Fibonacci

Memoización (de arriba abajo)

Tabulación (de abajo arriba)

Cómo plantear un problema

Problemas clásicos

Ejemplos resueltos

Errores frecuentes

Preguntas frecuentes

Temas relacionados