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:
