Cos'è la programmazione dinamica?
La programmazione dinamica, quando si riferisce al campo dell'informatica, descrive un gruppo di algoritmi informatici simili intesi a risolvere problemi complessi suddividendo il problema in gruppi di problemi minori. Creata per la prima volta da Richard Bellman negli anni '50, la programmazione dinamica funziona con problemi che si sovrappongono a sottoproblemi 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, se suddivise in insiemi di equazioni più piccoli, riutilizzano più volte parti delle equazioni più piccole per raggiungere una risposta. Ad esempio, un'equazione matematica che dice di calcolare tutti i possibili risultati usando una serie di numeri può calcolare lo stesso risultato numerose volte calcolando 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 collegare la risposta all'equazione in un secondo momento invece di calcolarlo di nuovo. Quando si ha a che fare con processi ed equazioni lunghi e complessi, questo fa risparmiare tempo e crea una soluzione più veloce usando molti meno passaggi.
Le sottostrutture ottimali creano una soluzione trovando la risposta migliore a tutti i sottoproblemi e quindi creando la migliore risposta globale. Dopo aver suddiviso un problema complesso in problemi minori, il computer utilizza quindi 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. Mentre offre la soluzione che funziona matematicamente al meglio, può o meno essere la soluzione migliore nella vita reale, a seconda del tipo di problema e di come si collega al mondo reale.
Durante una di queste operazioni, l'algoritmo di programmazione dinamica cerca di trovare il percorso più breve per la soluzione. A tale scopo può essere necessario uno dei due approcci. L'approccio top-down suddivide l'equazione in equazioni più piccole e riutilizza le risposte per queste equazioni quando necessario. L'approccio dal basso cerca di risolvere il più piccolo valore matematico dopo aver abbattuto l'equazione e poi si fa strada verso il più grande da lì. Entrambi gli approcci consentono di risparmiare tempo, ma la programmazione dinamica funziona solo quando il problema originale può essere suddiviso in equazioni più piccole che a un certo punto vengono riutilizzate per risolvere l'equazione.