# Stone Game VII
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/stone-game-vii)
Canonical: https://scaleengineer.com/dsa/problems/stone-game-vii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
**Data structures:** Array
**Companies:** [Dunzo](https://scaleengineer.com/companies/dunzo)
---
## Problem
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 `ith` 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`

# Approaches
## Brute-force Recursion
This approach directly translates the game's rules into a recursive function. The function calculates the score difference for a given sub-array of stones. At each step, it explores two possibilities: taking the leftmost stone or the rightmost stone. It then recursively calls itself for the remaining sub-array and the next player. Since it's a minimax problem, the current player chooses the move that maximizes their score difference relative to the opponent.
**Time:** O(2^n). For each subproblem of size `k`, we make two recursive calls for subproblems of size `k-1`. This creates a binary recursion tree of depth `n`. · **Space:** O(n) for the recursion stack depth and O(n) for the prefix sum array. Total O(n).
**Pros:** Simple to understand and implement as it directly follows the game's logic.
**Cons:** Extremely inefficient due to a large number of overlapping subproblems.; Will result in a "Time Limit Exceeded" (TLE) error for larger inputs.
### Explanation
We define a recursive function, say `solve(i, j)`, which returns the maximum score difference the current player can get from the subarray `stones[i...j]`. The total score of the stones from index `i` to `j` is needed for calculating the points. We can pre-calculate prefix sums for efficiency. Let `sum(i, j) = prefix[j+1] - prefix[i]`. In the `solve(i, j)` function:

*   **Base Case:** If `i > j` (no stones left), the score difference is 0.
*   **Recursive Step:** The current player has two choices:
    1.  **Take `stones[i]`:** The player gets `sum(i+1, j)` points. The game continues on the subarray `stones[i+1...j]`, and it's the opponent's turn. The opponent will play optimally to get a difference of `solve(i+1, j)`. So, the current player's net difference for this move is `sum(i+1, j) - solve(i+1, j)`.
    2.  **Take `stones[j]`:** The player gets `sum(i, j-1)` points. The game continues on `stones[i...j-1]`. The opponent will get a difference of `solve(i, j-1)`. The current player's net difference is `sum(i, j-1) - solve(i, j-1)`.

The current player wants to maximize their difference, so they choose the maximum of these two outcomes. This approach recomputes the same subproblems multiple times, leading to an exponential time complexity.

```java
class Solution {
    private int[] prefixSum;

    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        this.prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        }
        return solve(0, n - 1);
    }

    private int getSum(int i, int j) {
        if (i > j) {
            return 0;
        }
        return prefixSum[j + 1] - prefixSum[i];
    }

    private int solve(int i, int j) {
        if (i >= j) {
            return 0;
        }

        // Option 1: Take the leftmost stone stones[i]
        int scoreTakeLeft = getSum(i + 1, j);
        int diff1 = scoreTakeLeft - solve(i + 1, j);

        // Option 2: Take the rightmost stone stones[j]
        int scoreTakeRight = getSum(i, j - 1);
        int diff2 = scoreTakeRight - solve(i, j - 1);

        return Math.max(diff1, diff2);
    }
}
```
### Algorithm
- Create a prefix sum array to quickly calculate the sum of any subarray.
- Define a recursive function `solve(i, j)` that computes the maximum score difference for the subarray `stones[i...j]`.
- The base case for the recursion is when `i >= j`, meaning there is one or zero stone left. In this case, the game ends for this subproblem, and the difference is 0.
- In the recursive step, calculate the outcome of two possible moves:
    a. Removing `stones[i]`: The score gained is `sum(i+1, j)`. The opponent will then play on `stones[i+1...j]` and achieve a difference of `solve(i+1, j)`. The current player's total difference is `sum(i+1, j) - solve(i+1, j)`.
    b. Removing `stones[j]`: The score gained is `sum(i, j-1)`. The opponent will play on `stones[i...j-1]` and achieve `solve(i, j-1)`. The current player's total difference is `sum(i, j-1) - solve(i, j-1)`.
- The function `solve(i, j)` returns the maximum of the two outcomes, as the current player plays optimally to maximize the difference.
- The final answer is the result of `solve(0, n-1)`.

## Top-Down Dynamic Programming with Memoization
This approach improves upon the brute-force recursion by storing the results of subproblems in a memoization table (a 2D array). Before computing the result for a subproblem `(i, j)`, we first check if it has already been solved. If so, we return the stored value. Otherwise, we compute it, store it, and then return it. This avoids redundant computations.
**Time:** O(n^2). There are `n * (n+1) / 2` possible states `(i, j)`. Each state is computed only once. The computation for each state takes O(1) time (excluding the recursive calls, which are memoized). · **Space:** O(n^2) for the memoization table `memo`. The recursion stack depth can go up to O(n). So, the total space is dominated by the memoization table.
**Pros:** Much more efficient than brute-force recursion.; Guaranteed to pass within the time limits for the given constraints.; Often more intuitive to write than the bottom-up approach.
**Cons:** Uses O(n^2) space, which might be a concern for very large n.; Can lead to stack overflow for very deep recursion, although not an issue with n <= 1000.
### Explanation
The recursive structure is the same as the brute-force approach. We introduce a 2D array, `memo[n][n]`, to store the results of `solve(i, j)`. Initialize it with a value indicating that the state has not been computed (e.g., `null` or a sentinel value like `-1`). In the `solve(i, j)` function, we first check if `memo[i][j]` has been computed. If yes, we return `memo[i][j]`. If not, we perform the recursive calculations as before and store the result in `memo[i][j]` before returning it. This technique is also known as memoization and is a top-down dynamic programming approach.

```java
class Solution {
    private int[] prefixSum;
    private Integer[][] memo;

    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        this.prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        }
        this.memo = new Integer[n][n];
        return solve(0, n - 1);
    }

    private int getSum(int i, int j) {
        if (i > j) {
            return 0;
        }
        return prefixSum[j + 1] - prefixSum[i];
    }

    private int solve(int i, int j) {
        if (i >= j) {
            return 0;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }

        int scoreTakeLeft = getSum(i + 1, j);
        int diff1 = scoreTakeLeft - solve(i + 1, j);

        int scoreTakeRight = getSum(i, j - 1);
        int diff2 = scoreTakeRight - solve(i, j - 1);

        memo[i][j] = Math.max(diff1, diff2);
        return memo[i][j];
    }
}
```
### Algorithm
- Initialize a prefix sum array for `O(1)` sum calculations.
- Initialize a 2D memoization array `memo[n][n]` with a sentinel value to store results of subproblems.
- Define a recursive function `solve(i, j)`.
- Inside `solve(i, j)`, first check if `memo[i][j]` contains a valid result. If so, return it.
- The base case is `i >= j`, return 0.
- Otherwise, compute the two possible outcomes by taking the leftmost or rightmost stone, just like in the recursive approach.
    a. `diff1 = sum(i+1, j) - solve(i+1, j)`
    b. `diff2 = sum(i, j-1) - solve(i, j-1)`
- Store the maximum of `diff1` and `diff2` in `memo[i][j]`.
- Return the stored value.
- The initial call is `solve(0, n-1)`.

## Bottom-Up Dynamic Programming (Tabulation)
This is an iterative version of the dynamic programming solution. We use a 2D array `dp[n][n]` where `dp[i][j]` stores the maximum score difference the current player can achieve from the subarray `stones[i...j]`. We fill this table starting from smaller subproblems (smaller length subarrays) and build up to the solution for the entire array.
**Time:** O(n^2). We have two nested loops to fill the O(n^2) states in the DP table. Each state calculation is O(1). · **Space:** O(n^2) for the DP table `dp` and `O(n)` for the prefix sum array.
**Pros:** Avoids recursion, so no risk of stack overflow.; Efficient and guaranteed to pass.; Can be slightly faster than memoization in practice due to no function call overhead.
**Cons:** Still uses O(n^2) space.; The iteration logic can sometimes be less intuitive to derive than the recursive solution.
### Explanation
The state transition is the same: `dp[i][j] = max(sum(i+1, j) - dp[i+1][j], sum(i, j-1) - dp[i][j-1])`. We can see that `dp[i][j]` depends on solutions for smaller subarrays: `dp[i+1][j]` and `dp[i][j-1]`. This suggests we can iterate over the length of the subarray, `len`, from 2 to `n`. For each `len`, we iterate through all possible starting indices `i`. The ending index `j` will be `i + len - 1`. The base cases are subarrays of length 0 or 1, for which the difference is 0. So, `dp[i][i]` is 0. The final answer will be in `dp[0][n-1]`.

```java
class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        }

        int[][] dp = new int[n][n];

        // len is the length of the subarray
        for (int len = 2; len <= n; len++) {
            // i is the starting index of the subarray
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;

                // Sum of stones from i+1 to j
                int sumTakeLeft = prefixSum[j + 1] - prefixSum[i + 1];
                // Sum of stones from i to j-1
                int sumTakeRight = prefixSum[j] - prefixSum[i];

                // Calculate the difference for both choices
                int diff1 = sumTakeLeft - dp[i + 1][j];
                int diff2 = sumTakeRight - dp[i][j - 1];

                dp[i][j] = Math.max(diff1, diff2);
            }
        }

        return dp[0][n - 1];
    }
}
```
### Algorithm
- Create a prefix sum array for `O(1)` sum calculations.
- Create a 2D DP table `dp[n][n]`, initialized to 0. `dp[i][j]` will store the max difference for `stones[i...j]`.
- Iterate over the subarray length `len` from 2 to `n`.
- For each `len`, iterate through all possible start indices `i` from 0 to `n - len`.
- Calculate the end index `j = i + len - 1`.
- Calculate the sum of the remaining stones for both possible moves:
    a. If taking `stones[i]`, remaining sum is `sum(i+1, j)`.
    b. If taking `stones[j]`, remaining sum is `sum(i, j-1)`.
- Use the DP recurrence to fill `dp[i][j]`:
  `dp[i][j] = max(sum(i+1, j) - dp[i+1][j], sum(i, j-1) - dp[i][j-1])`.
- After the loops complete, `dp[0][n-1]` will hold the final answer.

## Space-Optimized Bottom-Up Dynamic Programming
This approach optimizes the space complexity of the bottom-up DP solution. By observing the state transitions, we can see that to compute the values for a subarray of a certain length, we only need the results for subarrays of the immediately smaller length. This means to compute the current row `i` of our DP table, we only need the next row `i+1`. This dependency allows us to reduce the space from O(n^2) to O(n).
**Time:** O(n^2). The nested loops run O(n^2) times, and each step is O(1). · **Space:** O(n). We use a 1D array `dp` of size `n` and a prefix sum array of size `n+1`.
**Pros:** Most efficient in terms of space complexity.; Maintains the optimal O(n^2) time complexity.
**Cons:** The logic for in-place updates and loop directions can be tricky to reason about compared to the O(n^2) space solution.
### Explanation
The recurrence is `dp[i][j] = max(sum(i+1, j) - dp[i+1][j], sum(i, j-1) - dp[i][j-1])`. Let's iterate by the starting index `i` from `n-2` down to `0`, and the ending index `j` from `i+1` up to `n-1`. When we compute `dp[i][j]`, we need `dp[i+1][j]` (from the 'next' row `i+1`) and `dp[i][j-1]` (from the 'current' row `i`, but a previous column). This structure allows for space optimization. We can use a 1D array, say `dp[n]`. Let `dp[j]` represent the value for the current row `i` and column `j`. When we are calculating the row for `i`, the `dp` array will hold the values from the previous iteration, which corresponds to row `i+1`. The recurrence becomes: `dp[j] = max(sum(i+1, j) - dp[j], sum(i, j-1) - dp[j-1])`, where we update the `dp` array in place.

```java
class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        }

        int[] dp = new int[n];

        // i is the starting index of the subarray
        for (int i = n - 2; i >= 0; i--) {
            // j is the ending index of the subarray
            for (int j = i + 1; j < n; j++) {
                // Sum of stones from i+1 to j
                int sumTakeLeft = prefixSum[j + 1] - prefixSum[i + 1];
                // Sum of stones from i to j-1
                int sumTakeRight = prefixSum[j] - prefixSum[i];

                // dp[j] currently holds dp[i+1][j] from the previous outer loop iteration
                // dp[j-1] holds dp[i][j-1] from the current inner loop iteration
                int diff1 = sumTakeLeft - dp[j];
                int diff2 = sumTakeRight - dp[j - 1];

                dp[j] = Math.max(diff1, diff2);
            }
        }

        return dp[n - 1];
    }
}
```
### Algorithm
- Create a prefix sum array for `O(1)` sum calculations.
- Create a 1D DP array `dp[n]`, initialized to 0.
- Iterate the start index `i` from `n-2` down to `0`.
- In the inner loop, iterate the end index `j` from `i+1` up to `n-1`.
- Inside the inner loop, calculate the two possible differences:
    a. `diff1 = (prefixSum[j+1] - prefixSum[i+1]) - dp[j]`. Here `dp[j]` holds the value from the previous outer loop, which corresponds to `dp[i+1][j]`.
    b. `diff2 = (prefixSum[j] - prefixSum[i]) - dp[j-1]`. Here `dp[j-1]` holds the value just computed in the current inner loop, which corresponds to `dp[i][j-1]`.
- Update `dp[j]` with `max(diff1, diff2)`.
- After the loops, `dp[n-1]` will contain the result for the entire array `stones[0...n-1]`.

# Solutions
### Java

```java
class Solution {
private
  int[] s;
private
  Integer[][] f;
public
  int stoneGameVII(int[] stones) {
    int n = stones.length;
    s = new int[n + 1];
    f = new Integer[n][n];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + stones[i];
    }
    return dfs(0, n - 1);
  }
private
  int dfs(int i, int j) {
    if (i > j) {
      return 0;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    int a = s[j + 1] - s[i + 1] - dfs(i + 1, j);
    int b = s[j] - s[i] - dfs(i, j - 1);
    return f[i][j] = Math.max(a, b);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int stoneGameVII(vector<int> &stones) {
    int n = stones.size();
    int f[n][n];
    memset(f, 0, sizeof f);
    int s[n + 1];
    s[0] = 0;
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + stones[i];
    }
    function<int(int, int)> dfs = [&](int i, int j) {
      if (i > j) {
        return 0;
      }
      if (f[i][j]) {
        return f[i][j];
      }
      int a = s[j + 1] - s[i + 1] - dfs(i + 1, j);
      int b = s[j] - s[i] - dfs(i, j - 1);
      return f[i][j] = max(a, b);
    };
    return dfs(0, n - 1);
  }
};

```

### Python

```python
class Solution:
    def stoneGameVII(self, stones: List[int]) -> int: @ cache def dfs(i, j): if i > j: return 0 a = s[j + 1] - s[i + 1] - dfs(i + 1, j) b = s[j] - s[i] - dfs(i, j - 1) return max(a, b) s = list(accumulate(stones, initial=0)) ans = dfs(0, len(stones) - 1) dfs . cache_clear() return ans

```