# Corsa contro il tempo

**URL:** <https://forum.olinfo.it/t/corsa-contro-il-tempo/6193>\
**Category:** Aiuto\
**Created:** [14 Maggio 2020, 8:06am UTC](https://forum.olinfo.it/t/corsa-contro-il-tempo/6193 "2020-05-14T08:06:40Z")\
**Posts on this page:** 1\
**Showing post:** 2

<div class="post-metadata">

**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\
**Post date:** [14 Maggio 2020, 8:35am UTC](https://forum.olinfo.it/t/corsa-contro-il-tempo/6193/2 "2020-05-14T08:35:34Z")

</div>

Salve, negli esercizi di programmazione dinamica ci sono tipicamente due fasi:

1. Individuazione degli stati.
2. 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:

> [@Manuale su programmazione dinamica e teoria dei giochi](https://forum.olinfo.it/t/manuale-su-programmazione-dinamica-e-teoria-dei-giochi/3890):
>
> qualcuno conosce un buon manuale su programmazion dinamica e teoria dei giochi? se si:qualcuno mi potrebbe dare il link ?

Ci sono dei video realizzati da @dariost che potrebbero aiutarti:

[![](https://img.youtube.com/vi/dT5wMqCzp9I/maxresdefault.jpg "[CP2020] 04 | Programmazione dinamica 1 | Programmazione Competitiva 2020") ](https://www.youtube.com/watch?v=dT5wMqCzp9I)

[![](https://img.youtube.com/vi/Ubb-SwvMAq4/maxresdefault.jpg "[CP2020] 05 | Programmazione dinamica 2 | Programmazione Competitiva 2020") ](https://www.youtube.com/watch?v=Ubb-SwvMAq4)

---

_[View the full topic](https://forum.olinfo.it/t/corsa-contro-il-tempo/6193)._