Найдите победителя игры, в которой за каждый ход вынимают не более 3 камней из кучи.

Дан массив arr[] размера N , обозначающий значения, присвоенные N камням, два игрока, Player1 и Player2 , играют в игру с чередованием ходов. В каждый ход игрок может взять 1, 2 или 3 камня из первых оставшихся камней, при этом сумма значений всех удаленных камней прибавляется к счету игрока. Учитывая, что оба игрока играют оптимально, задача состоит в том, чтобы вывести победителя игры. Если оба игрока заканчивают игру с одинаковым счетом, выведите «Tie» .

Примеры:

Input: arr[] = {1, 2, 3, 7}
Output: Player2
Explanation: Player1 will always lose in an optimal scenario.

Input: arr[] = {1, 2, 3, -9}
Output: Player1
Explanation: Player1 must choose all the three piles at the first move to win and leave Player2 with negative score.
If Player1 chooses only one stone his score will be 1 and the next move Player2 score becomes 5. 
The next move Player1 will take the stone with value = -9 and lose.
If Player1 chooses two piles his score will be 3 and the next move Player2 score becomes 3. 
The next move Player1 will take the stone with value = -9 and also lose.

Наивный подход: простой подход состоит в том, чтобы выбрать такое количество камней, которое максимизирует общую сумму значений камней. Поскольку оба игрока играют оптимально и Игрок1 начинает игру, Игрок1 выбирает либо 1, либо 2, либо 3 камня, а оставшиеся камни передаются следующему игроку. Следовательно, счет Игрока2 должен быть вычтен из счета Игрока1. Идея состоит в том, чтобы использовать рекурсию для решения проблемы. Пусть максимальное количество очков Player1 равно res , полученному после рекурсивных вызовов.

• Если результат res > 0 , Player1 выигрывает.
• Если результат, res < 0 , Player2 выигрывает
• Если результат res == 0 , то ничья.

Так выглядит рекурсивное дерево, в котором некоторые подзадачи повторяются много раз.

Следуйте инструкциям, чтобы решить проблему:

• Объявите рекурсивную функцию, скажем, maxScore(i) для вычисления максимального количества очков Player1, если игра начинается с индекса i .
  • Если значение i ≥ n , вернуть 0 .
  • Инициализируйте переменную, скажем, score как INT_MIN, чтобы сохранить максимальное количество очков Player1.
    • Выбирает 1 камень: оценка = макс (оценка, обр [i] - максScore (i + 1))
    • Выбирает 2 камня, т.е. (i + 1 < N) : оценка = макс (оценка, обр [i] + обр [i + 1] - maxScore (i + 2))
    • Выбирает 3 камня, т.е. (i + 2 < N) : оценка = max(счет, arr[i] + arr[i + 1] + arr[i + 2] – maxScore(i + 3))
  • Возвращает значение score .
• Сохраните значение maxScore(0) в переменной res .
• Если значение res>0 , выведите «Player1» , если res<0 , выведите «Player2» , иначе выведите «Tie» .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(3 ^N )
Вспомогательное пространство: O(N)

Эффективный подход. Чтобы оптимизировать описанный выше подход, идея заключается в использовании динамического программирования. Данная задача обладает свойством оптимальной подструктуры и перекрывающимися подзадачами. Используйте мемоизацию, создав одномерную таблицу dp размера N для хранения результатов рекурсивных вызовов.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)