Programmazione dinamica — memoization e tabulation spiegate

La programmazione dinamica è un modo per risolvere problemi salvando le risposte a sottoproblemi più piccoli e riutilizzandole in seguito. È utile quando gli stessi sottoproblemi ricompaiono e la risposta completa può essere costruita a partire da quelle più piccole.

I due stili principali sono memoization e tabulation. La memoization memorizza le risposte durante una soluzione ricorsiva. La tabulation riempie le risposte in ordine bottom-up, di solito con un array o una tabella.

Quando la programmazione dinamica funziona

La programmazione dinamica è utile quando valgono due condizioni.

La prima è che i sottoproblemi si sovrappongano. Questo significa che lo stesso risultato intermedio serve più di una volta. La seconda è che le risposte più grandi possano essere costruite da quelle più piccole in modo coerente.

Se queste condizioni non valgono, memorizzare i risultati precedenti può aggiungere un costo in memoria senza offrire grandi vantaggi.

Memoization vs. tabulation

Memoization: memorizzazione top-down

La memoization parte dall’idea ricorsiva. Quando l’algoritmo risolve un sottoproblema per la prima volta, ne memorizza il risultato. Le chiamate successive riutilizzano il valore salvato invece di ricalcolarlo.

Questo stile è spesso più semplice quando la ricorrenza è chiara ma l’ordine di tutti gli stati necessari non lo è.

Tabulation: costruzione bottom-up

La tabulation parte dai casi base e riempie gli stati in un ordine che rende disponibili le dipendenze quando servono.

Questo stile è spesso più semplice quando conosci già un ordine di iterazione pulito e vuoi un controllo esplicito sulla tabella.

Esempio di programmazione dinamica: Fibonacci

La successione di Fibonacci è definita da

$$F(0) = 0, \quad F(1) = 1$$

e, per $n \ge 2$,

$$F(n) = F(n-1) + F(n-2)$$

Una soluzione ricorsiva semplice ripete del lavoro. Per esempio, calcolare $F(5)$ richiede $F(4)$ e $F(3)$, e poi calcolare $F(4)$ richiede di nuovo $F(3)$. Questa chiamata ripetuta a $F(3)$ è il tipo di spreco che la programmazione dinamica elimina.

Memoization su Fibonacci

Con la memoization, la ricorrenza resta la stessa, ma ogni valore viene memorizzato dopo la prima volta che viene calcolato.

Per $F(5)$, la sequenza utile è:

• calcola e memorizza $F(0)=0$
• calcola e memorizza $F(1)=1$
• calcola e memorizza $F(2)=1$
• calcola e memorizza $F(3)=2$
• calcola e memorizza $F(4)=3$
• calcola e memorizza $F(5)=5$

Il punto chiave è che ogni stato viene calcolato una sola volta. Le richieste successive leggono il valore memorizzato.

Tabulation su Fibonacci

Con la tabulation, costruisci a partire dai casi base verso l’alto:

$$\begin{aligned} F(0) &= 0 \\ F(1) &= 1 \\ F(2) &= F(1) + F(0) = 1 \\ F(3) &= F(2) + F(1) = 2 \\ F(4) &= F(3) + F(2) = 3 \\ F(5) &= F(4) + F(3) = 5 \end{aligned}$$

Questa versione rende evidente l’ordine delle dipendenze: ogni nuovo valore usa voci che sono già note.

Perché la programmazione dinamica può essere più veloce

Se un problema ha solo $k$ stati distinti che contano, la programmazione dinamica prova a risolvere ciascuno di questi $k$ stati una sola volta. Questo può trasformare un grande albero ricorsivo in un calcolo molto più piccolo.

L’accelerazione esatta dipende dal problema. La programmazione dinamica non è automaticamente veloce. Aiuta quando il lavoro ripetuto è davvero una parte importante della soluzione originale.

Errori comuni nella programmazione dinamica

Usarla quando i sottoproblemi non si sovrappongono

Non ogni problema ricorsivo è un problema di programmazione dinamica. Se quasi ogni sottoproblema è diverso, mettere in cache i risultati potrebbe non far risparmiare abbastanza lavoro da fare la differenza.

Definire lo stato sbagliato

Lo stato deve includere tutte le informazioni necessarie per il passo successivo. Se manca un’informazione importante, la ricorrenza può sembrare valida ma produrre risposte sbagliate.

Sbagliare i casi base

I casi base sostengono l’intero metodo. Se i valori iniziali sono sbagliati, anche ogni stato successivo costruito a partire da essi sarà sbagliato.

Riempire la tabella nell’ordine sbagliato

La tabulation funziona solo quando ogni stato viene riempito dopo gli stati da cui dipende. Una ricorrenza corretta può comunque fallire se l’ordine di riempimento è sbagliato.

Supporre che la programmazione dinamica significhi sempre ottimizzazione

Molti esempi famosi massimizzano o minimizzano qualcosa, ma la programmazione dinamica si usa anche per problemi di conteggio e di decisione. Il vero segnale sono i sottoproblemi riutilizzabili, non la parola "migliore".

Dove si usa la programmazione dinamica

La programmazione dinamica compare in problemi come la distanza di edit, la sottosequenza comune più lunga, il conteggio dei cammini, l’ottimizzazione in stile zaino e alcune impostazioni dei cammini minimi.

Quando devi decidere se provarla, poniti due domande:

• i sottoproblemi più piccoli si ripetono?
• la risposta più grande può essere costruita a partire da quelle più piccole?

Se entrambe le risposte sono sì, la programmazione dinamica è una candidata molto forte.

Prova un problema simile

Prova una tua versione con il numero di modi per salire $n$ gradini se ogni mossa è di $1$ gradino oppure di $2$ gradini. La ricorrenza è semplice, i sottoproblemi ripetuti sono facili da individuare ed è un ottimo esempio successivo dopo Fibonacci.