È un miglioramento della tecnica divide et impera nel caso in cui i sotto-problemi si sovrappongono (non sono indipendenti). Consiste nel risolvere ogni sotto-problema una sola volta, memorizzandone il risultato per riutilizzarlo.
Ci sono due modi per implementare gli algoritmi con questo principio:
- Memoizzazione: è l’approccio top-down con la ricorsione, aiutata da una cache, a partire dal problema principale verso i casi base.
- Tabulazione: è l’approccio bottom-up con l’iterazione a partire dai casi base verso il problema principale.