Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigma

Il divide and conquerParadigma in cui un'istanza si divide in sottoistanze più piccole, si risolvono ricorsivamente e si ricombinano le soluzioni (vedi Divide and conquer - proprietà di sottostruttura e albero delle chiamateUn algoritmo divide and conquer nasce da una proprietà di sottostruttura (funzioni Divide e Conquer, base n0) con sottoistanze di taglia strettamente minore; l'albero delle chiamate ne descrive l'esecuzione, e il D&C non ha memoria (ripete le sottoistanze uguali). Esempio completo: MAX di un array, con correttezza per induzione, ricorrenza e conteggio esatto n-1 tramite il teorema sugli alberi binari pieni.Divide and conquer - proprietà di sottostruttura e albero delle chiamate →) è smemorato: ogni nodo dell'albero delle chiamate viene espanso per intero, anche se un nodo con la stessa sottoistanza è già stato risolto altrove. Se le sottoistanze si ripetono, il costo può diventare esponenziale. La programmazione dinamica (DP, dynamic programming) mantiene una tabella con le soluzioni già calcolate e le riusa.

Un esempio semplice: i numeri di Fibonacci

Definizione. Si pone $F_0 = F_1 = 1$ e $F_n = F_{n-1} + F_{n-2}$ per $n > 1$. I primi valori sono $1, 1, 2, 3, 5, 8, 13, 21, \dots$

(Qui $F_0 = 1$, come nelle dispense del corso: il $F_n$ di altri testi, con $F_0 = 0$, è il $F_{n-1}$ di questa nota.) La definizione suggerisce subito un algoritmo divide and conquer:

RFIB(n)
  if n = 0 or n = 1 then return 1
  return RFIB(n-1) + RFIB(n-2)

Costo del ricorsivo

Si contano le addizioni tra interi. Il numero $T(n)$ soddisfa

$$T(n) = \begin{cases} 0 & n = 0, 1 \\ T(n-1) + T(n-2) + 1 & n > 1 \end{cases}$$

Valore esatto: $T(n) = F_n - 1$. Per induzione su $n$ (vedi Principio di induzionePer dimostrare una proprietà per ogni n basta il passo base e il passo induttivo da n a n+1.Principio di induzione →). Base: $T(0) = 0 = F_0 - 1$ e $T(1) = 0 = F_1 - 1$. Passo: per $n > 1$, supponendo la tesi per $n - 1$ e $n - 2$,

$$T(n) = T(n-1) + T(n-2) + 1 = (F_{n-1} - 1) + (F_{n-2} - 1) + 1 = F_n - 1.$$

Il numero di chiamate (nodi dell'albero) è $2F_n - 1$: ogni addizione corrisponde a un nodo interno, e un albero binario pieno con $F_n - 1$ nodi interni ha $F_n$ foglie, in tutto $2F_n - 1$ nodi.

Minorazione esponenziale (srotolamento). Senza conoscere $F_n$, $T$ è non decrescente ($T(n-1) \ge T(n-2)$), quindi $T(n) \ge 2T(n-2) + 1$. Srotolando:

$$\begin{aligned} T(n) &\ge 2T(n-2) + 1 \\ &\ge 2\,[\,2T(n-4) + 1\,] + 1 = 2^2 T(n-4) + 2 + 1 \\ &\ge 2^3 T(n-6) + 4 + 2 + 1 \\ &\;\;\vdots \\ &\ge 2^i\, T(n-2i) + \sum_{j=0}^{i-1} 2^j = 2^i\, T(n-2i) + 2^i - 1. \end{aligned}$$

Si arriva ai casi base quando $n - 2i \in \{0, 1\}$, cioè per $i^\star = \lfloor n/2 \rfloor$ (se $n$ è pari $n - 2i^\star = 0$, se è dispari vale $1$). Lì $T = 0$, quindi

$$T(n) \ge 2^{\lfloor n/2 \rfloor} - 1 = \Theta\big((\sqrt 2)^n\big).$$

Il valore esatto cresce come $\varphi^n$ con $\varphi = \frac{1 + \sqrt 5}{2} \approx 1{,}618$ (formula di Binet: $F_n = \frac{\varphi^{n+1} - \psi^{n+1}}{\sqrt 5}$ con $\psi = \frac{1 - \sqrt 5}{2}$).

Dove si spreca lavoro

Albero delle chiamate per $n = 5$ (a destra di ogni nodo, il valore restituito):

F(5)=8
├─ F(4)=5
│  ├─ F(3)=3
│  │  ├─ F(2)=2
│  │  │  ├─ F(1)=1
│  │  │  └─ F(0)=1
│  │  └─ F(1)=1
│  └─ F(2)=2
│     ├─ F(1)=1
│     └─ F(0)=1
└─ F(3)=3
   ├─ F(2)=2
   │  ├─ F(1)=1
   │  └─ F(0)=1
   └─ F(1)=1

Le chiamate sono $15 = 2F_5 - 1$ (le addizioni sono $7 = F_5 - 1$). Il sottoalbero di $F(3)$ è espanso due volte, quello di $F(2)$ tre volte; per argomento, le chiamate sono: $F(5)$ una, $F(4)$ una, $F(3)$ due, $F(2)$ tre, $F(1)$ cinque, $F(0)$ tre. Il grado di replicazione cresce esponenzialmente con $n$.

Il bottom-up: ITFIB

Basta riempire una tabella $F[0..n]$ dai casi base verso l'alto.

ITFIB(n)
  if n = 0 or n = 1 then return 1
  F[0] <- 1
  F[1] <- 1
  for i <- 2 to n do
    F[i] <- F[i-1] + F[i-2]
  return F[n]

• Correttezza per induzione su $i$: i casi base $F[0], F[1]$ sono corretti; se $F[i-1]$ e $F[i-2]$ sono corretti, lo è anche $F[i] = F[i-1] + F[i-2]$.
• Costo: il ciclo esegue $n - 1$ iterazioni (da $2$ a $n$), una addizione ciascuna: $T(n) = n - 1 = \Theta(n)$. Per $n = 5$: $4$ addizioni contro $7$ del ricorsivo; per $n = 40$: $39$ contro $F_{40} - 1 = 165\,580\,140$.

Tabella per $n = 7$:

Osservazione (taglia dell'istanza). Anche $\Theta(n)$ è inefficiente rispetto alla vera taglia dell'istanza. La taglia di $n$ non è $n$, ma il numero di cifre per scriverlo in notazione posizionale, $\text{size}(n) = \Theta(\log n)$ (vedi Problemi computazionali - istanze, soluzioni, correttezza e complessitàUn problema computazionale è una relazione totale (non necessariamente univoca) tra istanze e soluzioni; un algoritmo è una funzione dalle istanze alle soluzioni e risolve il problema se la sua uscita è sempre in relazione con l'ingresso. Correttezza = coerenza con la specifica; complessità = costo in funzione della taglia, per default al caso peggiore, con le istruzioni a costo unitario scelte in modo significativo.Problemi computazionali - istanze, soluzioni, correttezza e complessità →). Quindi ITFIB è esponenziale nella taglia ($n = b^{\text{size}}$) e RFIB addirittura doppiamente esponenziale. Esistono algoritmi con $\Theta(\log n)$ operazioni aritmetiche, cioè lineari nella taglia.

Un algoritmo logaritmico lavora direttamente sugli interi. Vale

$$\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix}, \qquad \text{quindi} \qquad \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n} = \begin{pmatrix} F_n & F_{n-1} \\ F_{n-1} & F_{n-2} \end{pmatrix}$$

(con $F_{-1} = 0$ per far tornare il caso $n = 1$; per esempio la quarta potenza è $\begin{pmatrix} 5 & 3 \\ 3 & 2 \end{pmatrix}$, con $F_4 = 5$, $F_3 = 3$, $F_2 = 2$). Elevando la matrice $2 \times 2$ a potenza con le quadrature successive (Esponenziazione veloce per quadrature successivepotenza x^n con un operatore associativo con elemento neutro, costo = numero di applicazioni dell'operatore; STUPID_POWER costa n-1, la sottostruttura x^n = (x^floor(n/2))^2 (per n dispari per x) dà POWER con T(n) = floor(log2 n) + (numero di bit a 1 di n) - 1, Theta(log n) (caso peggiore 2 floor(log2 n), n = 2^t - 1); versioni iterative POWER2 e POWER3 dalla rappresentazione binaria di n; esempio con la matrice di Fibonacci; il modello a costo unitario vale solo se l'operatore non fa crescere gli operandi.Esponenziazione veloce per quadrature successive →) bastano $\Theta(\log n)$ prodotti di matrici $2 \times 2$. Queste identità sono state controllate con Python per $n \le 39$.

Considerazioni sulla programmazione dinamica

La DP conserva l'idea del divide and conquer (una proprietà di sottostruttura: la soluzione di un'istanza si ottiene da quelle di istanze più piccole), ma cambia il modo di calcolare. Il processo è puramente bottom-up: si parte dalle istanze più piccole e, ricombinando le soluzioni salvate, si arriva alle più grandi. La fase top-down del D&C (scendere dalla radice alle foglie per decidere quali sottoistanze servono) sparisce.

• Vantaggio: si ottiene un algoritmo iterativo, in pratica più veloce (niente costi di ricorsione).
• Svantaggio 1: senza la ricorsione che guida, si risolvono tutte le sottoistanze di taglia inferiore riconducibili alla sottostruttura, anche quelle che servono poco o niente per l'istanza data.
• Svantaggio 2: l'ordine bottom-up va costruito a mano, e in alcuni casi non è ovvio (lo si vede nella Matrix Chain Multiplication).

Condizioni per applicare la DP:

1. il problema ha una proprietà di sottostruttura;
2. le sottoistanze generate compaiono più volte (overlapping subproblems): è questo che giustifica la tabella;
3. lo spazio delle sottoistanze potenzialmente utilizzabili è abbastanza ristretto (polinomiale), perché vanno calcolate e salvate tutte.

Memoizzazione

La memoizzazioneDal latino memo, promemoria: da non confondere con memorizzazione è un approccio ibrido: si mantiene la ricorsione della sottostruttura (e quindi la fase top-down del D&C), ma con una tabella globale a tutte le chiamate in cui salvare le istanze già risolte. L'algoritmo ha due procedure.

1. INIT_X, non ricorsiva: risolve i casi base, inizializza la tabella (casi base più un valore di default, la sentinella, per le istanze ancora da risolvere) e chiama REC_X sull'istanza principale.
2. REC_X, ricorsiva: controlla se la tabella contiene già la soluzione; se sì la restituisce, altrimenti calcola con Divide, Recurse e Conquer, salva in tabella prima di restituire.

Per Fibonacci:

INIT_FIB(n)
  if n <= 1 then return 1
  F[0] <- 1
  F[1] <- 1
  for i <- 2 to n do F[i] <- 0       { 0 = non ancora calcolato }
  return REC_FIB(n)

REC_FIB(i)
  if F[i] = 0 then F[i] <- REC_FIB(i-1) + REC_FIB(i-2)
  return F[i]

Lo $0$ è un buon valore di default perché nessun $F_i$ vale $0$ (sono tutti $\ge 1$). La scelta della sentinella è parte della correttezza: deve essere un valore che la ricorrenza non può mai produrre (per le lunghezze di una sottosequenza si userà $-1$, per un costo minimo $+\infty$). La correttezza discende dalla sottostruttura e da questa scelta.

Albero delle chiamate per $n = 5$ (in ordine di esecuzione; = sono le chiamate che trovano il valore in tabella o sono casi base):

REC(5)
├─ REC(4)
│  ├─ REC(3)
│  │  ├─ REC(2)
│  │  │  ├─ REC(1)     base
│  │  │  └─ REC(0)     base      F[2] = 2
│  │  └─ REC(1)        base      F[3] = 3
│  └─ REC(2)           letto in tabella      F[4] = 5
└─ REC(3)              letto in tabella      F[5] = 8

Analisi della complessità

Non si può usare la ricorrenza per valutare il costo: una ricorrenza descrive l'esecuzione puramente funzionale del D&C, in cui ogni nodo viene espanso. Si analizza l'albero. Per Fibonacci l'albero di $\text{REC\_FIB}(n)$ contiene tutte le istanze di taglia minore di $n$, e ogni istanza non di base $i \in \{2, \dots, n\}$ compare come nodo interno una sola volta (tutte le altre occorrenze sono letture della tabella). Quindi:

• $n - 1$ nodi interni, con lavoro unitario (una addizione);
• l'albero è binario e pieno, quindi $n$ foglie a lavoro nullo;
• $T(n) = n - 1$ addizioni e $2n - 1$ chiamate in tutto.

Per $n = 5$: $4$ addizioni, $9$ chiamate (nell'albero sopra si contano $9$ nodi). Il conteggio è lo stesso di ITFIB; in pratica ITFIB è più veloce perché non ha i costi nascosti della ricorsione.

Sintesi per confronto:

La memoizzazione è poco usata, perché il bottom-up è spesso ugualmente efficiente e senza i costi della ricorsione. Conviene quando la risoluzione top-down evita di calcolare molte sottoistanze (un esempio è la LCS di stringhe simili: Longest Common Subsequence - ricorrenza, tabella e ricostruzionela LCS di X (m caratteri) e Y (n caratteri) è la sottosequenza comune più lunga. Sottoistanze = coppie di prefissi (Theta(mn)). Ricorrenza: l(i,j) = 0 se i = 0 o j = 0; 1 + l(i-1,j-1) se x_i = y_j; max{l(i-1,j), l(i,j-1)} altrimenti. Bottom-up con tabelle l e b (freccia): mn confronti; ricostruzione in O(m+n). Il D&C sulla stessa ricorrenza costa C(m+n,m) - 1 nodi interni nel caso peggiore (esponenziale). Memoizzazione: stessa complessità nel caso peggiore, ma molto meno lavoro su stringhe simili. Spazio ridotto a Theta(min{m,n}) se serve solo la lunghezza.Longest Common Subsequence - ricorrenza, tabella e ricostruzione →) o quando l'ordine bottom-up è difficile da scrivere.

In Python, la memoizzazione è una riga:

from functools import cache

@cache
def fib(n):
    return 1 if n <= 1 else fib(n - 1) + fib(n - 2)

assert [fib(i) for i in range(8)] == [1, 1, 2, 3, 5, 8, 13, 21]

Problemi di ottimizzazione e sottostruttura ottima

Un problema computazionale $\Pi \subseteq I \times S$ è una relazione tra istanze e soluzioni; per un'istanza $i \in I$ le soluzioni ammissibili sono $S(i) = \{s \in S : i \,\Pi\, s\}$. Un problema di ottimizzazione ha una funzione di costo $c : S \to \mathbb{R}$ e chiede la migliore soluzione ammissibile (minimo o massimo di $c$ su $S(i)$), oppure di provare che $S(i) = \emptyset$. Una soluzione $s^*$ è ottima se $c(s^*) = \min / \max \{c(s) : s \in S(i)\}$.

Definizione (sottostruttura ottima). Un problema di ottimizzazione ha la proprietà di sottostruttura ottima se una soluzione ottima di un'istanza si ottiene da soluzioni ottime di istanze più piccole.

Si dimostra quasi sempre con la tecnica del cut-and-paste: si suppone per assurdo che una sottosoluzione contenuta nella soluzione ottima non sia ottima, la si sostituisce con una sottosoluzione ottima della stessa sottoistanza e si ottiene una soluzione complessiva strettamente migliore, in contraddizione con l'ottimalità. La prova della LCS e quella di Matrix Chain usano proprio questo argomento.

Avere un problema di ottimizzazione non implica che serva la DP: anche il D&C (o il greedy, vedi Paradigma greedy - scelta golosa, sottostruttura e selezione delle attivitàIl paradigma greedy compie subito una scelta localmente migliore (scelta greedy), pulisce l'istanza (clean-up) e risolve l'unica sottoistanza residua, con ricorsione di coda eliminabile; il codice è facile, la correttezza no e richiede due proprietà, la scelta greedy (esiste un ottimo che la contiene) e la sottostruttura ottima (cut-and-paste), da cui la correttezza segue per induzione. Caso di studio: la selezione delle attività, con l'algoritmo del primo che finisce, correttezza completa, complessità Theta(n) dopo l'ordinamento e controesempi per le scelte greedy sbagliate.Paradigma greedy - scelta golosa, sottostruttura e selezione delle attività →) può risolverlo. La scelta dipende dalla presenza di sottoistanze ripetute (che rendono il D&C inefficiente) e dalla taglia dello spazio dei sottoproblemi (che devono stare in tabella).

Lo schema del paradigma

Dato un problema di ottimizzazione, un algoritmo di DP si sviluppa in cinque passi.

Schema DP.

1. Sottostruttura ottima. Una relazione tra la soluzione ottima $s^*$ di un'istanza di taglia $n > n_0$ e le soluzioni ottime $s_1^*, \dots, s_k^*$ di istanze di taglia strettamente minore, più la caratterizzazione dei casi base (taglia $\le n_0$). Si dimostra (di solito con cut-and-paste). La presenza di sottoistanze ripetute giustifica la DP.
2. Costo. Una ricorrenza sui costi $c(s^*) = f\big(c(s_1^*), \dots, c(s_k^*)\big)$. 2'. Informazione addizionale. La minima informazione necessaria a ricostruire $s^*$ da $s_1^*, \dots, s_k^*$.
3. Calcolo dei costi, bottom-up (ordine di riempimento coerente con le dipendenze della ricorrenza) oppure top-down memoizzato. 3'. Calcolo dell'informazione addizionale, insieme ai costi.

I passi $2'$ e $3'$ si saltano se interessa solo il costo dell'ottimo e non la soluzione: succede quando il costo è esso stesso una metrica (per esempio la similarità tra due sequenze di DNA, misurata dal numero minimo di cancellazioni e inserzioni; sapere quali operazioni siano contano di meno).

Se serve la soluzione, non si salvano le sottosoluzioni intere (costerebbe troppo spazio e tempo), ma solo l'informazione incrementale: per esempio una freccia, o l'indice di spezzamento. La soluzione ottima si ricostruisce poi in una fase di postprocessing, componendo queste informazioni.

I problemi svolti nelle note seguenti applicano tutti lo stesso schema:

Domande d'esame

1. (Quesito a risposta unica.) Quante addizioni esegue RFIB(6)? Quante ITFIB(6)? Traccia: $T(n) = F_n - 1$, con $F_6 = 13$, quindi $12$ addizioni (e $25$ chiamate); ITFIB ne fa $n - 1 = 5$.
2. (Quesito aperto.) Quali condizioni deve soddisfare un problema perché la programmazione dinamica sia conveniente rispetto al divide and conquer? Traccia: sottostruttura ottima; sottoistanze che si ripetono (altrimenti la tabella non serve, il D&C basta); spazio dei sottoproblemi polinomiale, perché si calcolano e si salvano tutti.
3. (Quesito aperto.) Perché la complessità di un algoritmo memoizzato non si valuta con la ricorrenza del D&C? Qual è il costo di REC_FIB(n)? Traccia: la ricorrenza conta ogni nodo dell'albero, ma nell'albero memoizzato molti nodi sono letture della tabella (lavoro nullo). Si contano i nodi interni: $n - 1$, quindi $T(n) = n - 1$.

Esercizi d'esame svolti su ricorrenze a due indici calcolate con la tabella:

• calcolo iterativo e spazio lineare: Esercizio - ricorrenza c(i,j) con bordi dati da due array, calcolo iterativo e spazio lineare (compito del 18 giugno 2026, es. 2);
• calcolo memoizzato e scelta della sentinella: Esercizio - ricorrenza t(i,j) con calcolo memoizzato e conteggio esatto (compito del 26 giugno 2025, es. 2), Esercizio - ricorrenza c(i,j) con valore di default e conteggio delle operazioni (simulazione d'esame 2023-24, problema 2) e la nota Memoizzazione di ricorrenze triangolari - conteggio esatto e diagonali costantimemoizzazione di M(i,j) = M(i+1,j-1) M(i+1,j) M(i,j-1) sulle coppie 1 <= i <= j <= n, con M(i,i) = 1 e M(i,i+1) = 2. Il codice standard (INIT_M e REC_M, valore di default 0) esegue esattamente (n-1)(n-2) moltiplicazioni, uno nodo interno per ogni coppia con j >= i+2. Ma tutti gli elementi della stessa diagonale hanno lo stesso valore V(l) = V(l-1)^2 V(l-2): con questa osservazione bastano 2(n-2) moltiplicazioni. Lezione: prima di scrivere la tabella conviene cercare regolarità nella ricorrenza.Memoizzazione di ricorrenze triangolari - conteggio esatto e diagonali costanti →;
• ottimizzazione su suffissi, con due ricorrenze intrecciate: Esercizio - costo alternato minimo e massimo di una sottosequenza (simulazione d'esame 2025-26, es. 2).