Dynamic Programming
La programación dinámica descompone un problema en subproblemas superpuestos y almacena sus soluciones para evitar recomputación, resolviendo de abajo hacia arriba o de arriba hacia abajo (memoización).
Propósito
Resolver eficientemente problemas de optimización con subestructura óptima y subproblemas superpuestos.
Mecanismo
Identificar la subestructura óptima: la solución óptima contiene soluciones óptimas de subproblemas. Abajo-arriba: rellenar la tabla en orden creciente de tamaño. Arriba-abajo: recursión con memoización. Clásicos: mochila, subsecuencia común más larga, distancia de edición, multiplicación encadenada de matrices.
Casos de uso
- Diseño de algoritmos
- Problemas de optimización
- Análisis de secuencias