Решение: Каменная игра VII

Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашел его полезным, Пожалуйста, как этот пост и/или УПОТАТЬ Мое решение пост на форумах LeetCode Отказ

Проблема лецкода # 1690 (средний): Каменная игра VII.

Описание:

( Перейти к : Идея решения Код : JavaScript | Python |. Java |. C ++

Алиса и Боб по очереди играют в игру, с Алиса начала первая Отказ

Есть n камни расположены подряд. На ходу каждого игрока они могут Удалить либо самый крайний камень или самый правый камень от ряда и получают точки, равные сумма Из остальных значений камней в ряд. Победитель – это тот, кто с более высоким баллом, когда не осталось камней для удаления.

Боб обнаружил, что он всегда потеряет эту игру (плохой боб, он всегда теряет), поэтому он решил минимизировать разницу . Цель Алисы – максимизировать разницу в счет.

Учитывая массив целых чисел камни где камни [я] представляет значение i камень слева , вернуть Разница в счет Алисы и Боба, если они оба играют Оптимально Отказ

Примеры:

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

• N.Length
• 2
• 1 [я]

Идея:

( Перейти к : Описание проблемы Код : JavaScript | Python |. Java |. C ++

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

Для того, чтобы представлять различные позиции на доске, мы обычно построим N * n DP Matrix, где N Это длина массива камней ( S ). В этом массиве DP DP [I] [J] будет представлять лучшие результаты разницы с Я представляя левый оставшийся индекс камня и J представляя самый правый оставшийся указатель камня.

Мы начнем в Я – 2 и итереть назад и начать каждый вложенный для петля на J + 1 Отказ Это гарантирует, что мы наращиваем пирамиду результатов DP вниз, всегда начинаем каждую строку с i и J рядом друг с другом.

Для каждой строки мы отслеживаем сумму Всего из камней в диапазоне [я, j] Добавляя S [j] На каждой итерации j . Затем мы можем представлять идеальную игру «текущий проигрыватель», выбрав наилучшее значение между выбором камня на i ( Total – S [I] ) и выбирая камень на j ( Всего – s [j] ). Для каждого варианта мы должны также вычесть наилучшее значение, которое другой игрок получит из полученной позиции платы ( DP [I + 1] [J] или DP [I] [J-1] ).

Поскольку мы будем строить только с ячейки влево и над текущей ячейкой, однако, мы можем фактически устранить матрицу DP и вместо этого только один массив, представляющий текущую строку, использующую ее каждый раз. Это бросит Космическая сложность от O (n ^ 2) к O (n) Отказ

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

В конце решение будет значение, хранящимся в массиве DP, представляющей положение платы со всеми присутствующими камнями. Поэтому мы должны Вернуть DP [N-1] Отказ

• Сложность времени: O (N ^ 2) где N это длина S
• Космическая сложность: O (n) за дп

Код JavaScript:

( Перейти к : Описание проблемы Идея решения

var stoneGameVII = function(S) {
    let N = S.length, dp = new Uint32Array(N)
    for (let i = N - 2; ~i; i--) {
        let total = S[i]
        for (let j = i + 1; j < N; j++) {
            total += S[j]
            dp[j] = Math.max(total - S[i] - dp[j], total - S[j] - dp[j-1])
        }
    }
    return dp[N-1]
};

Код Python:

( Перейти к : Описание проблемы Идея решения

class Solution:
    def stoneGameVII(self, S: List[int]) -> int:
        N, dp = len(S), [0] * len(S)
        for i in range(N - 2, -1, -1):
            total = S[i]
            for j in range(i + 1, N):
                total += S[j]
                dp[j] = max(total - S[i] - dp[j], total - S[j] - dp[j-1])
        return dp[-1]

Java код:

( Перейти к : Описание проблемы Идея решения

class Solution {
    public int stoneGameVII(int[] S) {
        int N = S.length;
        int[] dp = new int[N];
        for (int i = N - 2; i >= 0; i--) {
            int total = S[i];
            for (int j = i + 1; j < N; j++) {
                total += S[j];
                dp[j] = Math.max(total - S[i] - dp[j], total - S[j] - dp[j-1]);
            }
        }
        return dp[N-1];
    }
}

C ++ код:

( Перейти к : Описание проблемы Идея решения

class Solution {
public:
    int stoneGameVII(vector& S) {
        int N = S.size();
        vector dp(N);
        for (int i = N - 2; ~i; i--) {
            int total = S[i];
            for (int j = i + 1; j < N; j++) {
                total += S[j];
                dp[j] = max(total - S[i] - dp[j], total - S[j] - dp[j-1]);
            }
        }
        return dp[N-1];
    }
};

Оригинал: “https://dev.to/seanpgallivan/solution-stone-game-vii-3lei”