Dot Juego y Programación Dinámica

Question

Estoy tratando de resolver una variante del juego de puntos con la programación dinámica.

El Juego del punto normal se juega con una línea de puntos. Cada jugador toma uno o dos puntos en sus respectivas final de la línea y la persona que se queda sin puntos a tener victorias.

En esta versión del juego, cada punto tiene un valor diferente. Cada jugador toma turnos alternos y toma cualquiera de puntos en cada extremo de la línea. Quiero encontrar una manera de utilizar la programación dinámica para encontrar la cantidad máxima que el primer jugador está garantizado para ganar.

Tengo problemas para agarrar mi cabeza alrededor de esto y tratando de escribir una recurrencia de la solución. Cualquier ayuda se agradece, gracias!

Answer 1

Tome un vistazo a este sitio: http://people.csail.mit edu / Bdean / 6.046 / dp / , especialmente el problema número 10:

estrategia óptima para un juego. Considere una fila de n monedas de los valores v (1) ... v (n), donde n es par. Jugamos un partido contra un oponente por la alternancia de turnos. En cada turno, un jugador selecciona bien la primera o la última moneda de la fila, lo elimina de forma permanente desde la primera fila, y recibe el valor de la moneda. Determinar la cantidad máxima posible de dinero definitivamente podemos ganar si nos movemos en primer lugar.

Es exactamente lo que quiere si estoy leyendo su derecha posterior. La solución es bastante simple y es explicado muy bien allí en mi opinión.