universitystudyingsubject-2101
2023-11-07
Algoritmi
Programmazione Dinamica
Utile per risolvere problemi di ottimizzazione.
Si usa la ricorsione pura quando i sottoproblemi vengono calcolati una volta sola.
Se i sottoproblemi vengono calcolati più di una volta, si può effettuare un’ottimizzazione.
- mediante memorizzazione: è utile se esistono sottoproblemi non esplorati per calcolare la soluzione
- mediante programmazione dinamica: se tutti i sottoproblemi sono necessari per risolvere il problema.
La programmazione dinamica trasforma l’approccio da Top-Down in Bottom-Up.