花花酱 LeetCode 1690. Stone Game VII

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones arranged in a row. On each player’s turn, they can remove either the leftmost stone or the rightmost stone from the row and receive points equal to the sum of the remaining stones’ values in the row. The winner is the one with the higher score when there are no stones left to remove.

Bob found that he will always lose this game (poor Bob, he always loses), so he decided to minimize the score’s difference. Alice’s goal is to maximize the difference in the score.

Given an array of integers stones where stones[i] represents the value of the i^th stone from the left, return the difference in Alice and Bob’s score if they both play optimally.

Example 1:

Input: stones = [5,3,1,4,2]
Output: 6
Explanation: 
- Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
- Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
- Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
- Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
- Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = [].
The score difference is 18 - 12 = 6.

Example 2:

Input: stones = [7,90,5,1,100,10,10,2]
Output: 122

Constraints:

n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000

Solution: MinMax + DP

For a sub game of stones[l~r] game(l, r), we have two choices:
Remove the left one: sum(stones[l + 1 ~ r]) – game(l + 1, r)
Remove the right one: sum(stones[l ~ r – 1]) – game(l, r – 1)
And take the best choice.

Time complexity: O(n^2)
Space complexity: O(n^2)

C++/Top Down

// Author: Huahua

class Solution {

public:

int stoneGameVII(vector<int>& A) {

const int n = A.size();

vector<vector<int>> cache(n, vector<int>(n, INT_MAX));

function<int(int, int, int)> dp = [&](int l, int r, int s) {

if (l >= r) return 0;

if (cache[l][r] == INT_MAX)

cache[l][r] = max(s - A[r] - dp(l, r - 1, s - A[r]),

s - A[l] - dp(l + 1, r, s - A[l]));

return cache[l][r];

};

return dp(0, n - 1, accumulate(begin(A), end(A), 0));

}

};

C++/Bottom-Up

// Author: Huahua

class Solution {

public:

int stoneGameVII(vector<int>& A) {

const int n = A.size();

vector<int> s(n + 1);

for (int i = 0; i < n; ++i) s[i + 1] = s[i] + A[i];

vector<vector<int>> dp(n, vector<int>(n, 0));

for (int c = 2; c <= n; ++c)

for (int l = 0, r = l + c - 1; r < n; ++l, ++r)

dp[l][r] = max(s[r + 1] - s[l + 1] - dp[l + 1][r],

s[r] - s[l] - dp[l][r - 1]);

return dp[0][n - 1];

}

};

Python3

# Author: Huahua

class Solution:

def stoneGameVII(self, stones: List[int]) -> int:

n = len(stones)

s = [0] * (n + 1)

for i in range(n): s[i + 1] = s[i] + stones[i]

dp = [[0] * n for _ in range(n)]

for c in range(2, n + 1):

for l in range(0, n - c + 1):

r = l + c - 1

dp[l][r] = max(s[r + 1] - s[l + 1] - dp[l + 1][r],

s[r] - s[l] - dp[l][r - 1])

return dp[0][n - 1]

花花酱 LeetCode 1690. Stone Game VII

Solution: MinMax + DP

C++/Top Down

C++/Bottom-Up

Python3

Related Problems

Be First to Comment

Leave a Reply Cancel reply