Number Game Algorithm

0

Collegamento problema - link

L'obiettivo è trovare il punteggio massimo che puoi ottenere nel gioco. Tali problemi, basati sui giochi, in cui devi simulare, prevedere il risultato o ottenere il massimo punteggio possibile sembrano sempre sconcertarmi.

Posso farlo con la ricorsione considerando due casi: il primo numero selezionato o l'ultimo numero selezionato, ognuno dei quali si dirama nuovamente in due stati in modo simile, e così via ... che alla fine può produrre il massimo risultato possibile.

Ma è un approccio molto inefficiente dal momento che il tempo aumenta in modo esponenziale, a causa dei grossi casi di test.

Qual è l'approccio più pragmatico al problema e a questi problemi in generale?

    
posta 7Aces 06.11.2012 - 19:47
fonte

1 risposta

5

Il trucco è quindi:
Considera 2,5,3,3,2,1 .

La tua mossa: scegli Sinistra
Mossa dell'avversario: scegli Destra
Stato attuale: 5,3,3,2 .

vs.

La tua mossa: scegli Destra
Mossa avversario: scegli Sinistra
Stato attuale: 5,3,3,2 .

Usando la ricorsione, finirai per calcolare quanti più punti puoi ottenere per 5,3,3,2 due volte!

Quindi, la soluzione è usare la memoizzazione (programmazione dinamica)

La prima volta che chiami la tua funzione su 5,3,3,2 , memorizza il punteggio per quello (ad esempio, in un array bidimensionale in cui il primo indice è quanti numeri sono stati rimossi da sinistra e il secondo indice è quanti numeri sono stati rimossi da destra). La prossima volta che stai per chiamarlo, carica il punteggio dalla volta precedente.

Un buon vantaggio di questa strategia è che puoi usare l'algoritmo ricorsivo esistente con solo modifiche minime.

    
risposta data 06.11.2012 - 21:25
fonte

Leggi altre domande sui tag