Dot Game und Dynamische Programmierung

Question

Ich versuche, eine Variante des Punktspiel mit der dynamischen Programmierung zu lösen.

Das reguläre Punkt Spiel wird mit einer Reihe von Punkten gespielt. Jeder Spieler nimmt sich entweder ein oder zwei Punkte an ihrem jeweiligen Ende der Leitung und der Person, die ohne Punkte bleibt, gewinnt zu nehmen.

In dieser Version des Spiels hat jeder Punkt einen anderen Wert. Jeder Spieler nimmt abwechselnde Windungen und nimmt entweder Punkt an jedem Ende der Leitung. Ich mag mit einem Weg kommen dynamische Programmierung zu verwenden, um den maximalen Betrag, dass der erste Spieler zu finden ist garantiert, um zu gewinnen.

Ich habe Probleme Greifen meinen Kopf um diese und versuchen, eine Wiederholung für die Lösung zu schreiben. Jede Hilfe ist willkommen, danke!

Answer 1

Schauen Sie sich auf diese Seite: http://people.csail.mit edu / Bdean / 6,046 / dp / , insbesondere Problem Nummer 10:

Optimale Strategie für ein Spiel. Betrachten wir eine Reihe von n Münzen von Werten v (1) ... v (n), wobei n gerade ist. Wir spielen ein Spiel gegen einen Gegner durch abwechselnde Kurven. In jeder Runde ein Spieler wählt entweder die erste oder die letzte Münze aus der Reihe, entfernt sich aus der Reihe dauerhaft und empfängt den Wert der Münze. Bestimmen Sie die maximal mögliche Menge an Geld, das wir auf jeden Fall gewinnen können, wenn wir zuerst bewegen.

Es ist genau das, was Sie wollen, wenn ich Ihren Beitrag richtig zu lesen. Die Lösung ist recht einfach und es ist sehr gut erklärt es meiner Meinung nach.