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

Question

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

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

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

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

Answer 1

Посмотрите на этот сайт: http://people.csail.mit.edu/bdean/6.046/dp/, Особенно проблема номер 10:

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

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