¿Qué dos propiedades indican que un problema encaja con la programación dinámica?
Opciones
- Entrada ordenada y valores únicos
- Subproblemas solapados y subestructura óptima (Opción correcta)
- Entrada en forma de grafo y presencia de ciclos
- Recursión y algo de aleatoriedad en las decisiones
Respuesta
Subproblemas solapados y subestructura óptima
Por qué
La programación dinámica (DP) resuelve un problema grande combinando respuestas de versiones más pequeñas, y guarda cada respuesta pequeña para calcularla una sola vez.
Encaja cuando:
- Subestructura óptima: la mejor respuesta se construye con las mejores respuestas de los subproblemas.
- Subproblemas solapados: los mismos subproblemas aparecen una y otra vez.
Dos estilos: top-down con memoización (@lru_cache) o bottom-up rellenando una tabla.
Recuerda
DP = resolver cada subproblema una vez y reutilizarlo.