Solution: Stone Game VII
Tags: algorithms, javascript, java, python
Published: 2021-06-11 09:08:33

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/stone-game-vii/discuss/1264516).*

---

#### [Leetcode Problem #1690 (*Medium*): Stone Game VII](https://leetcode.com/problems/stone-game-vii/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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**_.

---

#### ***Examples:***
>
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].<br>- Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].<br>- Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].<br>- Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].<br>- Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = [].<br>The score difference is 18 - 12 = 6.<br>
>
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`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

Like most of the Stone Game problems, this one boils down to a system of ever-repeating subproblems, as the there are many different ways to get to the same board condition as we move towards the end of the game. This naturally points to a **dynamic programming** (**DP**) solution.

In order to represent the different board positions, we'd normally build an **N * N** DP matrix where **N** is the length of the stones array (**S**). In this DP array, **dp[i][j]** would represent the best score difference with **i** representing the leftmost remaining stone's index and **j** representing the rightmost remaining stone's index.

We'll start at **i = N - 2** and iterate backwards and start each nested **for** loop at **j = i + 1**. This ensures that we're building the pyramid of DP results downward, always starting each row with **i** and **j** next to each other.

For each row, we'll keep track of the sum **total** of the stones in the range **[i,j]** by adding **S[j]** at each iteration of **j**. Then, we can represent the current player's ideal play by choosing the best value between picking the stone at **i** (**total - S[i]**) and picking the stone at **j** (**total - S[j]**). For each option, we have to also subtract the best value that the other player will get from the resulting board position (**dp[i+1][j]** or **dp[i][j-1]**).

Since we will only be building off the cells to the left and above the current cell, however, we can actually eliminate the DP matrix and instead just one array representing the current row, reusing it each time. This will drop the **space complexity** from **O(N^2)** to **O(N)**.

This approach works because, when evaluating a new cell, the cell to the left will already have been overwritten and will accurately represent the previous cell on the same row. The not-yet-overwritten current cell value still represents the cell that would have been in the row above in a full DP matrix.

At the end, the solution will be the value stored in the DP array representing the board position with all stones present. We should therefore **return dp[N-1]**.

 - _**Time Complexity: O(N^2)** where **N** is the length of **S**_
 - _**Space Complexity: O(N)** for **dp**_

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```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 Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```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 Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```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++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int stoneGameVII(vector<int>& S) {
        int N = S.size();
        vector<int> 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];
    }
};
```