# Stone Game III
**Difficulty:** HARD
[External](https://leetcode.com/problems/stone-game-iii)
Canonical: https://scaleengineer.com/dsa/problems/stone-game-iii
**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
---
## Problem
Alice and Bob continue their games with piles of stones. There are several stones **arranged in a row**, and each stone has an associated value which is an integer given in the array `stoneValue`.

Alice and Bob take turns, with Alice starting first. On each player's turn, that player can take `1`, `2`, or `3` stones from the **first** remaining stones in the row.

The score of each player is the sum of the values of the stones taken. The score of each player is `0` initially.

The objective of the game is to end with the highest score, and the winner is the player with the highest score and there could be a tie. The game continues until all the stones have been taken.

Assume Alice and Bob **play optimally**.

Return `"Alice"` _if Alice will win,_ `"Bob"` _if Bob will win, or_ `"Tie"` _if they will end the game with the same score_.

**Example 1:**

**Input:** stoneValue = [1,2,3,7]
**Output:** "Bob"
**Explanation:** Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

**Example 2:**

**Input:** stoneValue = [1,2,3,-9]
**Output:** "Alice"
**Explanation:** Alice must choose all the three piles at the first move to win and leave Bob with negative score.
If Alice chooses one pile her score will be 1 and the next move Bob's score becomes 5. In the next move, Alice will take the pile with value = -9 and lose.
If Alice chooses two piles her score will be 3 and the next move Bob's score becomes 3. In the next move, Alice will take the pile with value = -9 and also lose.
Remember that both play optimally so here Alice will choose the scenario that makes her win.

**Example 3:**

**Input:** stoneValue = [1,2,3,6]
**Output:** "Tie"
**Explanation:** Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise she will lose.

**Constraints:**

* `1 <= stoneValue.length <= 5 * 104`
* `-1000 <= stoneValue[i] <= 1000`

# Approaches
## Brute-Force Recursion
This approach directly translates the game's rules into a recursive solution. The problem has optimal substructure and overlapping subproblems, which are characteristics of problems solvable by recursion. We define a function that calculates the maximum score difference a player can achieve from a given starting stone. Since both players play optimally, they will always make the move that maximizes their final score relative to their opponent.
**Time:** O(3^n), where n is the number of stones. For each state, the function branches into three recursive calls, leading to an exponential number of computations. · **Space:** O(n), where n is the number of stones. This is due to the maximum depth of the recursion stack.
**Pros:** Simple to conceptualize and implement based on the problem's recursive nature.
**Cons:** Extremely inefficient due to a large number of redundant computations for the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The core idea is to model the game as a recursive function. Let's define `solve(i)` as the maximum score difference the current player can get over the opponent from the stones `stoneValue[i:]`. When it's a player's turn at index `i`, they can take `k` stones, where `k` can be 1, 2, or 3. If they take `k` stones, their score for this turn is the sum of values of these `k` stones. The game then proceeds from index `i+k`, but now it's the opponent's turn. The opponent, playing optimally, will achieve a score difference of `solve(i+k)` from the remaining stones. From the current player's perspective, this is a loss of `solve(i+k)`. Thus, the total score difference for the current player, if they take `k` stones, is `(sum of k stones) - solve(i+k)`. The player will choose the `k` that maximizes this value. The final answer depends on `solve(0)`: if it's positive, Alice wins; if negative, Bob wins; if zero, it's a tie.

```java
class Solution {
    public String stoneGameIII(int[] stoneValue) {
        int diff = solve(stoneValue, 0);
        if (diff > 0) {
            return "Alice";
        } else if (diff < 0) {
            return "Bob";
        } else {
            return "Tie";
        }
    }

    private int solve(int[] stoneValue, int i) {
        int n = stoneValue.length;
        if (i >= n) {
            return 0;
        }

        int maxDiff = Integer.MIN_VALUE;
        int currentSum = 0;
        // Iterate through the 3 possible moves (take 1, 2, or 3 stones)
        for (int k = 0; k < 3 && i + k < n; k++) {
            currentSum += stoneValue[i + k];
            maxDiff = Math.max(maxDiff, currentSum - solve(stoneValue, i + k + 1));
        }
        
        return maxDiff;
    }
}
```
### Algorithm
- Define a recursive function `solve(i)` that returns the maximum score difference the current player can achieve starting from index `i`.
- **Base Case:** If `i` is out of bounds (i.e., `i >= n`), it means there are no stones left, so the difference is 0. Return 0.
- **Recursive Step:** The current player at index `i` has three choices:
  1. Take 1 stone: The player's score increases by `stoneValue[i]`. The turn passes to the opponent, who will play optimally from index `i+1`. The opponent's score difference from that point will be `solve(i+1)`. Therefore, the current player's net score difference for this choice is `stoneValue[i] - solve(i+1)`.
  2. Take 2 stones: Net score difference is `(stoneValue[i] + stoneValue[i+1]) - solve(i+2)`.
  3. Take 3 stones: Net score difference is `(stoneValue[i] + stoneValue[i+1] + stoneValue[i+2]) - solve(i+3)`.
- The player will choose the option that maximizes their score difference. So, `solve(i)` is the maximum of the valid choices.
- The initial call is `solve(0)`. The final result is determined by the sign of `solve(0)`.

## Dynamic Programming (O(n) Space)
The brute-force approach is slow because it repeatedly solves the same subproblems. We can significantly optimize this by using dynamic programming. This can be implemented using a top-down approach with memoization or a bottom-up iterative approach. Both share the same core logic and complexity.

**Top-Down with Memoization:** We use a helper array, `memo`, to store the result of `solve(i)` after computing it for the first time. Subsequent calls for the same `i` will fetch the result from `memo` in O(1) time, avoiding redundant calculations.

**Bottom-Up:** This approach avoids recursion by solving subproblems iteratively. We use a `dp` array where `dp[i]` stores the solution for the subproblem starting at index `i`. We fill the table from the end (`dp[n-1]`) to the beginning (`dp[0]`), since the solution for `dp[i]` depends on solutions for `dp[i+1]`, `dp[i+2]`, and `dp[i+3]`.
**Time:** O(n). Each state `dp[i]` is computed once, and each computation takes constant time (a loop of size 3). · **Space:** O(n). The top-down approach uses O(n) for the memoization table and O(n) for the recursion stack. The bottom-up approach uses O(n) for the DP table.
**Pros:** Efficient enough to pass the given constraints.; Guarantees that each subproblem is solved only once.
**Cons:** Uses O(n) extra space for the memoization table and recursion stack.; For extremely large n (not the case here), it could lead to a stack overflow error.
### Explanation
### Top-Down with Memoization
This approach enhances the recursive solution by caching results. An array `memo` of size `n` is used. `memo[i]` will store the result of `solve(i)`. When `solve(i)` is called, it first checks `memo[i]`. If a value exists, it's returned. Otherwise, the value is computed, stored in `memo[i]`, and then returned. This pruning of the recursion tree reduces the time complexity dramatically.

```java
// Top-Down with Memoization
class Solution {
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        Integer[] memo = new Integer[n];
        int diff = solve(stoneValue, 0, memo);
        if (diff > 0) {
            return "Alice";
        } else if (diff < 0) {
            return "Bob";
        } else {
            return "Tie";
        }
    }

    private int solve(int[] stoneValue, int i, Integer[] memo) {
        int n = stoneValue.length;
        if (i >= n) {
            return 0;
        }
        if (memo[i] != null) {
            return memo[i];
        }

        int maxDiff = Integer.MIN_VALUE;
        int currentSum = 0;
        for (int k = 0; k < 3 && i + k < n; k++) {
            currentSum += stoneValue[i + k];
            maxDiff = Math.max(maxDiff, currentSum - solve(stoneValue, i + k + 1, memo));
        }
        
        return memo[i] = maxDiff;
    }
}
```

### Bottom-Up DP
This iterative approach builds the solution from the base cases. We create a `dp` array of size `n+k` (where k=3, for easier boundary handling). `dp[i]` will store the maximum difference from index `i`. We iterate from `i = n-1` down to `0`, calculating `dp[i]` based on the already computed values `dp[i+1]`, `dp[i+2]`, and `dp[i+3]`. The final answer is `dp[0]`.

```java
// Bottom-Up DP
class Solution {
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        int[] dp = new int[n + 3]; // dp[n], dp[n+1], dp[n+2] will be 0 by default

        for (int i = n - 1; i >= 0; i--) {
            dp[i] = Integer.MIN_VALUE;
            int currentSum = 0;
            for (int k = 0; k < 3 && i + k < n; k++) {
                currentSum += stoneValue[i + k];
                dp[i] = Math.max(dp[i], currentSum - dp[i + k + 1]);
            }
        }

        int diff = dp[0];
        if (diff > 0) {
            return "Alice";
        } else if (diff < 0) {
            return "Bob";
        } else {
            return "Tie";
        }
    }
}
```
### Algorithm
- The recursive structure is the same as the brute-force approach. The key difference is the use of a memoization table (e.g., an array `memo`) to store the results of subproblems.
- Initialize the `memo` array with a sentinel value (like `null` or `Integer.MIN_VALUE`) to indicate that a state has not been computed.
- In the recursive function `solve(i)`, first check if `memo[i]` contains a pre-computed result. If it does, return it immediately.
- If not, compute the result as in the brute-force approach by exploring the 1, 2, or 3 stone choices.
- Before returning the computed maximum difference, store it in `memo[i]`.
- This ensures that each subproblem `solve(i)` is computed only once.

## Space-Optimized Bottom-Up Dynamic Programming
This approach further optimizes the bottom-up DP solution by reducing its space complexity. By analyzing the recurrence relation, we notice that to compute the DP value for the current state `i`, we only need the results of the next three states (`i+1`, `i+2`, `i+3`). This allows us to discard older DP values that are no longer needed, reducing the space requirement from a full array of size `n` to just a few variables.
**Time:** O(n), as we still need to iterate through the entire array once. · **Space:** O(1), as we only use a fixed-size array (or a few variables) regardless of the input size.
**Pros:** Most optimal solution with linear time and constant space complexity.
**Cons:** The logic with modular arithmetic can be slightly more complex to reason about compared to the straightforward DP table.
### Explanation
Instead of an O(n) DP array, we can use an array of size 4. Let's call it `dp`. `dp[i % 4]` will store the result for the subproblem starting at index `i`. As we iterate `i` from `n-1` down to `0`, the values for `dp[i+1]`, `dp[i+2]`, and `dp[i+3]` will be available in our small `dp` array at indices `(i+1)%4`, `(i+2)%4`, and `(i+3)%4` respectively. This is because when we computed `dp[i+1]`, we used `dp[i+2], dp[i+3], dp[i+4]`, and so on. The required values are always within the last few computed results. This 'sliding window' of necessary DP states allows for a constant space solution.

```java
class Solution {
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        // We only need to store the last 3 dp values, so an array of size 4 is sufficient.
        // dp[i % 4] will store the result for the subproblem starting at index i.
        // The extra space handles indices i+1, i+2, i+3 gracefully.
        int[] dp = new int[4];

        for (int i = n - 1; i >= 0; i--) {
            // Initialize with a very small value
            dp[i % 4] = Integer.MIN_VALUE;
            
            // Option 1: Take 1 stone
            int take1 = stoneValue[i] - dp[(i + 1) % 4];
            dp[i % 4] = Math.max(dp[i % 4], take1);
            
            // Option 2: Take 2 stones
            if (i + 1 < n) {
                int take2 = stoneValue[i] + stoneValue[i + 1] - dp[(i + 2) % 4];
                dp[i % 4] = Math.max(dp[i % 4], take2);
            }
            
            // Option 3: Take 3 stones
            if (i + 2 < n) {
                int take3 = stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[(i + 3) % 4];
                dp[i % 4] = Math.max(dp[i % 4], take3);
            }
        }

        int diff = dp[0];
        if (diff > 0) {
            return "Alice";
        } else if (diff < 0) {
            return "Bob";
        } else {
            return "Tie";
        }
    }
}
```
### Algorithm
- Observe the DP transition: `dp[i]` depends only on `dp[i+1]`, `dp[i+2]`, and `dp[i+3]`.
- This means we don't need to store the entire DP table. We only need to keep track of the last 3 computed values.
- We can use a small, constant-size array (e.g., of size 4) to store these values, using modular arithmetic (`i % 4`) to cycle through the indices.
- We iterate from `i = n-1` down to `0` as in the bottom-up approach.
- In each step, we calculate `dp[i % 4]` using the values at `dp[(i+1) % 4]`, `dp[(i+2) % 4]`, and `dp[(i+3) % 4]`.
- After the loop finishes, the result for `dp[0]` will be stored at `dp[0 % 4]`, which is `dp[0]`.

# Solutions
### Java

```java
class Solution {
private
  int[] stoneValue;
private
  Integer[] f;
private
  int n;
public
  String stoneGameIII(int[] stoneValue) {
    n = stoneValue.length;
    f = new Integer[n];
    this.stoneValue = stoneValue;
    int ans = dfs(0);
    if (ans == 0) {
      return "Tie";
    }
    return ans > 0 ? "Alice" : "Bob";
  }
private
  int dfs(int i) {
    if (i >= n) {
      return 0;
    }
    if (f[i] != null) {
      return f[i];
    }
    int ans = -(1 << 30);
    int s = 0;
    for (int j = 0; j < 3 && i + j < n; ++j) {
      s += stoneValue[i + j];
      ans = Math.max(ans, s - dfs(i + j + 1));
    }
    return f[i] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  string stoneGameIII(vector<int> &stoneValue) {
    int n = stoneValue.size();
    int f[n];
    memset(f, 0x3f, sizeof(f));
    function<int(int)> dfs = [&](int i) -> int {
      if (i >= n) {
        return 0;
      }
      if (f[i] != 0x3f3f3f3f) {
        return f[i];
      }
      int ans = -(1 << 30), s = 0;
      for (int j = 0; j < 3 && i + j < n; ++j) {
        s += stoneValue[i + j];
        ans = max(ans, s - dfs(i + j + 1));
      }
      return f[i] = ans;
    };
    int ans = dfs(0);
    if (ans == 0) {
      return "Tie";
    }
    return ans > 0 ? "Alice" : "Bob";
  }
};

```

### Python

```python
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str: @ cache def dfs(i: int) -> int: if i >= n: return 0 ans, s = - inf, 0 for j in range(3): if i + j >= n: break s += stoneValue[i + j] ans = max(ans, s - dfs(i + j + 1)) return ans n = len(stoneValue) ans = dfs(0) if ans == 0: return 'Tie' return 'Alice' if ans > 0 else 'Bob'

```