universityin-classsubject-2101
2023-11-09
Algoritmi
Programmazione Dinamica
Proprietà e passaggi per problemi ricorsivi
1. Sotto-struttura ottima
Il problema è ricorsivo. Per risolvere il problema di ottimizzazione è necessario aver risolto i problemi di ottimizzazione dei sotto-problemi.
2. Definizione ricorsiva ottima
Definire ricorsivamente una funzione ricorsiva per il calcolo del costo di una soluzione ottima
3. Calcolo del costo di una soluzione ottima
Si definisce l’algoritmo vero e proprio in pseudo-codice basandosi sulla definizione ricorsiva dello step 2, individuando se utilizzare:
- ricorsione pura
- ricorsione con memorizzazione
- dynamic programming
4. Costruzione di una soluzione ottima
Problema della parentesizzazione delle matrici.