Programmazione dinamica (DP)
Tecnica di ottimizzazione: ogni sottoproblema ricorsivo si risolve una sola volta e il risultato viene memorizzato invece di essere ricalcolato. Richard Bellman, anni Cinquanta: «dinamica» servì solo a fare colpo sui dirigenti della RAND.
Esistono due varianti: top-down (ricorsione più memoizzazione) e bottom-up (riempimento iterativo di una tabella). Problemi classici: Fibonacci, sottosequenza comune più lunga, problema dello zaino, distanza di edit, moltiplicazione di catene di matrici.
La DP funziona quando il problema ha una sottostruttura ottima (la soluzione grande si costruisce con quelle piccole) e sottoproblemi sovrapposti (lo stesso sottoproblema ricompare più volte). Le alternative sono divide et impera (senza sovrapposizione) e gli algoritmi greedy.