Ho provato a risolvere il problema dei turni ma non riesco a capire in che modo strutturare la programmazione dinamica. Qualcuno che mi può dare qualche suggerimento?
Grazie in anticipo.
1 Mi Piace
Non è programmazione dinamica c:
Il problema ti assicura che esiste almeno una soluzione disponibile, quindi hai sicuramente almeno un turno che parte da t = 0.
Ora, fingiamo ci siano tre turni diversi del tipo (0, x). Qual è il turno che dobbiamo prendere?
Beh, sicuramente quello che ha una fine maggiore.
Detto questo, andiamo avanti prendendo turni che hanno un inizio minore o uguale della fine del turno precedente e la fine deve essere il massimo che posso prendere.
Il problema è greedy, perché la miglior scelta locale mi assicura la miglior scelta globale.
1 Mi Piace
Se proprio vogliamo mettere i puntini sulle i puoi anche risolverlo in DP 
Il problema che vuoi risolvere è: qual è il numero minino di intervalli da prendere per coprire \lbrack 0, K-1 \rbrack sapendo che ho N intervalli?
Una possibile scelta di sotto-problemi potrebbe essere ad esempio: qual è il numero minimo di intervalli da prendere per coprire \lbrack x, K-1 \rbrack sapendo che ho m intervalli?
A questo punto, ordinando gli intervalli in crescente rispetto al primo estremo, ti è facile trovare un approccio ricorsivo dove ad ogni intervallo puoi scegliere se prenderlo o non prenderlo: in alcuni casi noterai, come diceva @db2000 qui sopra, che a volte sai già cosa conviene prendere 
2 Mi Piace
In effetti in dp non l’avevo pensata ahahah
La domanda che mi sorge è: quindi è vera la storia che, in fondo, tutti i problemi potrebbero esser risolti in dp o ricorsivamente? 
Ogni problema lo puoi risolvere con la pura ricorsione (basti pensare ai linguaggi funzionali).
Per la DP invece è diverso, non puoi sempre applicarla
Ma generalmente ogni problema di massimo/minimo/combinatoria ha a che fare con DP/Greedy.
E ogni problema Greedy può essere risolto via DP (in genere peggiorando la complessità), ma non il contrario 
1 Mi Piace
grazie a tutti.
ma come riesco a capire se un problema posso risolverlo in maniera greedy o sono costretto ad usare la DP?
Capire che un problema è risolvibile con la DP generalmente è molto più semplice perché hai una ricorsione, ad esempio f(n, m), dove allo stato (n, m) ci puoi arrivare da “più parti” (quindi calcoli più volte la stessa sotto-soluzione).
Per i Greedy è più spinosa perché hai sempre il dubbio che non sia veramente Greedy il problema (sempre se non lo dimostri). Ma di solito o lo capisci subito oppure ci arrivi notando qualcosa quando scrivi la DP.
Se sei in una competizione con il correttore non ti costa niente buttare una soluzione Greedy, se invece sei alle territoriali (sempre se non hanno messo il correttore anche lì) forse è meglio pensarci due volte e se non si è sicuri inviare una DP
1 Mi Piace
con la pura ricorsione puoi sempre fare algoritmi complete-search (eufemismo per brute-force) che trovano sempre la migliore soluzione, ma con complesiità esponenziale.
1 Mi Piace