La programmazione dinamica, quando si fa riferimento al campo dell’informatica, descrive un gruppo di algoritmi informatici simili destinati a risolvere problemi complessi suddividendo il problema in serie di problemi più piccoli. Creata per la prima volta da Richard Bellman negli anni ‘1950, la programmazione dinamica funziona con problemi che sono sottoproblemi sovrapposti o sottostrutture ottimali. Per capire come funziona la programmazione dinamica, è meglio comprendere il concetto alla base di questi due termini.
I sottoproblemi sovrapposti descrivono equazioni complicate che, una volta suddivise in insiemi di equazioni più piccoli, riutilizzano parti delle equazioni più piccole più di una volta per ottenere una risposta. Ad esempio, un’equazione matematica detta di calcolare tutti i possibili risultati utilizzando un insieme di numeri può calcolare lo stesso risultato numerose volte mentre si calcolano altri risultati solo una volta. La programmazione dinamica direbbe a questo problema che dopo aver calcolato il risultato la prima volta dovrebbe salvare quel risultato e inserire la risposta nell’equazione in un secondo momento invece di calcolarla di nuovo. Quando si ha a che fare con processi ed equazioni lunghi e complessi, ciò consente di risparmiare tempo e crea una soluzione più rapida utilizzando molti meno passaggi.
Le sottostrutture ottimali creano una soluzione trovando la migliore risposta a tutti i sottoproblemi e quindi creando la migliore risposta complessiva. Dopo aver suddiviso un problema complesso in problemi più piccoli, il computer utilizza un sistema matematico per determinare quale sia la risposta migliore per ciascun problema. Calcola la risposta al problema originale dalle risposte più piccole. I difetti esistono con questo processo. Sebbene fornisca la soluzione che funziona meglio dal punto di vista matematico, può essere o meno la soluzione migliore nella vita reale, a seconda del tipo di problema e di come si relaziona al mondo reale.
Durante una qualsiasi di queste operazioni, l’algoritmo di programmazione dinamica cerca di trovare il percorso più breve per la soluzione. Può richiedere uno dei due approcci per farlo. L’approccio top-down suddivide l’equazione in equazioni più piccole e riutilizza le risposte per queste equazioni quando necessario. L’approccio dal basso verso l’alto cerca di risolvere il valore matematico più piccolo dopo aver scomposto l’equazione e poi si fa strada verso il più grande da lì. Entrambi gli approcci fanno risparmiare tempo, ma la programmazione dinamica funziona solo quando il problema originale può essere scomposto in equazioni più piccole che a un certo punto vengono riutilizzate per risolvere l’equazione.