qualcuno conosce un buon manuale su programmazion dinamica e teoria dei giochi?
se si:qualcuno mi potrebbe dare il link ?
Per la programmazione dinamica (DP) questa è una buona introduzione: http://ioi.di.unimi.it/dinamica.pdf, devo dire però che quando la lessi io non la trovai molto intuitiva, perché la spiega fin da subito con un approccio “bottom-up”… Personalmente mi sono trovato meglio a capire la DP “top-down”, che praticamente è una generalizzazione del divide et impera con la differenza che la fase “divide” non fa una divisione netta, ovvero i vari pezzi potrebbero avere delle parti “in comune” (o “sovrapposte”) quindi va usata la memoizzazione per evitare di ricalcolare tante volte gli stessi sottoproblemi. La guida alle selezioni territoriali (che puoi scaricare a questo indirizzo) forse è più intuitiva. Il capitolo 7 è dedicato alla DP (è importante però leggere prima anche il capitolo 6).
Per la teoria dei giochi si dovrebbe specificare meglio cosa vuoi di preciso dato che è una branca abbastanza ampia. Ad uno stage di qualche anno fa si tenne una lezione sulla strategia Minimax, che si usa per i giochi a due giocatori che “muovono” a turno (giocatore 1, giocatore 2, giocatore 1, …). Una dispensa la trovi qui: http://ioi.di.unimi.it/minimax.pdf. Il task che ci fecero risolvere usando questa strategia è Ioiwari. A questo indirizzo trovi un videotutorial. Allo stage ci fecero anche implementare il pruning alpha-beta in modo da velocizzare l’esecuzione.
ti ringrazio molto
Ciao a tutti,
oltre ai riferimenti di wil93 ci sono degli altri riferimenti e/o esercizi svolti per approcciarsi alla programmazione dinamica?
Grazie in anticipo!
Su wiki.olinfo.it puoi trovare le lezioni degli stage di allenamento nazionali degli anni passati, che coprono quasi tutti gli argomenti base e anche più avanzati. Per esempio la prima lezione dell’anno scorso era sulla programmazione dinamica:
1 Mi Piace
Per esperienza, il modo più efficace per migliorare con dp è vedere tanti esercizi e in caso spoilerarsi le soluzioni capendole per bene. A volte conviene non spendere tantissimo tempo su un problema ma piuttosto vedere la soluzione e passare a un altro. Su training puoi ordinare i problemi per difficoltà e filtrarli per categoria. Su codeforces puoi fare lo stesso e hai sempre gli editorial dei problemi.
1 Mi Piace
Grazie mille!
Grazie per il consiglio! 
1 Mi Piace