> ## Documentation Index
> Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt
> Use this file to discover all available pages before exploring further.

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

> Programación dinámica explicada: subestructura óptima y subproblemas solapados, memoización (top-down) y tabulación (bottom-up), cómo plantear la recurrencia, y problemas clásicos resueltos con código: Fibonacci, cambio de monedas, mochila 0/1, subsecuencia común más larga y distancia de edición.

Muchos problemas se pueden resolver dividiéndolos en subproblemas más pequeños, como en [divide y vencerás](https://apuntes.simulab.es/programacion/c/divide-y-venceras.md). 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:

1. **Subestructura óptima:** la solución óptima se construye a partir de soluciones óptimas de subproblemas.
2. **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:

```python theme={null}
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:

```python theme={null}
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

1. **Estado:** ¿qué parámetros definen un subproblema? Por ejemplo, $dp[i][w]$: el mejor valor con los $i$ primeros objetos y capacidad $w$.
2. **Recurrencia:** ¿cómo se obtiene un estado a partir de otros más pequeños?
3. **Casos base.**
4. **Orden de cálculo:** que cada estado se calcule después de aquellos de los que depende.
5. **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

> [accordion] Ejemplo 1 · Cambio de monedas
>
> Mínimo de monedas para pagar 11 con monedas de 1, 5 y 6.
>
> ```python theme={null}
> 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.

> [accordion] Ejemplo 2 · Mochila 0/1
>
> Capacidad 7; objetos (peso, valor): (1, 1), (3, 4), (4, 5), (5, 7).
>
> ```python theme={null}
> 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.

> [accordion] Ejemplo 3 · Subsecuencia común más larga
>
> Entre `"ABCBDAB"` y `"BDCABA"`:
>
> ```python theme={null}
> 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.

> [accordion] 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.
>
> ```python theme={null}
> 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.

> [accordion] 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

> [accordion] ¿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.

> [accordion] ¿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

> [card] [Recursión en C](https://apuntes.simulab.es/programacion/c/recursion.md)
>
> La pila de llamadas paso a paso.

> [card] [Divide y vencerás](https://apuntes.simulab.es/programacion/c/divide-y-venceras.md)
>
> Cuando los subproblemas no se repiten.

> [card] [Notación asintótica](https://apuntes.simulab.es/programacion/algoritmos/notacion-asintotica.md)
>
> Medir el coste de los algoritmos.


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.