Programación dinámica (PD)
Técnica de optimización: resuelve subproblemas recursivos una sola vez y cachea los resultados en vez de recalcularlos. Richard Bellman (años 50) — lo de "dinámica" era solo para sonar impresionante ante los gestores de RAND.
Dos variantes: de arriba abajo (recursión + memoización) y de abajo arriba (rellenado iterativo de una tabla). Problemas clásicos: Fibonacci, subsecuencia común más larga, mochila, distancia de edición, multiplicación encadenada de matrices.
La PD funciona cuando el problema tiene subestructura óptima (la solución grande se construye a partir de las pequeñas) y subproblemas solapados (el mismo subproblema aparece repetidamente). Rival: divide y vencerás (sin solapamiento) y los algoritmos voraces.