# 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:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\
**Post date:** [14 Maggio 2020, 8:06am UTC](https://forum.olinfo.it/t/corsa-contro-il-tempo/6193/1 "2020-05-14T08:06:41Z")

</div>

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?

---

<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)

---

<div class="post-metadata">

**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\
**Post date:** [14 Maggio 2020, 1:25pm UTC](https://forum.olinfo.it/t/corsa-contro-il-tempo/6193/3 "2020-05-14T13:25:19Z")

</div>

Grazie mille, per quanto riguarda la memoizzazione viene spiegata in qualcuno di questi video?

---

<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, 2:23pm UTC](https://forum.olinfo.it/t/corsa-contro-il-tempo/6193/4 "2020-05-14T14:23:46Z")

</div>

Non ricordo ma credo proprio di si.