La programación dinámica (DP) resuelve problemas con overlapping subproblems y optimal substructure calculando cada subproblema una vez y reutilizando el resultado. Los dos estilos son memoization (top-down) y tabulation (bottom-up).
La recursión ingenua recomputa los mismos subproblemas exponencialmente. DP los almacena en caché, colapsando el trabajo exponencial en polinomial.
from functools import lru_cache
@lru_cache(maxsize=None) # cache results automatically
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2) # each n computed once
def fib_table(n):
if n < 2:
return n
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2]) # build up from base cases
return dp[n]
| Memoization | Tabulation | |
|---|---|---|
| Dirección | recursión top-down | iteración bottom-up |
| Calcula | solo estados necesarios | todos los estados |
| Riesgo | stack overflow | ninguno |
| Espacio | puede reducirse | a menudo reducible a filas O(1) |
Fibonacci: de O(2ⁿ) ingenuo a O(n) tiempo, O(n) (u O(1)) espacio.
Usa DP cuando los subproblemas se superponen. Define el estado y la recurrencia cuidadosamente — esa es la parte difícil. Si los subproblemas no se superponen, el divide-and-conquer simple es suficiente.
DP convierte problemas exponenciales intratables — rutas más cortas, distancia de edición, knapsack — en eficientes.
La habilidad de identificar estado y recurrencia está entre las más valoradas en entrevistas de algoritmos.
Subyace en sistemas reales desde herramientas diff hasta alineación de secuencias bioinformáticas.