Buongiorno stavo risolvendo Corsa Contro il Tempo e ho scritto una soluzione ricorsiva decisamente troppo lenta perciò penso che serva per forza un applicazione della programmazione dinamica solo che in questo momento non ho nessuna idea, perciò avete qualche consiglio o idea di base da cui partire?
Salve, negli esercizi di programmazione dinamica ci sono tipicamente due fasi:
- Individuazione degli stati.
- Individuazione delle transizioni.
Il primo serve a identificare univocamente un sotto-problema in modo tale da non ricalcolarlo se si presenta più volte.
Il secondo serve a comporre il risultato migliore per un determinato stato.
Con gli esercizi più banali e classici, se scritti ricorsivi, solitamente è facile aggiungere la memoizzazione per comporre la programmazione dinamica: gli stati sono i parametri della funzione ricorsiva mentre le transizioni i modi con cui la richiami.
A seconda dei parametri che hai scelto la memorizzazione potrebbe essere possibile oppure no. Per saperlo basta contare in quanti modi diversi si possono presentare i vari parametri e valutare se la memoria a disposizione sia abbastanza da poterli rappresentare.
La complessità di tempo sarà uguale a O(numeroStati \times costoTransizione), dove costoTransizione è la complessità di una singola chiamata della funzione ricorsiva.
In questo post c’è una discussione in cuoi puoi trovare del materiale a riguardo:
Ci sono dei video realizzati da @dariost che potrebbero aiutarti:
2 Mi Piace
Grazie mille, per quanto riguarda la memoizzazione viene spiegata in qualcuno di questi video?
Non ricordo ma credo proprio di si.
1 Mi Piace