Игра в камни 3

Источник: https://leetcode.com/problems/stone-game-iii/

Alice и Bob играют с камнями. Несколько камней выложены в рядок. У каждого камня есть своя стоимость stoneValueположительная или отрицательная.

Alice и Bob играют по очереди, при этом Alice начинает первая. каждый ход позволяет взять игроку 1, 2 или 3 подряд лежащих камня, с первого доступного в ряду.

Счёт каждого игрока - это сумма камней, которые он взял. Начальный счёт = 0.

Цель игры: завершить игру (когда не осталось доступных камней) со счётом, превосходящим счёт противника. Если у обоих игроков равный счёт, то получается ничья (tie). Игра продолжается, пока камней не останется.

Можно считать, что Alice и Bob играют оптимально.

Вернуть "Alice" , если победит Alice; "Bob", если победит Bob; или"Tie", если ничья.

Пример 1:

Дано: values = [1,2,3,7]
Результат: "Bob"
Пояснение: Alice проиграет в любом случае. Её лучший ход, дающий максимальный счёт - это первые три камня: 1+2+3=6. Ход Боба в любом случае будет содержать 7, что больше, чем наилучший счёт Алисы.

Пример 2:

Дано: values = [1,2,3,-9]
Результат: "Alice"
Пояснение: Alice должна зять на первом ходу первые три камня и оставить Боба с негативным счётом.
Если Alice возьмет только первый камень, то её счет равен 1, слледующим ходом Bob достигнет счета 5. Наконец, Alice должна будет взять -9 и проиграет со счетом 1-9=-8.
Если Alice возьмет только два первых камня, её счет будет равен 3, на следующем ходу счет Боба станет 3. Наконец, Alice должна будет взять -9 и проиграет со счетом 3-9=-6.
Если мы вспомним об условии, что игроки играют оптиально, то Alice выберет сценарий, в котором она выйграет.

Example 3:

Дано: values = [1,2,3,6]
Результат: "Tie"
Пояснение: Alice не может выйграть эту игру. Она может свести её к ничье, если на первом ходу возьмет первые три камня. В любом другом сценарии она проиграет.

Example 4:

Дано: values = [1,2,3,-1,-2,-3,7]
Результат: "Alice"

Example 5:

Дано: values = [-1,-2,-3]
Результат: "Tie"

Ограничения:

• 1 <= values.length <= 50000
• -1000 <= values[i] <= 1000

Идея решения

Будем рассматривать игру с конца. То есть исходный массив values сканируем с конца к началу. 

Если у нас в распоряжении только последний элемент, то этот элемент достается Алисе. И в зависимости от его веса (положительного или отрицательного) она выйгрывает или проигрывает.

Если мы рассмотрим подзадачу, состоящую из двух последних элементов, то Алиса может взять первый элемент, и тогда Бобу достанется второй. И результат победы будет зависеть отразницы между первым и вторым элементом: если она положительная, то Алиса выйграет. Или она может взять оба элемента, если захочем оставить Боба с нулем.

Рассмотрим подзадачу, состоящую из трёх последних элементов. Опять рассматриваем разные вариации, когда Алиса берет 1, 2 или 3 элемента. И выбираем тот сценарий, при котором выйгрыш Алисы максимизирован, а Боба минимизирован.

Затем мы рассматриваем подхвадачу, состоящую из 4-х последних элементов и можем уже свестии ее к подзадаче из 3-х элементов.

Имплементация

class Solution {
    public String stoneGameIII(int[] A) {
        int n = A.length, dp[] = new int[n+1];
// dp - это массив из промежуточных результатов Алисы, начиная с хвоста
        for (int i = n - 1; i >= 0; --i) {
            dp[i] = Integer.MIN_VALUE;
// берем три последовательных элемента (если они существуют)
// и последовательно рассматриваем сценарий, что будет, если Алиса возьмет камни
// 1, или 1+2, или 1+2+3
            for (int k = 0, take = 0; k < 3 && i + k < n; ++k) {
                take += A[i + k]; // счет Алисы в подзадаче из 3 ближайших элементов
                dp[i] = Math.max(dp[i], take - dp[i + k + 1]);
// выбираем сценрий, дающий максимальный счёт:
// take - текущий счёт Алисы в подзадаче из ближайших трех элементов
// dp[i + k + 1] - лучший счет, который может получить Боб на следующем ходу
// разница между ними показывает, насколько Алиса може победить
            }
        }
        if (dp[0] > 0) return "Alice";
        if (dp[0] < 0) return "Bob";
        return "Tie";
    }
}