"Coloro che non ricordano il passato sono condannati a ripeterlo", Programmazione Dinamica"

La Programmazione Dinamica è un metodo per risolvere problemi complessi spezzandoli in problemi più piccoli e più semplici. La risoluzione di questi sottoproblemi viene fatta soltanto una volta ed i loro risultati vengono salvati in una struttura dati in memoria (con un array, una matrice, etc.)

Ognuno di questi sottoproblemi è indicizzato in un qualche modo, tipicamente basandosi sui parametri di input, in modo da facilitarne il ritrovamento. Quindi, la prossima volta che lo stesso sottoproblema si ripresenta, invece di ricalcolarne la sua soluzione, si può facilmente ritrovarla nella struttura dati in memoria, risparmiando così tempo computazionale.

Ad esempio, la creazione di un albero filogenetico partendo dal DNA si può calcolare facilmente con la Programmazione Dinamica:

Clicca qui per una lista completa di problemi che possono essere risolti con la Programmazione Dinamica.