# Stone Game II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/stone-game-ii)
Canonical: https://scaleengineer.com/dsa/problems/stone-game-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
**Data structures:** Array
---
## Problem
Alice and Bob continue their games with piles of stones. There are a number of piles **arranged in a row**, and each pile has a positive integer number of stones `piles[i]`. The objective of the game is to end with the most stones.

Alice and Bob take turns, with Alice starting first.

On each player's turn, that player can take **all the stones** in the **first** `X` remaining piles, where `1 <= X <= 2M`. Then, we set `M = max(M, X)`. Initially, M = 1.

The game continues until all the stones have been taken.

Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.

**Example 1:**

**Input:** piles = \[2,7,9,4,4\]

**Output:** 10

**Explanation:**

* If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get `2 + 4 + 4 = 10` stones in total.
* If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get `2 + 7 = 9` stones in total.

So we return 10 since it's larger.

**Example 2:**

**Input:** piles = \[1,2,3,4,5,100\]

**Output:** 104

**Constraints:**

* `1 <= piles.length <= 100`
* `1 <= piles[i] <= 104`

# Approaches
## Brute-Force Recursion
This approach directly translates the game's logic into a recursive function. The function explores every possible move Alice can make, and for each move, it recursively explores every possible move Bob can make, and so on. This creates a large tree of game states. Since the same game states (defined by the starting pile index `i` and the value of `M`) can be reached through different sequences of moves, this method recomputes the optimal strategy for these states multiple times, leading to exponential time complexity.
**Time:** Exponential, roughly O(2^n). The recursion tree branches for each possible move, and subproblems are recomputed. · **Space:** O(n), for the recursion stack depth, where n is the number of piles.
**Pros:** Simple to conceptualize and implement.; Directly models the turn-based nature of the game.
**Cons:** Extremely inefficient due to a large number of overlapping subproblems.; Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
### Explanation
The core idea is to model the game as a recursive process. The state of the game can be uniquely identified by two parameters: `i`, the index of the first pile in the remaining sequence, and `M`, the value that constrains the number of piles a player can take.

We define a function `solve(i, M)` which calculates the maximum number of stones the current player can obtain starting from `piles[i]` with the given `M`.

Since this is a game where both players play optimally, we can use the minimax principle. The current player wants to maximize their score. This is equivalent to choosing a move that minimizes the maximum score the opponent can get from the subsequent state. The total number of stones from pile `i` onwards is fixed. Let's say this is `total_remaining`. If the current player makes a move and the opponent is guaranteed to get `opponent_score` from the remaining piles, the current player's final score will be `total_remaining - opponent_score`. To maximize their own score, the current player must choose a move that minimizes the opponent's score.

The recurrence relation is:
`solve(i, M) = max over X { total_remaining_stones - solve(i + X, max(M, X)) }`
where `1 <= X <= 2*M`.

To avoid recomputing the sum of remaining piles repeatedly, we can pre-calculate a suffix sum array.

```java
class Solution {
    int[] suffixSum;
    int n;

    public int stoneGameII(int[] piles) {
        this.n = piles.length;
        this.suffixSum = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffixSum[i] = suffixSum[i + 1] + piles[i];
        }
        return solve(0, 1);
    }

    private int solve(int i, int M) {
        if (i >= n) {
            return 0;
        }
        // Optimization: If the current player can take all remaining piles
        if (i + 2 * M >= n) {
            return suffixSum[i];
        }

        int maxScore = 0;
        // Iterate through all possible moves X
        for (int X = 1; X <= 2 * M; X++) {
            // Opponent's score from the remaining piles
            int opponentScore = solve(i + X, Math.max(M, X));
            // Current player's score for this move
            int currentScore = suffixSum[i] - opponentScore;
            maxScore = Math.max(maxScore, currentScore);
        }
        return maxScore;
    }
}
```
### Algorithm
- Create a recursive function `solve(i, M)` that returns the maximum score the current player can get from piles starting at index `i` with the current `M`.
- Pre-calculate a suffix sum array to quickly find the sum of stones in any range `piles[i:]`.
- The base case for the recursion is when `i` is out of bounds, in which case the score is 0.
- In the recursive function, iterate through all possible moves `X` (from 1 to `2*M`).
- For each move `X`, the current player takes `X` piles. The remaining piles are passed to the opponent. The opponent's score will be `solve(i + X, max(M, X))`. 
- The current player's score for this move is the total remaining stones (`suffixSum[i]`) minus the opponent's score.
- The function returns the maximum score found among all possible `X` values.
- The initial call is `solve(0, 1)`.

## Top-Down Dynamic Programming with Memoization
This approach enhances the brute-force recursion by adding memoization, a technique also known as top-down dynamic programming. We store the results of solved subproblems (game states) in a cache or table. When the recursive function encounters a state it has seen before, it retrieves the result from the cache instead of recomputing it. This drastically reduces the number of calculations, pruning the recursion tree and making the solution efficient enough to pass within the given constraints.
**Time:** O(n^3). There are O(n^2) states, and each state computation involves a loop of up to O(n) iterations. · **Space:** O(n^2), for the memoization table and the recursion stack.
**Pros:** Efficient enough for the given constraints.; Guarantees finding the optimal solution.; Often more intuitive to write than the bottom-up approach as it follows the logical flow of the game.
**Cons:** Uses O(n^2) space for the memoization table.; May have higher overhead than the bottom-up iterative approach due to recursion.
### Explanation
The state of the game is defined by `(i, M)`. Since the brute-force approach recomputes the solution for the same state multiple times, we can optimize it by storing the results. We use a 2D array, `memo[n+1][n+1]`, where `memo[i][M]` will store the result of `solve(i, M)`.

The logic of the recursive function `solve(i, M)` remains the same, but with two additions:
1. At the beginning of the function, we check if `memo[i][M]` has been computed. If it has, we return the value immediately.
2. After computing the maximum score for the state `(i, M)`, we store it in `memo[i][M]` before returning.

This ensures that each state `(i, M)` is solved only once. The number of states is determined by `i` (from 0 to `n`) and `M` (from 1 to `n`), giving `O(n^2)` unique states.

```java
class Solution {
    int[] suffixSum;
    int[][] memo;
    int n;

    public int stoneGameII(int[] piles) {
        this.n = piles.length;
        this.suffixSum = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffixSum[i] = suffixSum[i + 1] + piles[i];
        }
        // A safe upper bound for M is n. Initialize with 0 as scores are positive.
        this.memo = new int[n + 1][n + 1];
        return solve(0, 1);
    }

    private int solve(int i, int M) {
        if (i >= n) {
            return 0;
        }
        if (memo[i][M] != 0) {
            return memo[i][M];
        }
        // Optimization: If the current player can take all remaining piles
        if (i + 2 * M >= n) {
            return memo[i][M] = suffixSum[i];
        }

        int maxScore = 0;
        // Try all possible moves X
        for (int X = 1; X <= 2 * M; X++) {
            int opponentScore = solve(i + X, Math.max(M, X));
            int currentScore = suffixSum[i] - opponentScore;
            maxScore = Math.max(maxScore, currentScore);
        }
        return memo[i][M] = maxScore;
    }
}
```
### Algorithm
- Use the same recursive structure as the brute-force approach.
- Introduce a 2D memoization table, `memo[i][M]`, to store the results of `solve(i, M)`.
- Before computing `solve(i, M)`, check if the result is already in the memoization table. If so, return the stored value.
- If the result is not stored, compute it using the same recursive logic as the brute-force method.
- After computing the result, store it in `memo[i][M]` before returning it.
- The initial call remains `solve(0, 1)`.

## Bottom-Up Dynamic Programming
This approach, also known as bottom-up dynamic programming, solves the problem iteratively, eliminating recursion. We build a DP table that stores the solution for each subproblem. By filling the table in a specific order (from the end of the game to the beginning), we ensure that when we calculate the solution for a state, the solutions for all the subsequent states it depends on are already available. This method has the same time and space complexity as the memoization approach but can be slightly faster in practice due to the absence of recursion overhead.
**Time:** O(n^3). We have three nested loops: `i` from `n` to `0`, `M` from `1` to `n`, and `X` from `1` to `2*M` (at most `2n`). · **Space:** O(n^2), for the 2D DP table.
**Pros:** Highly efficient and guaranteed to be optimal.; Avoids recursion overhead, which can lead to a slight performance improvement over the top-down approach.; No risk of stack overflow for large inputs (though not an issue with n<=100).
**Cons:** Can be less intuitive to formulate than the recursive top-down approach.; Uses O(n^2) space, same as the memoization approach.
### Explanation
We can convert the top-down memoized recursion into an iterative solution. We'll use a 2D array `dp[n+1][n+1]` where `dp[i][M]` stores the maximum number of stones the current player can get starting from pile `i` with a given `M`.

The calculation for `dp[i][M]` depends on values `dp[i+X][...]`, where `X > 0`. This dependency on states with a larger `i` suggests that we should fill our DP table by iterating `i` from `n-1` down to `0`.

The recurrence relation remains the same:
`dp[i][M] = max_{1<=X<=2M} (suffixSum[i] - dp[i + X][max(M, X)])`

We iterate through all states `(i, M)` and fill the `dp` table. The base cases `dp[n][M] = 0` are handled by initializing the table with zeros.

```java
class Solution {
    public int stoneGameII(int[] piles) {
        int n = piles.length;
        if (n == 0) {
            return 0;
        }

        int[] suffixSum = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffixSum[i] = suffixSum[i + 1] + piles[i];
        }

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

        for (int i = n - 1; i >= 0; i--) {
            for (int M = 1; M <= n; M++) {
                // If the current player can take all remaining piles
                if (i + 2 * M >= n) {
                    dp[i][M] = suffixSum[i];
                    continue;
                }
                
                int minOpponentScore = Integer.MAX_VALUE;
                // Try all possible moves X
                for (int X = 1; X <= 2 * M; X++) {
                    // Opponent's score from the remaining piles
                    // The state (i+X, max(M,X)) is already computed because i+X > i
                    int opponentScore = dp[i + X][Math.max(M, X)];
                    minOpponentScore = Math.min(minOpponentScore, opponentScore);
                }
                dp[i][M] = suffixSum[i] - minOpponentScore;
            }
        }

        return dp[0][1];
    }
}
```
### Algorithm
- Create a 2D DP table, `dp[n+1][n+1]`, where `dp[i][M]` stores the max stones the current player can get from `piles[i:]` with value `M`.
- Pre-calculate the suffix sum array `suffixSum`.
- Iterate through the piles index `i` from `n-1` down to `0`.
- For each `i`, iterate through `M` from `1` to `n`.
- Inside the loops, calculate `dp[i][M]` by trying all possible moves `X` (from 1 to `2*M`).
- The score for a move `X` is `suffixSum[i] - dp[i + X][max(M, X)]`. The value `dp[i + X][...]` is already computed because we iterate `i` backwards.
- `dp[i][M]` is the maximum score over all possible `X`.
- The final answer is `dp[0][1]`.

# Solutions
### Java

```java
class Solution {
private
  int[] s;
private
  Integer[][] f;
private
  int n;
public
  int stoneGameII(int[] piles) {
    n = piles.length;
    s = new int[n + 1];
    f = new Integer[n][n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + piles[i];
    }
    return dfs(0, 1);
  }
private
  int dfs(int i, int m) {
    if (m * 2 >= n - i) {
      return s[n] - s[i];
    }
    if (f[i][m] != null) {
      return f[i][m];
    }
    int res = 0;
    for (int x = 1; x <= m * 2; ++x) {
      res = Math.max(res, s[n] - s[i] - dfs(i + x, Math.max(m, x)));
    }
    return f[i][m] = res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int stoneGameII(vector<int> &piles) {
    int n = piles.size();
    int s[n + 1];
    s[0] = 0;
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + piles[i];
    }
    int f[n][n + 1];
    memset(f, 0, sizeof f);
    function<int(int, int)> dfs = [&](int i, int m) -> int {
      if (m * 2 >= n - i) {
        return s[n] - s[i];
      }
      if (f[i][m]) {
        return f[i][m];
      }
      int res = 0;
      for (int x = 1; x <= m << 1; ++x) {
        res = max(res, s[n] - s[i] - dfs(i + x, max(x, m)));
      }
      return f[i][m] = res;
    };
    return dfs(0, 1);
  }
};

```

### Python

```python
class Solution:
    def stoneGameII(self, piles: List[int]) -> int: @ cache def dfs(i, m): if m * 2 >= n - i: return s[n] - s[i] return max(s[n] - s[i] - dfs(i + x, max(m, x)) for x in range(1, m << 1 | 1)) n = len(piles) s = list(accumulate(piles, initial=0)) return dfs(0, 1)

```