Dot Game и динамическое программирование

Question

Я пытаюсь решить вариант точечной игры с динамическим программированием.

В обычную игру с точками играет линия из точек. Каждый игрок берет одну или две точки на соответствующем конце линии, и человек, у которого нет точек, выигрывает.

В этой версии игры каждая точка имеет различное значение. Каждый игрок делает поочередные ходы и берет любую точку на любом конце линии. Я хочу найти способ использовать динамическое программирование, чтобы найти максимальную сумму, которую гарантированно выиграет первый игрок.

У меня проблемы с тем, что я обдумываю это и пытаюсь написать повторение решения. Любая помощь приветствуется, спасибо!

Answer 1

Взгляните на этот сайт: http://people.csail.mit.edu/bdean/6.046/dp/, особенно проблема № 10:

Оптимальная стратегия для игры. Рассмотрим ряд из n монет со значениями v (1) ... v (n), где n четное. Мы играем в игру против оппонента, чередуя ходы. В каждом ходу игрок выбирает первую или последнюю монету из ряда, навсегда удаляет ее из ряда и получает ценность монеты. Определите максимально возможную сумму денег, которую мы можем определенно выиграть, если будем двигаться первым.

Это именно то, что вы хотите, если я правильно читаю ваш пост. Решение довольно простое, и, на мой взгляд, оно очень хорошо объяснено.