Задача задается следующим образом:
Существует игра с последовательностью из n чисел (a1, a2, a3, .., an) и двумя игроками.Игроки берут числа из последовательности;на каждом ходу игрок может выбрать первый или последний номер в последовательности.Когда последовательность очищается, игрок с большим общим количеством выигрывает;если равен, игра ничья.
Цель состоит в том, чтобы написать алгоритм, который возвращает последовательность выборов, чтобы гарантировать лучший результат (выигрыш или ничья) для первого игрока, при условии, что второй игрок будетиграть оптимально.
Я придумал рекурсивную формулу, которая может быть преобразована в решение динамического программирования:
- Для последовательности Ai, Ai + 1, ..., Aj:
- Если в последовательности есть одно число - возьмите его.
- В противном случае, проверьте оба возможных варианта, выбрав тот, который дает более низкий результат для второго игрока до конца игры.
Таким образом, оптимальная сумма для первогоигрок - это сумма всех чисел в последовательности минус минимальная сумма, которую получит второй игрок.Формула выглядит следующим образом:
p (i, j) = Ai (если i = j)
p (i, j) = Ai + Ai + 1 + ... + Aj - min {p (i + 1, j), p (i, j-1)} (если j> i)
Мы используем ту же формулу для вычисления суммы второго игрока и суммы первого игрока, потому что второй игрок также хочет получить максимально возможное значение.
Корректность можетбыть легко доказанным индуктивно.Кроме того, мы можем получить решение динамического программирования из него: сначала вычислите значения p (i, j) для каждой пары (i, j) и сохраните его в таблице nxn.Решение принимает O (n ^ 3).Также есть способ выполнить предварительную обработку суммы A1 + Ai + 1 + Ai + 2 + ... + Aj: мы можем вычислить суммы A1 + ... + Aj для каждого j и каждый раз применяя формулу p(i, j) можно использовать sum (1, j) - sum (1, i), чтобы решение приняло O (n ^ 2).
Есть ли более быстрый алгоритм?В моем решении я получаю последовательность вариантов, которая дает максимальную сумму для первого игрока, но она слишком «сильная»: меня попросили получить последовательность вариантов, которые приносят ему победу, независимо от максимизации окончательной суммы.Так что, несомненно, я выполнил несколько ненужных шагов.
Лучшим решением кажется жадный алгоритм, потому что я видел ту же проблему, но с четным числом чисел в последовательности (здесь https://cs.stackexchange.com/questions/82351/optimizing-greedy-solution-for-choice-game/82450).
Кто-нибудь может подсказать, как должно выглядеть жадное решение? Заранее спасибо!