El cierre de la lección anterior dejó una pregunta abierta: ¿qué hacemos cuando un problema tiene subestructura óptima pero la apuesta voraz falla — cuando pagar 6 € exige darse cuenta de que 3+3 gana a empezar por el 4? La respuesta es la programación dinámica (PD): en lugar de jugárselo todo a una decisión, se consideran todas las decisiones posibles... pero sin pagar el precio exponencial de la fuerza bruta, porque los subproblemas repetidos se calculan una sola vez y se guardan. Es exactamente la idea que apuntamos en 02-02 con construir_indice — gastar memoria para no repetir trabajo — elevada a estrategia de diseño. En esta lección la desarrollaremos en sus dos sabores (memoización y tabulación), la aplicaremos a dos problemas de RutaBus — el trayecto más barato con tarifas por tramos y la selección de mejoras de flota con presupuesto limitado — y aprenderemos no solo a calcular el valor óptimo, sino a reconstruir la solución que lo alcanza.

1. Los dos ingredientes: subproblemas solapados y subestructura óptima
2. Fibonacci: el ejemplo mínimo del desastre y su cura
3. Memoización (top-down): recordar lo ya calculado
4. Problema RutaBus: el trayecto más barato con tarifas por tramos
5. Tabulación (bottom-up): rellenar la tabla sin recursión
6. Top-down vs bottom-up
7. La mochila 0/1: mejoras de flota con presupuesto limitado
8. Reconstruir la solución, no solo el valor

La programación dinámica aplica cuando el problema tiene, a la vez:

• Subestructura óptima: la solución óptima del problema se construye a partir de soluciones óptimas de sus subproblemas. (La misma propiedad que exigía greedy en 03-02 — no es casualidad: greedy es, en cierto modo, una PD que se atreve a explorar una sola rama.)
• Subproblemas solapados: al descomponer el problema, los mismos subproblemas aparecen una y otra vez. Aquí está la diferencia clave con divide y vencerás (03-01), cuyos subproblemas eran independientes: si no hay solapamiento, guardar resultados no ahorra nada.

Antes de subir al autobús, el ejemplo más pequeño posible de subproblemas solapados: la sucesión de Fibonacci (1, 1, 2, 3, 5, 8, ...), donde cada término es la suma de los dos anteriores.

En 02-01 aprendimos a analizar recursivas contando llamadas. Contémoslas: fib(5) llama a fib(4) y fib(3); fib(4) llama a fib(3) — ¡otra vez! — y a fib(2)...

fib(3) se calcula 2 veces aquí; en fib(50), fib(3) se calcularía miles de millones de veces. El árbol de llamadas crece como O(2ⁿ) — la peor categoría de la jerarquía de 01-03 — para un problema que solo tiene n subproblemas distintos: fib(1), fib(2), ..., fib(n). Todo el exceso es trabajo repetido. La cura: calcular cada uno una vez y apuntarlo.

Memoización = envolver la recursión con una "libreta" (normalmente un diccionario) donde se anota cada resultado la primera vez que se calcula; las veces siguientes se devuelve la anotación en O(1) — la consulta a diccionario cuyo coste estudiamos con construir_indice en 02-02.

Análisis con las herramientas del Módulo 2:

• Tiempo: cada fib_memo(k) se calcula de verdad una sola vez (después queda en memo). Hay n subproblemas y cada uno hace trabajo O(1) fuera de las recursiones: O(n). De exponencial a lineal.
• Espacio: el diccionario guarda n entradas y la pila de recursión alcanza profundidad n (02-02): O(n).

Este es, con nombre y apellidos, el trade-off tiempo ↔ espacio que anticipamos en 02-02: pagamos O(n) de memoria para desplomar el tiempo de O(2ⁿ) a O(n). Pocas veces en informática se compra tanto con tan poco.

Nota práctica: Python trae la memoización de serie con from functools import lru_cache y el decorador @lru_cache(maxsize=None) sobre la función recursiva. Úsalo en producción; aquí escribimos la libreta a mano para ver el mecanismo.

Ahora un problema real de RutaBus. En la línea L2 hay n + 1 paradas numeradas de 0 (Plaza Mayor) a n (Parque del Río). Desde cada parada i el pasajero puede:

• avanzar 1 parada pagando tarifa1[i] céntimos, o
• avanzar 2 paradas (servicio semidirecto) pagando tarifa2[i] céntimos.

¿Cuál es el coste mínimo para ir de la parada 0 a la parada n?

Paso 1 — definir el subproblema. Sea coste(i) = coste mínimo para llegar de la parada i hasta la n. Queremos coste(0).

Paso 2 — la recurrencia (subestructura óptima). Desde i solo hay dos primeras decisiones posibles; lo que venga después debe ser, a su vez, óptimo:

Paso 3 — comprobar el solapamiento. coste(3) lo necesitan tanto coste(2) (saltando 1) como coste(1) (saltando 2): los mismos subproblemas aparecen por caminos distintos, igual que en Fibonacci. Sin memoria, la recursión sería exponencial; con ella, solo hay n + 1 subproblemas.

Versión top-down (memoización):

Tiempo O(n) — cada parada se resuelve una sola vez — y espacio O(n) entre el memo y la pila de recursión.

La tabulación da la vuelta al cálculo: en lugar de partir de la pregunta grande y bajar (top-down), parte de los casos base y sube, rellenando una tabla con un bucle. Sin recursión, sin pila.

Rellenemos la tabla a mano, celda a celda y en el mismo orden que el bucle — verificar dos o tres celdas manualmente es la prueba unitaria más barata que existe para una PD:

El coste mínimo es 490 céntimos. Observa la celda i = 3: ahí el semidirecto (180) gana al salto simple (240); en cambio en i = 2 conviene el salto simple. La tabla toma, para cada parada, la mejor decisión — nada de apuestas irrevocables.

Tiempo O(n), espacio O(n) para la tabla — y fíjate: como coste[i] solo consulta i+1 e i+2, bastarían dos variables, bajando el espacio auxiliar a O(1). Esa clase de reducciones de memoria se estudia en el Módulo 5 (05-02); aquí nos basta con saber que existe.

Regla práctica: diseña siempre la recurrencia primero (es el corazón de la PD); luego escribe la memoización para validarla rápido, y pásala a tabulación si necesitas rendimiento, control del espacio o evitar la pila.

El problema estrella de la PD, en versión RutaBus. Dirección aprueba un presupuesto de 9 (miles de euros) y el equipo técnico propone cuatro mejoras, cada una con su coste y su beneficio estimado (índice de mejora de servicio):

Cada mejora se financia entera o no se financia (de ahí "0/1": nada de medio wifi). Objetivo: maximizar el beneficio total sin exceder el presupuesto. El greedy por ratio beneficio/coste falla en general (es el cambio de monedas otra vez); la PD lo resuelve de forma exacta.

Subproblema: V[i][p] = beneficio máximo usando solo las i primeras mejoras con presupuesto p.

Recurrencia: para la mejora i-ésima, de coste c y beneficio b:

La tabla completa (filas: mejoras consideradas hasta el momento; columnas: presupuesto 0..9):

Leamos varias celdas para entender el mecanismo — esto es lo que convierte la tabla en conocimiento:

• Fila Wifi, p=2: por fin cabe el wifi (coste 2): max(V[∅][2], V[∅][0] + 3) = max(0, 3) = 3. Toda la fila vale 3 de ahí en adelante: con una sola mejora disponible no hay más que rascar.
• Fila Rampa, p=3: max(V[wifi][3], V[wifi][0] + 4) = max(3, 4) = 4. Con presupuesto 3 conviene la rampa sola antes que el wifi solo.
• Fila Rampa, p=5: max(V[wifi][5], V[wifi][5−3] + 4) = max(3, 3 + 4) = 7. Financiar la rampa compensa porque con el presupuesto restante (2) aún cabe el wifi: la celda V[wifi][2] = 3 ya contenía esa mejor decisión previa. Cada celda reutiliza óptimos ya calculados: subestructura óptima en acción.
• Fila Paneles, p=9: max(V[rampa][9], V[rampa][9−4] + 5) = max(7, 7 + 5) = 12. Financiando los paneles (4) quedan 5, y V[rampa][5] = 7 era "wifi + rampa": total wifi + rampa + paneles = 12.
• Fila Clima, p=9 — la respuesta final: max(V[paneles][9], V[paneles][9−5] + 8) = max(12, 5 + 8) = 13. Financiar la climatización deja presupuesto 4, cuyo óptimo previo era V[paneles][4] = 5 (los paneles solos). El máximo global es 13.

Coste del algoritmo: dos bucles anidados → O(n · P) en tiempo y espacio (n mejoras, P presupuesto), un análisis directo con las reglas de 02-01. Nota fina: ese coste depende del valor numérico P, no solo de cuántos elementos hay — la mochila por PD es eficiente para presupuestos moderados, no gratis en general.

"El beneficio máximo es 13" no le sirve a dirección: quiere saber qué mejoras financiar. La tabla ya contiene esa información — basta recorrerla hacia atrás preguntando en cada fila "¿esta mejora cambió el valor?":

Traza sobre la tabla anterior:

1. Fila Clima, p=9: V[4][9] = 13 ≠ V[3][9] = 12 → la climatización entra; presupuesto restante: 9 − 5 = 4.
2. Fila Paneles, p=4: V[3][4] = 5 ≠ V[2][4] = 4 → los paneles entran; restante: 4 − 4 = 0.
3. Fila Rampa, p=0: V[2][0] = 0 = V[1][0] → la rampa no cambió nada: fuera.
4. Fila Wifi, p=0: V[1][0] = 0 = V[0][0] → fuera.

Selección óptima: paneles + climatización (coste 4 + 5 = 9, beneficio 5 + 8 = 13). Fíjate en el detalle anti-intuición: el wifi, la mejora con mejor ratio beneficio/coste (1,5), no está en el óptimo — un greedy por ratio la habría tomado primero y habría quedado atrapado. La PD lo vio venir porque exploró todas las combinaciones... pagando cada subproblema una sola vez.

El mismo truco de "mirar de qué celda vengo" reconstruye el trayecto barato de la L2: en cada parada i, si coste[i] == tarifa1[i] + coste[i+1] el óptimo saltó 1 parada; si no, saltó 2. Con nuestra tabla: 0 →(210)→ 2 →(100)→ 3 →(180)→ 5, total 490.

Cerramos con la mención prometida: la PD también opera sobre grafos completos — Floyd-Warshall calcula los caminos mínimos entre todos los pares de paradas de la red RutaBus rellenando una tabla de subproblemas indexada por parejas de paradas y nodos intermedios permitidos. Es PD pura sobre grafos y lo estudiaremos en 04-06.

• Empezar a programar sin escribir la recurrencia. La PD se diseña en papel: subproblema (¿qué significa exactamente V[i][p]?), recurrencia, casos base. El código es la traducción literal; sin recurrencia clara, saldrá una maraña de índices.
• Definir mal el subproblema. Si no puedes expresar la recurrencia usando solo subproblemas "más pequeños", la definición no sirve. Reformúlala — a menudo añadiendo un parámetro, como el "usando solo las i primeras mejoras" de la mochila.
• No verificar celdas a mano. Elige 2-3 celdas de la tabla, recalcúlalas con la recurrencia y conviértelas en assert de test. Los errores de índices (i vs i-1, p vs p-c) son silenciosos y esta es la red que los caza.
• Olvidar los casos base o dejar la tabla sin inicializar. coste[n] = 0 y la fila ∅ de la mochila no son decoración: toda la tabla se apoya en ellos.
• Usar memoización con listas como clave. Las claves de un diccionario deben ser inmutables (int, tuple); una lista lanza TypeError. Convierte el estado a tupla.
• Recursión demasiado profunda. Para n de decenas de miles, la memoización agota la pila de Python (02-02): pasa a tabulación.
• Aplicar PD donde no hay solapamiento. Si cada subproblema aparece una sola vez, el memo no ahorra nada y solo gasta memoria: eso es divide y vencerás (03-01) y no necesita libreta.

Un pasajero en la parada 0 puede avanzar 1 o 2 paradas en cada paso (sin tarifas: aquí solo contamos caminos). Escribe formas_de_llegar(n) que cuente de cuántas maneras distintas puede llegar exactamente a la parada n, con memoización. Calcula a mano los valores para n = 1..5 y observa qué sucesión aparece. ¿Cuál es el coste temporal y espacial?

Convierte formas_de_llegar a tabulación y reduce después su espacio auxiliar a O(1) conservando el tiempo O(n). (Pista: ¿cuántas celdas anteriores necesita cada celda?)

Al problema de las mejoras de flota se añade una quinta opción: ("GPS de flota", 4, 6). Con presupuesto 9, calcula la nueva fila de la tabla y reconstruye la selección óptima. ¿Sigue estando la climatización en la solución? ¿Y los paneles?

Solución 1

Para llegar a n, el último salto vino de n−1 o de n−2, y ambos conjuntos de caminos son disjuntos: f(n) = f(n−1) + f(n−2). Valores: f(1)=1, f(2)=2, f(3)=3, f(4)=5, f(5)=8 — Fibonacci desplazado. Nuestro problema de transporte esconde la misma estructura que el ejemplo "de juguete": reconocer recurrencias conocidas bajo disfraces nuevos es una de las grandes destrezas de la PD. Tiempo O(n), espacio O(n).

Solución 2

Cada celda solo necesita las dos anteriores, así que la "tabla" se comprime en dos variables: tiempo O(n), espacio auxiliar O(1) y sin pila de recursión. Es el trade-off tiempo↔espacio de 02-02 ajustado al mínimo imprescindible.

Solución 3

La nueva fila se calcula con V[5][p] = max(V[4][p], V[4][p−4] + 6) para p ≥ 4. En la celda final: V[5][9] = max(V[4][9], V[4][5] + 6) = max(13, 8 + 6) = 14. Reconstrucción: V[5][9] = 14 ≠ V[4][9] = 13 → el GPS entra, restante 5; V[4][5] = 8 ≠ V[3][5] = 7 → la climatización entra, restante 0; nada más cabe. Selección óptima: GPS + climatización (coste 4 + 5 = 9, beneficio 14). La climatización sigue, pero los paneles salen: añadir un candidato puede reorganizar toda la solución — exactamente lo que un greedy de decisiones irrevocables jamás podría hacer.

La programación dinámica es la estrategia para problemas con subestructura óptima y subproblemas solapados: se explora el espacio completo de decisiones, pero cada subproblema se paga una sola vez, cambiando memoria por tiempo — el trade-off que veníamos anunciando desde 02-02, ahora con nombre propio. Hemos aprendido su método de diseño (definir el subproblema → escribir la recurrencia → fijar los casos base), sus dos realizaciones — memoización top-down y tabulación bottom-up —, y la hemos aplicado al trayecto más barato de la L2 (490 céntimos, y sabemos por dónde) y a la mochila 0/1 de las mejoras de flota, incluida la reconstrucción de la solución recorriendo la tabla hacia atrás. Con divide y vencerás, greedy y PD tenemos ya tres formas de construir soluciones; nos falta la estrategia para cuando no queda más remedio que buscar: problemas de restricciones donde hay que probar combinaciones, detectar callejones sin salida y volver sobre los propios pasos. Esa exploración sistemática con marcha atrás — el backtracking — cierra el módulo en la próxima lección, donde además pondremos las cuatro estrategias frente a frente.