Problem Explanation

Alice and Bob are playing a game where they take turns to remove either the leftmost or the rightmost stone from a row of stones, and they receive points equal to the sum of the remaining stones' values in the row. Alice goes first and wants to maximize the difference in their scores, while Bob wants to minimize this difference. Each stone has a value denoted by the array stones. The aim of this problem is to find out the difference in score between Alice and Bob when they both play optimally.

Let's take an example. If stones = [5,3,1,4,2], the game plays as follows:

• Alice removes the rightmost stone and earns 13 points. The remaining stones are [5,3,1,4], and the scores are Alice=13, Bob=0.
• Bob removes the leftmost stone and earns 8 points. The remaining stones are [3,1,4], and the scores are Alice=13, Bob=8.
• Alice removes the leftmost stone and earns 5 points. The remaining stones are [1,4], and the scores are Alice=18, Bob=8.
• Bob removes the leftmost stone and earns 4 points. The remaining stone is [4], and the scores are Alice=18, Bob=12.
• Alice removes the remaining stone and earns 0 points. There are no stones left, and the scores are Alice=18, Bob=12.

Therefore, the difference in score is 18 - 12 = 6.

Solution Approach

The solution approach involves using a dynamic programming strategy. Let dp[i][j] denote the maximum score difference that can be obtained when the remaining stones are between i and j. The goal is to update dp[i][j] by choosing the leftmost or rightmost stone and updating accordingly based on the sum of the remaining stones.

A helper function stoneGameVII is used to update dp[i][j]. If i equals j, all stones have been removed so return 0. If dp[i][j] has been previously computed, return dp[i][j]. Otherwise, removing the leftmost stone results in getting the sum of stones between i + 1 and j, and removing the rightmost stone results in getting the sum of stones between i and j - 1. The maximum value of these two options is chosen.

This logic is implemented in the following solutions in Python, Java, JavaScript, C++, and C#.

Python Solution

1
2python
3class Solution:
4    def stoneGameVII(self, stones):
5        n = len(stones)
6        dp = [[0]*n for _ in range(n)]
7        prefix = [0]*(n+1)
8        for i in range(n):
9            prefix[i+1] = prefix[i] + stones[i]
10        for l in range(n-2, -1, -1):
11            for r in range(l+1, n):
12                dp[l][r] = max(prefix[r+1]-prefix[l+1]-dp[l+1][r], prefix[r]-prefix[l]-dp[l][r-1])
13        return dp[0][n-1]

Java Solution

1
2java
3class Solution {
4    public int stoneGameVII(int[] stones) {
5        int N = stones.length;
6        int[] dp = new int[N];
7        int sum = 0;
8        for (int i = N - 1; i >= 0; --i) {
9            sum += stones[i];
10            for (int j = i + 1; j < N; ++j) {
11                dp[j] = Math.max(sum - stones[i] - dp[j], sum - stones[j] - dp[j - 1]);
12            }
13        }
14        return dp[N - 1];
15    }
16}

JavaScript Solution

1
2javascript
3var stoneGameVII = function(stones) {
4    let cache = new Map();
5    let prefix = new Array(stones.length + 1).fill(0);
6    for(let i = 0; i < stones.length; i++) {
7        prefix[i + 1] = prefix[i] + stones[i];
8    }
9
10    function dp(l, r) {
11        if(l >= r) return 0;
12        let key = `${l}-${r}`;
13        if(cache.has(key)) return cache.get(key);
14        
15        let score = Math.max(prefix[r + 1] - prefix[l + 1] - dp(l + 1, r), prefix[r] - prefix[l] - dp(l, r - 1));
16        cache.set(key, score);
17        return score;
18    }
19    
20    return dp(0, stones.length - 1);
21};

C++ Solution

1
2cpp
3class Solution {
4 public:
5  vector<int> prefix;
6  vector<vector<int>> dp; 
7
8  int stoneGameVII(vector<int>& stones) {
9    int n = stones.size();
10    dp.resize(n, vector<int>(n));
11    prefix.resize(n + 1);
12    partial_sum(stones.begin(), stones.end(), prefix.begin() + 1);
13
14    return findDifference(stones, 0, n - 1);
15  }
16
17  int findDifference(const vector<int>& stones, int start, int end) {
18    if (start == end) return 0;
19    if (dp[start][end] > 0) return dp[start][end];
20
21    dp[start][end] = max(prefix[end + 1] - prefix[start + 1] - findDifference(stones, start + 1, end),
22                          prefix[end] - prefix[start] - findDifference(stones, start, end - 1));
23
24    return dp[start][end];
25  }
26};

C# Solution

1
2csharp
3public class Solution {
4    public int StoneGameVII(int[] stones) {
5        int n = stones.Length;
6        int[,] dp = new int[n,n];
7        int[] prefix = new int[n + 1];
8        for(int i = 0; i < n; i++) {
9            prefix[i + 1] = prefix[i] + stones[i];
10        }
11        for(int l = n - 2; l >= 0; l--) {
12            for(int r = l + 1; r < n; r++) {
13                dp[l,r] = Math.Max(prefix[r + 1] - prefix[l + 1] - dp[l + 1,r], prefix[r] - prefix[l] - dp[l,r - 1]);
14            }
15        }
16        return dp[0,n - 1];
17    }
18}

These solutions iterate through the stones array in reverse, updating dp for each pair of indices (l, r) where l < r. The maximum score difference when the remaining stones are between l and r is the maximum of two options:

1. The sum of stones between l + 1 and r, minus the score difference when the remaining stones are between l + 1 and r (after removing the leftmost stone)
2. The sum of stones between l and r - 1, minus the score difference when the remaining stones are between l and r - 1 (after removing the rightmost stone)

In the Python and C# solutions, to get the sum of stones between i and j, we create a prefix array where prefix[i] is the sum of stones from index 0 to i - 1. The sum of stones between i and j is then prefix[j + 1] - prefix[i].

In the Java solution, dp is updated in-place to reduce the space complexity. During each iteration, sum is the sum of stones from index i to the end of the array. When calculating dp[j], we subtract stones[i] or stones[j] from sum to get the sum of stones between i + 1 and j, or between i and j - 1, respectively.

In the JavaScript solution, we store the score difference in a cache data structure for faster access. The cache is implemented as a JavaScript Map, and the key for each entry is a string in the form of ${l}-${r}, where l and r are the start and end indices, respectively.

The C++ solution creates a prefix array similar to the Python and C# solutions, and uses a helper function findDifference to update dp.

All solutions have a time complexity of O(n^2), where n is the number of stones. This is because we iterate over each pair of indices. The space complexity is also O(n^2) because of the dp array. The exception is the Java solution, which has a space complexity of O(n) by reusing the dp array.

In conclusion, these solutions accurately determine the maximum score difference in the Stone Game VII problem by applying dynamic programming strategies. Despite differences in their implementation, all solutions fundamentally use the same logic: calculate the possible scores for each pair of indices and choose the maximum value.