Dynamic Programming

La Programmazione Dinamica (DP) è la tecnica di risoluzione dei problemi decisionali multistadio introdotta da Richard Bellman nel suo libro del 1957 (*Dynamic Programming*, Princeton University Press); scompone un problema in sottoproblemi sovrapposti, memorizza i risultati intermedi in una tabella (memoization o tabulation) e risolve ricorsivamente tramite l'equazione di Bellman V(s) = max_a {r(s, a) + γ V(s')}. Il problema dello zaino è l'esempio canonico di DP — Bellman presenta lo schema DP sullo knapsack nel libro del 1957; la complessità O(N×W) è **pseudo-polinomiale** (polinomiale nel valore di W, esponenziale nella sua lunghezza in bit). Altre applicazioni canoniche: cammini minimi (Bellman-Ford), inventario (lot-sizing Wagner-Whitin), sostituzione di attrezzature (Bellman 1955), processi decisionali stocastici (Markov Decision Process), allineamento di sequenze (Needleman-Wunsch), parsing (CYK), ordine di moltiplicazione di catene di matrici. La DP esiste in due forme principali: **DP deterministica** (ogni stadio con esito noto) e **DP stocastica** (ogni stadio con esito probabilistico — processi di Markov). L'applicabilità della DP richiede struttura sub-ottima (gli ottimi dei sottoproblemi si compongono nell'ottimo globale) e sottoproblemi sovrapposti (si ripetono). Approximate Dynamic Programming (ADP) e Stochastic Dual Dynamic Programming (SDDP) estendono la DP a problemi stocastici di grande scala. Bellman 1957 + Bellman e Dreyfus 1962 + Bertsekas 1995 sono i riferimenti canonici.