La programmazione dinamica (DP) risolve problemi con sottoproblemi sovrapposti e sottostruttura ottimale calcolando ogni sottoproblema una volta e riutilizzando il risultato. I due stili sono memoization (top-down) e tabulation (bottom-up).
La ricorsione ingenua ricalcola gli stessi sottoproblemi in modo esponenziale. DP li memorizza, collassando il lavoro esponenziale in polinomiale.
from functools import lru_cache
@lru_cache(maxsize=None) # cache results automatically
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2) # each n computed once
def fib_table(n):
if n < 2:
return n
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2]) # build up from base cases
return dp[n]
| Memoization | Tabulation | |
|---|---|---|
| Direzione | ricorsione top-down | iterazione bottom-up |
| Calcola | solo stati necessari | tutti gli stati |
| Rischio | stack overflow | nessuno |
| Spazio | può essere ridotto | spesso riducibile a O(1) righe |
Fibonacci: da O(2ⁿ) ingenuo a O(n) tempo, O(n) (o O(1)) spazio.
Usa DP quando i sottoproblemi si sovrappongono. Definisci lo stato e la ricorrenza con attenzione — questa è la parte difficile. Se i sottoproblemi non si sovrappongono, il divide-and-conquer semplice è sufficiente.
DP converte problemi esponenziali intrattabili — cammini più brevi, distanza di edit, knapsack — in problemi efficienti.
La capacità di identificare lo stato e la ricorrenza è tra le più apprezzate nei colloqui su algoritmi.
Sottende sistemi reali dalla strumentazione diff all'allineamento di sequenze in bioinformatica.