Programmation du jeu et dynamique Dot

Question

Je suis en train de résoudre une variante du jeu de points avec la programmation dynamique.

Le jeu de points régulier se joue avec une ligne de points. Chaque joueur prend un ou deux points à leur extrémité respective de la ligne et la personne qui reste sans points à prendre victoires.

Dans cette version du jeu, chaque point a une valeur différente. Chaque joueur prend tour de rôle et prend soit point à l'une des extrémités de la ligne. Je veux trouver un moyen d'utiliser la programmation dynamique pour trouver le montant maximum que le premier joueur est garanti pour gagner.

Je vais avoir ma tête mal à tenir autour de cela et essayer d'écrire une récurrence pour la solution. Toute aide est appréciée, merci!

Answer 1

Jetez un oeil à ce site: http://people.csail.mit .edu / bdean / 6,046 / dp / , en particulier le problème numéro 10:

  

Stratégie optimale pour un jeu. Considérons une rangée de n pièces de monnaie de valeurs v (1) ... c (n), où n est pair. Nous jouons un match contre un adversaire tour à tour en alternance. A chaque tour, un joueur choisit soit la première ou la dernière pièce de la ligne, il retire de la ligne en permanence, et reçoit la valeur de la pièce. Déterminer le montant maximum d'argent que nous pouvons certainement gagner si on passe en premier.

Il est exactement ce que vous voulez, si je lis votre droite après. La solution est assez simple et il est très bien il expliqué à mon avis.