Dot Game e programmazione dinamica

Question

Sto cercando di risolvere una variante del gioco dot con la programmazione dinamica.

Il gioco di punti regolare si gioca con una linea di punti. Ogni giocatore prende uno o due punti al loro rispettivo capo della linea e la persona che è rimasto senza punti a prendere vittorie.

In questa versione del gioco, ogni punto ha un valore diverso. Ogni giocatore a turno si alternano e si sia punto alle due estremità della linea. Voglio venire con un modo per utilizzare la programmazione dinamica per trovare l'importo massimo che il primo giocatore è garantito per vincere.

Ho problemi afferrare la mia testa intorno a questo e cercando di scrivere una ricorrenza per la soluzione. Ogni aiuto è apprezzato, grazie!

Answer 1

Date un'occhiata a questo sito: http://people.csail.mit .edu / Bdean / 6,046 / dp / , in particolare il problema numero 10:

  

strategia ottimale per un gioco. Si consideri una fila di n monete di valori v (1) ... v (n), dove n è pari. Giochiamo una partita contro un avversario di volta in volta si alternano. In ogni turno, un giocatore seleziona sia la prima o l'ultima moneta dalla fila, rimuove dalla fila definitivo, e riceve il valore della moneta. Determinare l'importo massimo di denaro che possiamo sicuramente vincere se ci muoviamo prima.

E 'esattamente quello che vuoi, se sto leggendo il vostro diritto postale. La soluzione è abbastanza semplice ed è spiegato molto bene lì, a mio parere.