Un método para resolver problemas complejos descomponiéndolos en subproblemas superpuestos y almacenando sus soluciones (mediante memoización o tabulación) para que cada subproblema se resuelva una sola vez y se evite el cálculo redundante; aplicable cuando el problema presenta subestructura óptima y subproblemas superpuestos.

Principio

Aplicar el principio de optimalidad: una solución óptima de un problema contiene soluciones óptimas de sus subproblemas; organizar el cálculo alrededor de una representación de estado, una relación de recurrencia y la reutilización de subresultados calculados.

Demostración

Calcular el enésimo número de Fibonacci guardando los valores anteriores (memoización o tabla ascendente): en lugar de recursión exponencial, calcular F(0), F(1), …, F(n) una vez y reutilizarlos. En optimización, resolver la mochila 0/1 rellenando una tabla de mejores valores para capacidad y prefijo de objetos para evitar re-evaluar las mismas combinaciones.

Aplicación incorrecta

Aplicar programación dinámica a problemas sin subestructura óptima (por ejemplo, donde las elecciones locales óptimas no se componen en un óptimo global) o a problemas con un espacio de estados extremadamente grande sin compresión, lo que conduce a resultados incorrectos o a un consumo de memoria prohibitivo.

Consecuencia

Cuando es aplicable, búsquedas ingenuas exponenciales a menudo pueden reducirse a algoritmos en tiempo polinómico; se intercambia tiempo por espacio (tablas de memoización) y las soluciones son reproducibles y exactas dentro de la representación elegida.

Inversión

Enfoques voraces o divide y vencerás que no reutilizan soluciones de subproblemas y que toman decisiones locales sin asegurar optimalidad global; pueden ser más rápidos pero fallar en problemas que exigen coordinación global.

Límite

Se aplica a problemas discretos con estados y recurrencias bien definidos; excluye problemas sin subestructura óptima o donde el estado no puede representarse compactamente (p. ej., ciertos problemas no markovianos o continuos de alta dimensión) y casos en que el intercambio memoria/tiempo no es aceptable.

Tensión semántica

Tensión entre memoización (top-down caching) y tabulación (bottom-up), y entre programación dinámica y divide y vencerás: ambos descomponen tareas pero difieren en la estrategia y el orden de reutilización.

Síntesis

La programación dinámica convierte sistemáticamente una recurrencia o descomposición de estado en un cálculo que reutiliza subproblemas resueltos, intercambiando memoria por tiempo bajo la idea organizadora de que soluciones globales óptimas derivan de subsoluciones locales óptimas; su uso práctico exige diseñar estados, transiciones y límites de almacenamiento.