Dynamic Programming

La Programación Dinámica (DP) es la técnica de resolución de problemas de decisión multietapa introducida por Richard Bellman en su libro de 1957 (*Dynamic Programming*, Princeton University Press); descompone un problema en subproblemas superpuestos, guarda resultados intermedios en una tabla (memoización o tabulación) y resuelve recursivamente vía la ecuación de Bellman V(s) = max_a {r(s, a) + γ V(s')}. El problema de la mochila es el ejemplo canónico de DP — Bellman presenta el marco DP sobre el knapsack en el libro de 1957; la complejidad O(N×W) es **pseudo-polinómica** (polinómica en el valor de W, exponencial en su longitud en bits). Otras aplicaciones canónicas: caminos más cortos (Bellman-Ford), inventario (lot-sizing Wagner-Whitin), reemplazo de equipo (Bellman 1955), procesos de decisión estocásticos (Markov Decision Process), alineamiento de secuencias (Needleman-Wunsch), análisis sintáctico (CYK), orden de multiplicación de cadenas de matrices. DP tiene dos vertientes: **DP determinista** (cada etapa con resultado conocido) y **DP estocástica** (cada etapa con resultado probabilístico — procesos de Markov). La aplicabilidad de DP requiere subestructura óptima (los óptimos de subproblemas se combinan en óptimo global) y subproblemas superpuestos (se repiten). Approximate Dynamic Programming (ADP) y Stochastic Dual Dynamic Programming (SDDP) extienden DP a problemas estocásticos a gran escala. Bellman 1957 + Bellman y Dreyfus 1962 + Bertsekas 1995 son las referencias canónicas.