Sesión 02: Divide y vencerás con memorización¶
Divide y vencerás¶
Estrategia algoritmica
- Divide problemas en subproblemas hasta el problema trivial
- Los subproblemas deben ser INDEPENDIENTES
- Posteriormente se combinan las soluciones para CONQUISTAR el problema inicial
- Las soluciones parciales (subproblemas) deben cumplir la propiedad de la solución problema
- Divide y vencerás funciona bien SI NO HAY PROBLEMAS REPETIDOS → Incrementan la COMPLEJIDAD
Memorización
- Hay casos donde divide y vencerás GENERA PROBLEMAS REPETIDOS
- Podemos usar una estructura de datos para guardar las solucionar y sencillamente tomarlas cuando lo necesitemos (inicio programación dinámica)