Programmazione dinamica: calcolare una cosa sola una volta sola

La programmazione dinamica trasforma ricorsioni esponenziali in algoritmi rapidi con un’idea minima: riconoscere che lo stesso sottoproblema ricorre molte volte, calcolarlo una volta, riusarlo. È lo schema dietro la distanza di edit, l’allineamento di sequenze, l’algoritmo di Viterbi e — sotto un altro nome — l’equazione di Bellman del reinforcement learning.

Perché questo capitolo

Calcolare il cinquantesimo numero di Fibonacci con la ricorsione scritta nel modo più naturale richiede circa due miliardi di chiamate di funzione. Calcolarlo con una tabella di cinquanta caselle richiede cinquanta addizioni. Stesso risultato, stessa ricorrenza, stessa idea matematica: la differenza tra i due numeri è tutta nel modo in cui il calcolo è organizzato. Quella differenza è la programmazione dinamica.

Non è un dettaglio di efficienza marginale. È il passaggio da “intrattabile” a “banale”. Un’enorme classe di problemi — confrontare due stringhe, allineare due sequenze di DNA, trovare il percorso migliore in un grafo, scegliere quali oggetti mettere in uno zaino, decodificare un segnale rumoroso — ha la stessa struttura nascosta: si decompone in sottoproblemi, e gli stessi sottoproblemi tornano molte volte. Chi riconosce questa struttura risolve il problema in tempo polinomiale. Chi non la riconosce scrive una ricorsione che esplode.

C’è un secondo motivo, più profondo, per cui questo capitolo conta in una wiki sull’AI. La programmazione dinamica e il reinforcement learning hanno la stessa radice e lo stesso inventore. L’equazione di Bellman, che regge il calcolo del valore di ogni decisione in un agente che apprende, è una ricorrenza di programmazione dinamica. Value iteration, l’algoritmo che risolve un processo decisionale di Markov, è programmazione dinamica applicata agli stati di quel processo. Capire la versione algoritmica pulita — Fibonacci, distanza di edit — è il modo più diretto per capire la versione probabilistica che si incontra in RL.

E c’è un terzo motivo, vicino al lavoro quotidiano di chi costruisce sistemi che processano linguaggio. Una buona fetta degli algoritmi che stanno sotto il natural language processing classico — l’algoritmo di Viterbi per la decodifica, il CKY per il parsing, la distanza di edit per confrontare un output con un riferimento — sono programmazione dinamica. Anche la beam search, l’algoritmo di decodifica che genera testo nei modelli sequenziali, è una programmazione dinamica “potata”. Riconoscere lo schema comune significa capire una famiglia intera di algoritmi con un solo sforzo, invece di impararli uno per uno come trucchi scollegati.

Contesto

Il nome “programmazione dinamica” è uno dei più fuorvianti dell’informatica, e conviene disinnescarlo subito. “Programmazione” non ha niente a che vedere con lo scrivere codice. È un termine della ricerca operativa degli anni ‘40 e ‘50, dove “program” indicava un piano, una schedulazione: un programma di addestramento militare, un piano logistico. Lo stesso senso che ha in “linear programming”, la programmazione lineare. “Programmazione dinamica” significa quindi, alla lettera, “pianificazione di un processo che evolve nel tempo”.

Il termine viene da Richard Bellman (1920-1984), matematico applicato statunitense che lavora alla RAND Corporation — un think tank finanziato dall’aeronautica militare americana — a partire dalla fine degli anni ‘40. Bellman studia i processi decisionali multi-stadio: situazioni in cui si prendono decisioni in sequenza, ognuna che cambia lo stato del sistema, e si vuole la sequenza complessivamente migliore.

La storia dietro il nome è celebre, e Bellman stesso la racconta nella sua autobiografia Eye of the Hurricane (World Scientific, 1984). Secondo Bellman, il Segretario alla Difesa dell’epoca, Charles “Engine Charlie” Wilson, nutriva una vera avversione per la parola “research” e per la matematica in generale; la RAND operava sotto il suo controllo di bilancio. Bellman aveva bisogno di un nome per quel ramo della matematica che fosse impossibile da attaccare. “Programming” rimandava alla pianificazione, qualcosa di concreto e accettabile. “Dynamic” — sono parole sue — era un aggettivo impossibile da usare in senso peggiorativo: nessun membro del Congresso avrebbe potuto obiettare a qualcosa chiamato “dynamic programming”. Il nome fu scelto come scudo politico, non come descrizione tecnica.

Vale una nota di cautela storiografica. Stuart Russell e Peter Norvig, nel manuale Artificial Intelligence: A Modern Approach, osservano che il racconto non può essere letteralmente vero: il primo articolo di Bellman che usa il termine è del 1952, mentre Wilson diventa Segretario alla Difesa solo nel 1953. La storia è probabilmente abbellita a posteriori. Resta vero il punto che conta: “programming” significa pianificazione, non codice.

Il contributo tecnico di Bellman ha un nome preciso: il principio di ottimalità. La sua formulazione: una politica ottima ha la proprietà che, qualunque siano lo stato e la decisione iniziali, le decisioni rimanenti devono costituire una politica ottima rispetto allo stato che risulta dalla prima decisione. Detto senza gergo: ogni pezzo di una soluzione ottima è a sua volta una soluzione ottima del suo sotto-pezzo. È questa intuizione che permette di scrivere la ricorrenza, e da questa ricorrenza Bellman deriva l’equazione che porta il suo nome.

Il principio nasce in un contesto che con l’informatica c’entra poco: la ricerca operativa e il controllo ottimo. Bellman e i suoi colleghi alla RAND lavoravano su problemi di logistica, scorte, traiettorie — decisioni in sequenza sotto vincoli. La programmazione dinamica si diffonde da subito ben oltre i suoi confini originari: in economia regge il problema del risparmio ottimo di Frank Ramsey, in ingegneria aerospaziale la pianificazione di traiettorie, in bioinformatica l’allineamento di sequenze. Che lo stesso schema affiori in domini così distanti non è una coincidenza: ogni volta che un problema si decompone in stadi e i sottoproblemi si ripetono, la programmazione dinamica è lì in attesa di essere riconosciuta.

Nel grafo di questa Parte, la programmazione dinamica sta accanto agli algoritmi di ricerca. La ricerca BFS e DFS e A* esplorano uno spazio di stati cercando un percorso; la programmazione dinamica risolve problemi che si decompongono in sottoproblemi che si ripetono. I due mondi si toccano — il cammino minimo si può vedere in entrambi i modi — ma l’enfasi è diversa: la ricerca esplora, la programmazione dinamica riusa. E guarda avanti, verso la Parte VII: l’equazione di Bellman e value iteration sono programmazione dinamica indossata da un altro vocabolario.

L’intuizione

Tre angoli, prima di qualsiasi formula. Servono perché la programmazione dinamica è più uno schema mentale che una tecnica meccanica: una volta che lo schema scatta, gli algoritmi si scrivono quasi da soli.

Primo angolo: il quaderno degli appunti

Sei a un esame scritto e ti accorgi che la stessa sotto-domanda — poniamo, “quanto fa quella certa integrale” — compare dentro tre esercizi diversi. Hai due opzioni. La prima: rifare il calcolo da capo ogni volta che serve. La seconda: farlo una volta, scriverlo a margine su un foglio di brutta, e ricopiare il risultato le altre due volte.

La programmazione dinamica è la seconda opzione resa sistematica. C’è un quaderno — la tabella — dove finiscono tutti i risultati già calcolati. Prima di calcolare qualcosa, si guarda il quaderno: se c’è, si copia; se non c’è, si calcola e si annota. Il costo si sposta dal tempo (ricalcolare) allo spazio (la tabella). È uno scambio quasi sempre conveniente, perché ricalcolare un sottoproblema costa molto e annotarne il risultato costa una casella di memoria.

Questo angolo chiarisce anche perché lo scambio sia conveniente solo a una condizione: che la stessa sotto-domanda ricorra davvero. Se ogni sotto-domanda comparisse una volta sola, il quaderno si riempirebbe di annotazioni mai riconsultate — fatica sprecata. Il guadagno è proporzionale a quante volte un risultato viene riusato. È esattamente la proprietà dei sottoproblemi sovrapposti, vista dal lato pratico.

Secondo angolo: l’albero che collassa in un grafo

Guarda l’albero della ricorsione ingenua di Fibonacci. La radice è $F(6)$ . I suoi due figli sono $F(5)$ e $F(4)$ . Ma $F(4)$ compare anche come nipote sotto $F(5)$ . E $F(3)$ compare ancora più volte, $F(2)$ ancora di più. L’albero è gonfio di ripetizioni: lo stesso sotto-albero, identico, ricalcolato in rami diversi.

La programmazione dinamica “incolla” insieme i nodi identici. Tutte le copie di $F(4)$ diventano un nodo solo, a cui puntano più frecce. L’albero ridondante collassa in un grafo aciclico diretto — un DAG, directed acyclic graph, un grafo con frecce e senza cicli — minimo: un nodo per ogni sottoproblema distinto. L’albero aveva un numero esponenziale di nodi; il DAG ne ha un numero lineare. Tutto il guadagno della programmazione dinamica è in questo collasso.

L’osservazione chiave è che il numero di sottoproblemi distinti è ciò che conta davvero, non il numero di volte che la ricorsione ingenua li visiterebbe. La ricorsione ingenua misura il secondo numero — esponenziale; la programmazione dinamica paga solo il primo — polinomiale. Riconoscere che i due numeri sono diversi, e di quanto, è il momento in cui lo schema “scatta”.

Questo angolo dà anche il modo giusto di pensare alla complessità e all’ordine di calcolo. In un DAG di dipendenze, un sottoproblema va calcolato solo dopo tutti quelli da cui dipende: serve un ordine topologico del DAG. E il costo totale è la somma del lavoro fatto su ogni nodo. Torneremo su entrambi i punti.

Terzo angolo: la decomposizione che non perde l’ottimo

C’è un terzo modo di vederla, più vicino allo spirito di Bellman. Immagina di dover trovare il percorso stradale più breve da Milano a Napoli. Sai che passa per Roma. Allora il tratto Milano-Roma di quel percorso deve essere, a sua volta, il percorso più breve da Milano a Roma. Se così non fosse — se esistesse un tratto Milano-Roma più corto — potresti sostituirlo e ottenere un Milano-Napoli ancora più breve, contraddizione.

Questa è la sottostruttura ottima: la soluzione ottima del problema grande contiene, come pezzi, soluzioni ottime di sottoproblemi. È la proprietà che giustifica la decomposizione. Senza di essa, scomporre il problema sarebbe inutile: le soluzioni ottime dei pezzi non si comporrebbero in una soluzione ottima del tutto. Con essa, posso scrivere “la risposta al problema grande è una certa combinazione delle risposte ai sottoproblemi” — e quella frase, resa precisa, è la ricorrenza.

I tre angoli — il quaderno, il collasso albero-DAG, la decomposizione che non perde l’ottimo — descrivono la stessa cosa da tre lati. Il primo dice perché conviene (riusare invece di ricalcolare), il secondo dice quanto conviene (esponenziale che diventa polinomiale), il terzo dice quando è lecito (solo se la sottostruttura è ottima). Tenerli insieme è il modo più solido di interiorizzare lo schema.

Programmazione dinamica e ricorsione: cosa cambia davvero

Conviene fissare un punto che genera confusione. La programmazione dinamica non è “il contrario della ricorsione” né “un’alternativa alla ricorsione”. È ricorsione a cui si è aggiunta la memoria. La ricorrenza — il cuore della programmazione dinamica — è esattamente una definizione ricorsiva: $F(n)$ in termini di $F(n-1)$ e $F(n-2)$ , $d(i,j)$ in termini di $d(i-1,j)$ e simili.

Quello che la programmazione dinamica aggiunge è una sola osservazione: se la ricorsione, lasciata libera, ricalcola gli stessi argomenti molte volte, allora vale la pena ricordare i risultati. La versione top-down lo fa restando ricorsiva e aggiungendo una cache; la versione bottom-up lo fa abbandonando la ricorsione e srotolandola in cicli che riempiono una tabella. Ma la ricorrenza sottostante è la stessa in entrambi i casi, ed è la stessa della ricorsione ingenua. Chi sa scrivere la ricorsione ingenua corretta ha già fatto il lavoro concettuale difficile; la programmazione dinamica è il passo — quasi meccanico — che la rende efficiente.

La meccanica

Le due proprietà, con precisione

Un problema si presta alla programmazione dinamica se, e solo se, ha entrambe queste proprietà.

Sottostruttura ottima. La soluzione ottima del problema si costruisce a partire dalle soluzioni ottime dei suoi sottoproblemi. È la proprietà del terzo angolo qui sopra. È quella che permette di scrivere la ricorrenza. Attenzione: va dimostrata, non assunta. Esistono problemi che sembrano averla e non l’hanno (un esempio nella sezione “Dove si rompe”).

Sottoproblemi sovrapposti. Lo spazio dei sottoproblemi distinti è piccolo: una ricorsione ingenua risolve gli stessi identici sottoproblemi molte volte, invece di generarne sempre di nuovi. È la proprietà del secondo angolo: l’albero è gonfio di ripetizioni.

La seconda proprietà è quella che separa la programmazione dinamica dal divide et impera — lo schema di merge sort e quicksort. Anche il divide et impera decompone il problema in sottoproblemi. Ma in merge sort le due metà dell’array sono sottoproblemi nuovi e indipendenti: non si ripetono mai. Memorizzarli non farebbe risparmiare niente, perché non c’è niente da riusare. La programmazione dinamica è divide et impera più memoria, e la memoria serve a qualcosa solo quando i sottoproblemi si sovrappongono. Senza sovrapposizione, la tabella si riempie di valori che vengono letti una volta sola: pura zavorra.

I due stili: top-down e bottom-up

La stessa ricorrenza si implementa in due modi. Danno la stessa complessità asintotica, ma hanno trade-off diversi e conviene conoscerli entrambi.

Top-down, con memoizzazione. Si scrive la funzione ricorsiva nel modo naturale e le si aggiunge una cache. Prima di calcolare un sottoproblema, si controlla se è già nella cache: se sì lo si restituisce, se no lo si calcola, lo si salva, lo si restituisce. Il calcolo parte dal problema grande e scende verso i casi base, ma tocca solo i sottoproblemi effettivamente necessari.

def fib_topdown(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:                  # casi base: F(0)=0, F(1)=1
        return n
    if n in memo:              # risultato in cache: leggilo
        return memo[n]
    memo[n] = fib_topdown(n - 1, memo) + fib_topdown(n - 2, memo)
    return memo[n]

La riga if n in memo è tutta la programmazione dinamica. Senza quella riga, e senza il salvataggio in memo[n], questo codice è la ricorsione esponenziale ingenua. Con quelle due righe, ogni valore $F(n)$ viene calcolato una volta sola: alla seconda richiesta, la funzione esce subito dalla cache.

Una nota sul termine. “Memoizzazione” (con la doppia “z”, da memo, appunto — non “memorizzazione”) indica proprio questa tecnica: rendere una funzione capace di ricordare i propri risultati passati. È la forma top-down della programmazione dinamica.

Bottom-up, con tabella (tabulation). Si parte dai casi base e si riempie una tabella in ordine, dai sottoproblemi piccoli ai grandi, finché non si raggiunge quello voluto. Niente ricorsione: solo cicli.

def fib_bottomup(n):
    if n < 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1                  # casi base
    for i in range(2, n + 1):  # ordine: i dopo i-1 e i-2
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Il ciclo for va da 2 a $n$ in quest’ordine preciso, e non per caso: la casella dp[i] dipende da dp[i-1] e dp[i-2], quindi quelle due vanno riempite prima. Stabilire un ordine di valutazione corretto — un ordine topologico sul DAG delle dipendenze — è il lavoro extra che il bottom-up chiede e il top-down no (il top-down lo ottiene gratis dalla ricorsione).

In cambio, il bottom-up offre due vantaggi. Niente overhead di chiamate ricorsive, niente rischio di stack overflow per ricorsioni profonde. E spesso permette di ottimizzare la memoria: in Fibonacci, per calcolare dp[i] servono solo le ultime due caselle, non tutta la tabella. Tenendo solo due variabili, lo spazio scende da $O(n)$ a $O(1)$ .

def fib_ottimizzato(n):
    if n < 2:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

Questa ottimizzazione di memoria — tenere solo le ultime righe della tabella — ricorre in molti problemi (distanza di edit, knapsack) e non è possibile nello stile top-down, che ha bisogno della cache intera.

In sintesi: i due stili calcolano la stessa cosa con la stessa complessità asintotica, ma top-down è più vicino alla ricorsione naturale e tocca solo i sottoproblemi necessari, mentre bottom-up evita l’overhead delle chiamate e apre la porta all’ottimizzazione di memoria. La scelta dipende dal problema. Se lo spazio dei sottoproblemi è sparso — molti sottoproblemi teoricamente possibili, pochi davvero raggiunti — il top-down risparmia. Se la dipendenza è locale e la memoria conta, il bottom-up vince. Per la maggior parte dei casi didattici, entrambi vanno bene ed è questione di gusto.

Il template di complessità

C’è una formula che vale per quasi ogni problema di programmazione dinamica, e conviene impararla come si impara una tabellina:

$\text{costo totale} = (\text{numero di sottoproblemi distinti}) \times (\text{costo per sottoproblema})$

Dove “costo per sottoproblema” è il lavoro per combinare i risultati dei sottoproblemi più piccoli, escluso il costo del calcolo ricorsivo — quello è già contato perché ogni sottoproblema appare una volta sola nel conteggio. In parole povere: ogni casella della tabella si riempie una volta; conta quante caselle ci sono e quanto costa riempirne una.

Applichiamo il template:

Fibonacci: $n$ sottoproblemi, $O(1)$ per riempirne uno (una somma). Totale $O(n)$ .
Distanza di edit tra stringhe di lunghezza $m$ e $n$ : $m \cdot n$ sottoproblemi, $O(1)$ ciascuno. Totale $O(m \cdot n)$ .
Longest common subsequence: $m \cdot n$ sottoproblemi, $O(1)$ ciascuno. Totale $O(m \cdot n)$ .
Knapsack 0/1 con $n$ oggetti e capacità $W$ : $n \cdot W$ sottoproblemi, $O(1)$ ciascuno. Totale $O(n \cdot W)$ .

Questo template spiega da dove viene il guadagno. La ricorsione ingenua di Fibonacci è $O(\varphi^n)$ — esponenziale, dove $\varphi \approx 1{,}618$ è la sezione aurea — perché l’albero ricorsivo ha circa $\varphi^n$ nodi. La programmazione dinamica la rende $O(n)$ perché i sottoproblemi distinti sono solo $n$ . La differenza tra $\varphi^n$ e $n$ non è un’ottimizzazione: è la differenza tra un calcolo che non finisce mai e uno istantaneo. Per il legame generale tra notazione asintotica e scaling vedi il capitolo complessita-big-o (in preparazione).

Le tre domande che progettano un algoritmo di programmazione dinamica

Una volta interiorizzato il template, ogni problema di programmazione dinamica si affronta rispondendo, nell’ordine, a tre domande. Sono il metodo che vale la pena memorizzare al posto dei singoli esempi.

Prima domanda: cos’è un sottoproblema? Bisogna definire con precisione la quantità che la tabella conterrà, e da quali parametri dipende. In Fibonacci il sottoproblema è indicizzato da un parametro ( $n$ ); nella distanza di edit da due ( $i, j$ ); nel knapsack da due, di cui uno numerico ( $i, c$ ). Sbagliare qui — dimenticare un parametro da cui la soluzione in realtà dipende — è l’errore che produce ricorrenze plausibili ma scorrette.

Seconda domanda: qual è la ricorrenza? Come si esprime la soluzione di un sottoproblema in funzione di sottoproblemi più piccoli, e quali sono i casi base che fermano la ricorsione. È il passo che richiede la sottostruttura ottima: senza di essa la ricorrenza non esisterebbe.

Terza domanda: qual è l’ordine di valutazione? In quale sequenza vanno riempite le caselle, perché ogni casella sia calcolata dopo tutte quelle da cui dipende. È un ordine topologico sul DAG delle dipendenze. Il top-down lo risolve gratis (ci pensa la ricorsione); il bottom-up chiede di stabilirlo a mano, di solito con uno o più cicli annidati nell’ordine giusto.

Risposte a queste tre domande, e l’algoritmo è scritto. Tutto il resto — la scelta tra dict e array per la tabella, l’ottimizzazione di memoria — è dettaglio implementativo.

Quando il costo per sottoproblema non è costante

Negli esempi visti finora il costo per sottoproblema è $O(1)$ : per riempire una casella si combina un numero fisso di caselle vicine. Non è sempre così, e il template lo gestisce comunque — basta sostituire il fattore giusto.

Il caso classico è la moltiplicazione di una catena di matrici (matrix chain multiplication). Moltiplicare una sequenza di matrici $A_1 \cdot A_2 \cdots A_n$ dà sempre lo stesso risultato, ma il costo dipende dall’ordine con cui si mettono le parentesi: moltiplicare una matrice $10 \times 100$ per una $100 \times 5$ costa $10 \cdot 100 \cdot 5 = 5000$ operazioni scalari, e l’ordine sbagliato su una catena lunga può costare ordini di grandezza in più. Il problema: trovare la parentesizzazione di costo minimo.

Il sottoproblema $m(i, j)$ è il costo minimo per moltiplicare il tratto di catena da $A_i$ ad $A_j$ . La ricorrenza prova ogni punto $k$ dove spezzare il tratto in due:

$m(i, j) = \min_{i \le k < j} \big[\, m(i, k) + m(k+1, j) + \text{costo della moltiplicazione finale} \,\big]$

Qui il costo per sottoproblema non è $O(1)$ : riempire la casella $m(i,j)$ richiede di provare tutti i punti di spezzamento $k$ , che sono fino a $n$ . Il template diventa: $O(n^2)$ sottoproblemi (tutte le coppie $i \le j$ ) per $O(n)$ di costo ciascuno, totale $O(n^3)$ . È un esempio utile perché mostra che la formula “numero di sottoproblemi per costo per sottoproblema” non assume nulla sul secondo fattore: lo si misura caso per caso.

Esempi

Cinque esempi classici, dal più semplice al più ricco. Sono il vocabolario di base: chi li riconosce a vista riconosce la programmazione dinamica ovunque si nasconda.

Esempio 1 — Fibonacci, l’esempio canonico

Lo abbiamo già usato come filo conduttore, e per una buona ragione: è il caso in cui la ricorrenza è banale ( $F(n) = F(n-1) + F(n-2)$ ) e il guadagno è spettacolare e immediato da vedere. Mettiamo i numeri uno accanto all’altro.

Per calcolare $F(50)$ , la ricorsione ingenua fa circa $2{,}0 \times 10^9$ chiamate di funzione — qualche secondo di calcolo, e cresce così in fretta che $F(90)$ è già fuori portata su qualsiasi macchina. La versione con programmazione dinamica fa 50 addizioni. Stessa formula, stesso risultato: $F(50) = 12\,586\,269\,025$ . Tutto il divario è nella riga if n in memo.

Fibonacci è anche l’esempio con cui si vede meglio il “collasso dell’albero in DAG” del secondo angolo: l’albero ricorsivo di $F(6)$ ha 25 nodi, di cui solo 7 distinti ( $F(0)$ fino a $F(6)$ ). La programmazione dinamica calcola quei 7 e basta.

Conviene mettere le due versioni una accanto all’altra per vedere quanto poco le separa. La ricorsione ingenua:

def fib_ingenuo(n):
    if n < 2:
        return n
    return fib_ingenuo(n - 1) + fib_ingenuo(n - 2)

Funzionalmente corretta, e per $n$ piccoli istantanea. Ma il numero di chiamate cresce come $\varphi^n$ : per $n = 35$ è già nell’ordine dei dieci milioni, per $n = 50$ dei due miliardi. La versione con memoizzazione, vista nella sezione sulla meccanica, aggiunge una sola riga di controllo (if n in memo) e collassa $\varphi^n$ in $n$ . Lo stesso albero, gli stessi rami: la programmazione dinamica li percorre una volta sola.

Si noti una cosa non ovvia: la versione ingenua e quella con memoizzazione hanno lo stesso identico albero di chiamate logiche. La memoizzazione non cambia cosa viene calcolato, cambia quante volte. È questa la natura della programmazione dinamica: non un algoritmo nuovo, ma la stessa ricorsione resa consapevole di non doversi ripetere.

Esempio 2 — La distanza di edit (Levenshtein)

Date due stringhe, qual è il numero minimo di operazioni — inserire un carattere, cancellarne uno, sostituirne uno — per trasformare la prima nella seconda? Questa quantità si chiama distanza di edit o distanza di Levenshtein, dal nome di Vladimir Levenshtein, matematico sovietico che la definisce nel 1965 studiando la correzione di errori nei codici. L’algoritmo di programmazione dinamica che la calcola è dovuto a Robert Wagner e Michael Fischer, nel paper The String-to-String Correction Problem (Journal of the ACM, 1974).

Il sottoproblema: $d(i, j)$ è la distanza di edit tra i primi $i$ caratteri di $A$ e i primi $j$ caratteri di $B$ . La ricorrenza:

$d(i,j) = \begin{cases} d(i-1, j-1) & \text{se } A[i] = B[j] \\ 1 + \min\big(d(i-1,j),\; d(i,j-1),\; d(i-1,j-1)\big) & \text{altrimenti} \end{cases}$

In parole: se gli ultimi due caratteri coincidono, non serve nessuna operazione su di loro, e la distanza è quella dei prefissi più corti di uno. Se non coincidono, bisogna spendere un’operazione, e si sceglie la più economica delle tre: $d(i-1,j)$ corrisponde a cancellare $A[i]$ , $d(i,j-1)$ a inserire $B[j]$ , $d(i-1,j-1)$ a sostituire $A[i]$ con $B[j]$ . I casi base: $d(i, 0) = i$ (per trasformare un prefisso di $i$ caratteri nella stringa vuota servono $i$ cancellazioni) e $d(0, j) = j$ .

Concretamente, trasformare “gatto” in “ratti”: la tabella $6 \times 6$ si riempie riga per riga e dà distanza 2 — una sostituzione (g→r) e una sostituzione (o→i). Il costo è $O(m \cdot n)$ : una casella per ogni coppia di prefissi, $O(1)$ per riempirne una.

Vale la pena vedere la tabella riempita per intero, perché è il modo più concreto di capire come la programmazione dinamica “costruisce” la risposta. Confrontiamo “casa” (4 lettere) e “cara” (4 lettere). La tabella è $5 \times 5$ ; la riga 0 e la colonna 0 sono i casi base ( $d(i,0)=i$ , $d(0,j)=j$ ):

        ""   c    a    r    a
   ""    0   1    2    3    4
    c    1   0    1    2    3
    a    2   1    0    1    2
    s    3   2    1    1    2
    a    4   3    2    2    1

Si legge cella per cella. La cella (s, r) — quarta riga, quarta colonna — confronta “cas” con “car”: gli ultimi caratteri ‘s’ e ‘r’ differiscono, quindi il valore è $1 + \min(d(\text{ca},\text{car})=2,\ d(\text{cas},\text{ca})=2,\ d(\text{ca},\text{ca})=0) = 1 + 0 = 1$ , ottenuto dalla diagonale (una sostituzione s→r). La cella in basso a destra vale 1: trasformare “casa” in “cara” costa una sola operazione, la sostituzione della ‘s’ con la ‘r’. La tabella non solo dà il numero, ma — seguendo a ritroso da quale vicina ogni valore è stato derivato — ricostruisce quali operazioni servono.

In codice, lo stile bottom-up:

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i           # casi base: i cancellazioni
    for j in range(n + 1):
        dp[0][j] = j           # casi base: j inserimenti
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],      # cancella
                                   dp[i][j - 1],      # inserisci
                                   dp[i - 1][j - 1])  # sostituisci
    return dp[m][n]

I due cicli annidati scandiscono la tabella riga per riga, sinistra-destra: l’ordine di valutazione corretto, perché ogni cella dp[i][j] dipende solo da celle già riempite (sopra, a sinistra, in diagonale-sopra-sinistra). Notare che ogni casella dipende solo dalla riga corrente e da quella precedente: si potrebbe tenere solo due righe e scendere a $O(n)$ di spazio invece di $O(m \cdot n)$ — l’ottimizzazione di memoria vista per Fibonacci, applicata qui.

Esempio 3 — Longest common subsequence

La longest common subsequence (LCS) di due stringhe è la più lunga sequenza di caratteri che compare in entrambe nello stesso ordine, non necessariamente in posizioni contigue. Per “AGCAT” e “GAC” la LCS è “GA” oppure “AC”, lunghezza 2.

Il sottoproblema: $L(i, j)$ è la lunghezza della LCS dei prefissi $A[1..i]$ e $B[1..j]$ . La ricorrenza:

$L(i,j) = \begin{cases} 0 & \text{se } i = 0 \text{ o } j = 0 \\ 1 + L(i-1, j-1) & \text{se } A[i] = B[j] \\ \max\big(L(i-1, j),\; L(i, j-1)\big) & \text{altrimenti} \end{cases}$

Quando gli ultimi caratteri coincidono, fanno parte della LCS e si aggiunge 1 alla LCS dei prefissi più corti. Quando non coincidono, almeno uno dei due non fa parte della LCS, e si prova a scartarlo da una stringa o dall’altra, tenendo il caso migliore. Stessa complessità $O(m \cdot n)$ della distanza di edit, e per buona ragione: i due problemi sono strettamente imparentati.

In codice:

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

La somiglianza con il codice della distanza di edit non è casuale: stessa tabella, stessa scansione, ricorrenza quasi identica. Cambia solo cosa si fa quando i caratteri coincidono o no. È un buon promemoria del fatto che la programmazione dinamica è uno schema: una volta che lo si vede in un problema, lo si riconosce negli altri.

L’LCS non è un esercizio da manuale: è il cuore del comando diff e di ogni strumento che mostra le differenze tra due versioni di un file. La parte “invariata” tra due file è esattamente la loro LCS riga per riga; tutto il resto è “aggiunto” o “rimosso”. Ogni volta che si guarda un diff di Git, sotto sta girando una programmazione dinamica.

Esempio 4 — Knapsack 0/1, quando il sottoproblema ha due indici

Hai uno zaino che regge un peso massimo $W$ e $n$ oggetti, ognuno con un peso e un valore. Vuoi il sottoinsieme di oggetti di valore totale massimo che sta nello zaino. “0/1” significa che ogni oggetto si prende intero o non si prende: niente metà oggetto.

Il sottoproblema ha due parametri: $K(i, c)$ è il valore massimo ottenibile usando solo i primi $i$ oggetti con una capacità $c$ . La ricorrenza:

$K(i, c) = \max\big(\underbrace{K(i-1, c)}_{\text{salto l'oggetto } i},\; \underbrace{v_i + K(i-1,\, c - p_i)}_{\text{prendo l'oggetto } i,\ \text{se } p_i \le c}\big)$

dove $v_i$ e $p_i$ sono valore e peso dell’oggetto $i$ . Per ogni oggetto si decide: lo lascio (e resto con la stessa capacità e un oggetto in meno da considerare) o lo prendo (e guadagno il suo valore, ma la capacità residua cala del suo peso). Si tiene la scelta migliore. Il caso base è $K(0, c) = 0$ : con zero oggetti il valore è zero.

La tabella è $n \times W$ , quindi il costo è $O(n \cdot W)$ . In codice, bottom-up:

def knapsack(pesi, valori, W):
    n = len(pesi)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for c in range(W + 1):
            dp[i][c] = dp[i - 1][c]            # salto l'oggetto i
            if pesi[i - 1] <= c:               # se ci sta, provo a prenderlo
                con = valori[i - 1] + dp[i - 1][c - pesi[i - 1]]
                dp[i][c] = max(dp[i][c], con)
    return dp[n][W]

Qui c’è una sottigliezza che vale la pena anticipare — la riprendiamo in “Dove si rompe”: $O(n \cdot W)$ sembra polinomiale ma non lo è davvero, perché $W$ è un valore numerico, non la dimensione dell’input.

Esempio 5 — Change-making, quando il greedy sbaglia

Dato un insieme di tagli di moneta e un importo da pagare, qual è il numero minimo di monete? Il sottoproblema: $C(a)$ è il minimo numero di monete per fare esattamente l’importo $a$ . La ricorrenza:

$C(a) = \begin{cases} 0 & \text{se } a = 0 \\ 1 + \min_{t \in \text{tagli},\ t \le a} C(a - t) & \text{altrimenti} \end{cases}$

Per fare $a$ , si usa una moneta di un certo taglio $t$ e si risolve il sotto-importo $a - t$ ; si prova ogni taglio e si tiene il migliore.

Questo esempio merita un posto in lista perché mostra quando serve la programmazione dinamica. La strategia ingenua per il resto è greedy: prendi sempre la moneta più grande che ci sta, ripeti. Per le monete dell’euro o del dollaro funziona sempre, e per questo sembra ovvia. Ma per un sistema di tagli arbitrario fallisce. Tagli $\{1, 3, 4\}$ , importo 6: il greedy prende 4, poi 1, poi 1 — tre monete. L’ottimo è $3 + 3$ , due monete. Il greedy ha imboccato una strada localmente sensata e si è chiuso fuori dall’ottimo.

In codice, bottom-up, con float('inf') a marcare gli importi non realizzabili:

def change_making(tagli, importo):
    dp = [0] + [float('inf')] * importo
    for a in range(1, importo + 1):
        for t in tagli:
            if t <= a and dp[a - t] + 1 < dp[a]:
                dp[a] = dp[a - t] + 1
    return dp[importo] if dp[importo] != float('inf') else -1

La programmazione dinamica non ha il problema del greedy perché, attraverso la ricorrenza, considera tutte le combinazioni di scelte invece di impegnarsi sulla prima che sembra buona. Per il sistema di tagli $\{1,3,4\}$ e importo 6, il ciclo riempie dp[6] valutando ogni taglio e trova 2, l’ottimo, dove il greedy si ferma a 3. Quando il greedy basta, è più veloce e va usato. Quando non basta — e capire quando non basta è metà del mestiere — serve la programmazione dinamica.

Applicazioni pratiche

La programmazione dinamica non è folklore da manuale di algoritmi: è il motore di cose che si usano ogni giorno, spesso senza saperlo.

L’algoritmo di Viterbi. Dato un Hidden Markov Model — un modello probabilistico in cui un processo passa per stati nascosti e a ogni stato emette un’osservazione visibile — l’algoritmo di Viterbi trova la sequenza di stati nascosti più probabile che spiega le osservazioni viste. È programmazione dinamica pura: il sottoproblema è “la probabilità del cammino più probabile che termina nello stato $k$ al tempo $t$ ”, e la ricorrenza lo lega ai valori al tempo $t-1$ . Andrew Viterbi lo propose nel 1967 per decodificare codici convoluzionali su canali di comunicazione rumorosi. Lo stesso algoritmo è stato poi riscoperto, in modo indipendente, almeno sette volte in domini diversi — Needleman-Wunsch in bioinformatica, Wagner-Fischer per le stringhe ne sono due — segno che la struttura matematica è la stessa sotto travestimenti diversi. Viterbi è stato il cuore dei sistemi di speech recognition degli anni ‘70 e ‘80 e del part-of-speech tagging classico in NLP. È il tema del prossimo capitolo, viterbi (in preparazione).

Il CKY parsing. L’algoritmo di Cocke-Kasami-Younger costruisce tutti gli alberi sintattici possibili di una frase rispetto a una grammatica context-free. È programmazione dinamica su una tabella triangolare: il sottoproblema è “quali simboli grammaticali possono generare la sotto-frase dalla parola $i$ alla parola $j$ ”, riempito per span via via più lunghi. Con probabilità associate alle regole grammaticali, CKY restituisce l’analisi sintattica più probabile — chiamata appunto “Viterbi parse”, a sottolineare la parentela con l’algoritmo precedente.

L’allineamento di sequenze in bioinformatica. Confrontare due filamenti di DNA o due proteine — capire dove si somigliano e dove divergono — si fa con gli algoritmi di Needleman-Wunsch (allineamento globale, 1970) e Smith-Waterman (allineamento locale, 1981). Sono la stessa tabella della distanza di edit, con uno schema di punteggio per match, mismatch e gap. È uno degli usi più consolidati della programmazione dinamica, e uno dei motivi per cui lo schema è insegnato in ogni corso di biologia computazionale.

La distanza di edit nella valutazione di output testuali. Quando si misura quanto la trascrizione prodotta da un sistema di speech recognition differisce dal riferimento corretto, la metrica standard — il Word Error Rate — è una distanza di edit calcolata sulle parole invece che sui caratteri. Sotto la metrica gira una programmazione dinamica $O(m \cdot n)$ . Più in generale, ogni volta che si confronta l’output di un sistema con un testo di riferimento “carattere per carattere” o “parola per parola”, la distanza di edit è uno degli strumenti di base.

Il diff nel codice e negli strumenti di sviluppo. La longest common subsequence, vista negli esempi, è il motore del comando diff e quindi di ogni vista di differenze in Git, di ogni code review che mostra righe aggiunte e rimosse, di ogni applicazione di una patch. Quando un agente di coding genera una modifica come diff invece che riscrivendo l’intero file, sotto sta sfruttando — direttamente o indirettamente — un algoritmo di programmazione dinamica che individua il sottoinsieme massimo di righe rimaste invariate. È uno degli usi più quotidiani e meno visibili dello schema: ogni sviluppatore lo invoca decine di volte al giorno senza pensarci.

Il ponte verso il reinforcement learning. È l’applicazione concettualmente più importante per chi studia AI. Un processo decisionale di Markov (MDP) descrive un agente che, in ogni stato, sceglie un’azione, riceve una ricompensa e transisce a un nuovo stato. L’equazione di Bellman per un MDP ha la forma:

$V(s) = \max_a \Big[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V(s') \Big]$

dove $V(s)$ è il valore dello stato $s$ , $R$ la ricompensa, $\gamma$ il fattore di sconto, $P$ la probabilità di transizione. Si guardi la forma, ignorando i simboli: il valore di uno stato è definito in funzione del valore degli altri stati. È una ricorrenza. Ha esattamente la struttura logica della ricorrenza di Fibonacci o della distanza di edit — “la soluzione del problema grande è una combinazione delle soluzioni dei sottoproblemi” — con due differenze: c’è un $\max$ (la scelta dell’azione) e c’è una somma pesata (l’aspettazione sulle transizioni stocastiche).

Value iteration — l’algoritmo che risolve un MDP applicando ripetutamente l’equazione di Bellman come aggiornamento, finché i valori smettono di cambiare — è programmazione dinamica applicata agli stati dell’MDP. Non è un’analogia didattica: è un’equivalenza, ed è il modo in cui Richard Sutton e Andrew Barto la classificano nel manuale di riferimento Reinforcement Learning: An Introduction (MIT Press, 2018), che dedica un intero capitolo intitolato “Dynamic Programming” proprio a value iteration e policy iteration. Il legame è anche di filiazione storica documentata: Bellman è la radice comune sia della programmazione dinamica algoritmica sia del formalismo MDP. Il reinforcement learning vero e proprio — Q-learning e successori — nasce quando lo spazio degli stati è troppo grande per stare in una tabella, o quando le probabilità di transizione non sono note: allora la programmazione dinamica esatta si sostituisce con stime ottenute campionando. Ma lo scheletro — ricorrenza, memorizzazione, iterazione fino a un punto fisso — resta quello di Bellman.

Dove si rompe

La programmazione dinamica è potente ma non onnipotente, e ha un buon numero di modi di non funzionare o di essere fraintesa. Questa sezione conta quanto le precedenti.

Quando la sottostruttura ottima non c’è. È l’errore di progettazione più insidioso, perché il codice gira lo stesso e dà una risposta — solo che è sbagliata. Il controesempio classico è il longest simple path: il cammino più lungo tra due nodi di un grafo senza ripetere nodi. Sembra speculare al cammino minimo, e il cammino minimo ha sottostruttura ottima. Ma il cammino più lungo no: se concateno il cammino più lungo da A a B con quello da B a C, i due pezzi possono passare per uno stesso nodo, e il risultato non è più un cammino “semplice”. Le soluzioni ottime dei pezzi non si compongono in una soluzione valida del tutto. Applicare la programmazione dinamica qui produce numeri privi di senso. Morale: la sottostruttura ottima va dimostrata caso per caso, mai assunta perché “il problema sembra simile a un altro”.

Quando i sottoproblemi non si sovrappongono. Se i sottoproblemi sono tutti distinti, la tabella si riempie di valori letti una volta sola: la programmazione dinamica degenera in divide et impera con un costo di memoria in più e zero benefici. Memoizzare una funzione che non ricalcola mai niente aggiunge solo l’overhead della cache. Prima di applicare lo schema, va verificato che la sovrapposizione ci sia davvero.

La trappola della complessità pseudo-polinomiale. Il knapsack 0/1 in $O(n \cdot W)$ sembra un algoritmo polinomiale, ma non lo è nel senso tecnico. La dimensione dell’input non è $W$ : è il numero di bit necessari a scriverlo, cioè circa $\log_2 W$ . Un algoritmo $O(n \cdot W)$ è dunque $O(n \cdot 2^{\log_2 W})$ — esponenziale nella lunghezza dell’input. Si dice pseudo-polinomiale: polinomiale nel valore numerico, esponenziale nella sua codifica. La conseguenza pratica è netta: il knapsack 0/1 è un problema NP-completo, e la programmazione dinamica lo risolve in tempo ragionevole solo finché $W$ resta piccolo. Per $W$ dell’ordine di $10^{12}$ , la tabella non sta in memoria e l’algoritmo è inutilizzabile. La programmazione dinamica non rende magicamente trattabili i problemi NP-difficili; li rende trattabili solo quando un parametro numerico è contenuto.

Il costo di memoria. Lo scambio “tempo contro spazio” non è sempre conveniente. Una programmazione dinamica con un sottoproblema indicizzato da tre o quattro parametri ha una tabella di dimensione pari al prodotto dei range di quei parametri, e quel prodotto esplode in fretta. Una tabella $O(n^3)$ o $O(n^4)$ può eccedere la memoria disponibile molto prima che il tempo diventi un problema. Le ottimizzazioni di memoria — tenere solo le ultime righe — aiutano, ma non sempre sono possibili: funzionano solo se la dipendenza è “locale” (la riga $i$ dipende solo dalle poche righe precedenti).

“Programmazione dinamica” non significa “programmare in modo dinamico”. Vale la pena ripeterlo, perché è il fraintendimento più comune in assoluto. Non c’entra niente con il codice che cambia a runtime, con la tipizzazione dinamica o con la metaprogrammazione. È pianificazione (in senso di ricerca operativa) di un processo a stadi. Il nome, come abbiamo visto, fu scelto da Bellman per ragioni quasi di pubbliche relazioni, non di descrizione tecnica.

Programmazione dinamica non è memoizzazione, e non è greedy. Due confusioni frequenti. La memoizzazione è una tecnica di implementazione — la variante top-down: si può fare programmazione dinamica bottom-up senza memoizzare nel senso classico, riempiendo una tabella con dei cicli. La programmazione dinamica è il riconoscimento che il problema ha le due proprietà strutturali; la memoizzazione è solo uno dei due modi di sfruttarlo. Quanto al greedy: anche il greedy decompone il problema, ma fa una scelta localmente ottima e non torna mai indietro. È corretto solo per problemi con una proprietà aggiuntiva (la greedy choice property). La programmazione dinamica, considerando tutte le combinazioni tramite la ricorrenza, è più costosa ma corretta anche quando il greedy sbaglia — come nel change-making con tagli arbitrari.

La ricostruzione della soluzione, non solo del suo valore. La tabella, riempita, dà il valore della soluzione ottima: la distanza di edit è 2, il valore massimo nello zaino è 47. Ma spesso si vuole anche la soluzione stessa — quali operazioni di edit, quali oggetti nello zaino. Recuperarla richiede un passo extra: ripercorrere la tabella a ritroso dalla cella finale, ricostruendo a ogni passo quale scelta ha prodotto quel valore. È un’operazione $O(m + n)$ in più, di solito facile, ma va prevista: chi scrive solo la ricorrenza del valore e poi si accorge di volere anche la soluzione deve aggiungere il backtracking, o memorizzare a ogni cella la scelta fatta. Dimenticarsene è una svista frequente.

Non sempre la programmazione dinamica è la scelta giusta. Anche quando le due proprietà ci sono, possono esistere algoritmi migliori. Il cammino minimo da una sorgente in un grafo con archi non negativi si risolve con Dijkstra in $O((V + E) \log V)$ , spesso più efficiente di una programmazione dinamica naive; alcuni problemi hanno soluzioni in forma chiusa (Fibonacci ha una formula esplicita, quella di Binet, che dà $F(n)$ in tempo costante a meno della precisione aritmetica). La programmazione dinamica è uno strumento potente e generale, non l’unico né sempre il migliore. Riconoscere quando un greedy basta, quando una formula chiusa esiste, quando un algoritmo specializzato vince, fa parte della stessa competenza che riconosce quando serve la programmazione dinamica.

Il vero lavoro è trovare la ricorrenza. Una volta che la ricorrenza giusta è scritta, l’implementazione — top-down o bottom-up — è quasi meccanica. Ma trovare la ricorrenza giusta, cioè definire bene cos’è un “sottoproblema” e come si compone, è un atto di progettazione che nessuno schema automatizza. Sbagliare la definizione del sottoproblema — dimenticare un parametro da cui la soluzione in realtà dipende — produce ricorrenze che sembrano corrette e non lo sono. È lì che si concentra la difficoltà, ed è per questo che la programmazione dinamica resta un argomento ostico anche per chi ne conosce a memoria gli esempi classici. Il consiglio operativo: scrivere prima la ricorsione ingenua corretta, verificarla su input piccoli, e solo dopo aggiungere la cache. Se la ricorsione ingenua è giusta, la versione con programmazione dinamica calcola lo stesso e più in fretta; se è sbagliata, lo si scopre su un esempio piccolo invece che dopo aver costruito una tabella complicata.

Collegamenti

Equazione di Bellman — l’equazione di Bellman è una ricorrenza di programmazione dinamica applicata a un processo decisionale di Markov; stessa idea, stesso inventore. Filiazione storica diretta.
Value iteration e policy iteration — value iteration è programmazione dinamica sugli stati di un MDP. Equivalenza, non analogia: lo stesso schema sotto un altro vocabolario.
Processo decisionale di Markov — il formalismo su cui la programmazione dinamica di Bellman opera quando il processo è stocastico e ci sono decisioni da prendere.
Q-learning — cosa succede alla programmazione dinamica quando lo spazio degli stati è troppo grande per una tabella o le transizioni non sono note: si campiona invece di calcolare esattamente.
viterbi (in preparazione) — l’algoritmo di Viterbi è programmazione dinamica applicata agli Hidden Markov Model; il prossimo capitolo di questa Parte.
beam-search (in preparazione) — la beam search è una programmazione dinamica “potata”, che tiene solo i $k$ stati parziali migliori; l’approssimazione pratica quando la tabella esatta è troppo grande.
Monte Carlo Tree Search — la via opposta alla programmazione dinamica quando l’albero non sta in memoria e non c’è una valutazione esatta: campionare invece di tabulare.
Ricerca non informata: BFS e DFS — la ricerca esplora uno spazio di stati, la programmazione dinamica riusa sottoproblemi; il cammino minimo si lascia leggere in entrambi i modi.
graph-algorithms-base (in preparazione) — Dijkstra, Bellman-Ford e Floyd-Warshall sono, tutti e tre, programmazione dinamica su grafi.
complessita-big-o (in preparazione) — il template “numero di sottoproblemi per costo per sottoproblema” è analisi di complessità asintotica applicata.

Per andare oltre

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms (MIT Press) — il capitolo sulla programmazione dinamica è il riferimento didattico standard: sottostruttura ottima, sottoproblemi sovrapposti, matrix chain multiplication, LCS, template di complessità.
Robert A. Wagner, Michael J. Fischer, The String-to-String Correction Problem (Journal of the ACM, 1974) — il paper originale dell’algoritmo $O(m \cdot n)$ per la distanza di edit. Breve e leggibile.
Richard S. Sutton, Andrew G. Barto, Reinforcement Learning: An Introduction, 2a ed. (MIT Press, 2018) — il capitolo 4, “Dynamic Programming”, mostra esplicitamente che value iteration e policy iteration sono programmazione dinamica applicata agli MDP. Disponibile gratuitamente online.
Stuart Dreyfus, Richard Bellman on the Birth of Dynamic Programming (Operations Research, vol. 50 n. 1, 2002) — ricostruzione storica del racconto di Bellman sull’origine del nome e del metodo, con le citazioni dall’autobiografia Eye of the Hurricane.
MIT 6.006, Introduction to Algorithms — le lezioni sulla programmazione dinamica (materiale su MIT OpenCourseWare) presentano lo schema “definire il sottoproblema, scrivere la ricorrenza, stabilire l’ordine” come metodo riutilizzabile, con molti esempi svolti.

Una nota finale per chi vuole davvero impadronirsi dello schema: gli esempi classici di questo capitolo vanno implementati a mano almeno una volta, partendo dalla ricorsione ingenua e aggiungendo la cache. La programmazione dinamica si capisce con le dita, non solo con gli occhi.