----- 3/07/10 -----

> [Ho] cercato del materiale sulla programmazione dinamica.
> Ho letto che si memorizzano i dati in un array [eventualmente pluridimensionale].
> Ma che differenza c'e' tra memoization e programmazione dinamica? 
> Non vengono salvati i casi gia' calcolati in un array in entrambi i casi?

-----

L'obiettivo di programmazione dinamica e memoization e' quello di "ricordare" le
soluzioni di sottoproblemi che sono gia' state calcolate al fine di un riutilizzo
immediato. Per la registrazione dei risultati parziali si puo' utilizzare un array
di dimensione appropriata (e' il caso piu' semplice, frequentemente oggetto di esempi
ed esercizi), oppure si possono definire strutture piu' complesse; l'aspetto cruciale
sta nella possibilita' di recuperare i dati in modo efficiente.

In qualche senso si puo' dire che la memoization e' un caso particolare di
programmazione dinamica.

Di solito si parla di memoization quando ci si propone di rendere piu' efficiente
un programma ricorsivo, conservandone la struttura ricorsiva di base. Nel caso di
programmazione dinamica, invece, viene dato maggiore rilievo ai dettagli della
pianificazione delle operazioni che consentono di risolvere (in maniera efficiente)
i vari sottoproblemi e quindi il problema complessivo. In altri termini, si rende
esplicito l'ordine temporale di esecuzione delle operazioni (che invece nel caso di
memoization resta implicito) e, di conseguenza, il programma viene ad assumere una
struttura iterativa. Se la soluzione e' derivata da un'impostazione ricorsiva, il
programma finale non lo sara' piu'.

----- * -----