Che cos’è la programmazione dinamica?

La programmazione dinamica (DP) è una tecnica algoritmica utilizzata per risolvere problemi di ottimizzazione scomponendoli in sottoproblemi più semplici e riutilizzando le soluzioni di questi sottoproblemi per risolvere il problema originale.

La DP viene spesso usata per problemi la cui soluzione può essere espressa ricorsivamente in termini di sottoproblemi più piccoli. La tecnica è detta "dinamica" perché le soluzioni dei sottoproblemi possono essere memorizzate e riutilizzate per risolvere problemi più grandi, rendendo il processo più efficiente rispetto al semplice risolvere il problema più grande da zero.

La DP può essere usata per diversi problemi, come il cammino più breve, la sottosequenza comune più lunga e il sottarray massimo. È particolarmente utile quando il problema presenta sottoproblemi sovrapposti e una sottostruttura ottimale, il che significa che la soluzione ottimale del problema può essere costruita a partire dalle soluzioni ottimali dei suoi sottoproblemi.