Programmazione dinamica

Tecnica che risolve problemi complessi scomponendoli in sottoproblemi sovrapposti, memorizzandone i risultati per evitare ricalcoli. Applicabile quando vale il principio di ottimalità, trasforma soluzioni esponenziali in polinomiali, come nel calcolo di distanze fra stringhe.