# Stone Game
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/stone-game)
Canonical: https://scaleengineer.com/dsa/problems/stone-game
**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:** [Cisco](https://scaleengineer.com/companies/cisco)
---
## Problem
Alice and Bob play a game with piles of stones. There are an **even** 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. The **total** number of stones across all the piles is **odd**, so there are no ties.

Alice and Bob take turns, with **Alice starting first**. Each turn, a player takes the entire pile of stones either from the **beginning** or from the **end** of the row. This continues until there are no more piles left, at which point the person with the **most stones wins**.

Assuming Alice and Bob play optimally, return `true` _if Alice wins the game, or_ `false` _if Bob wins_.

**Example 1:**

**Input:** piles = [5,3,4,5]
**Output:** true
**Explanation:** 
Alice starts first, and can only take the first 5 or the last 5.
Say she takes the first 5, so that the row becomes [3, 4, 5].
If Bob takes 3, then the board is [4, 5], and Alice takes 5 to win with 10 points.
If Bob takes the last 5, then the board is [3, 4], and Alice takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alice, so we return true.

**Example 2:**

**Input:** piles = [3,7,2,3]
**Output:** true

**Constraints:**

* `2 <= piles.length <= 500`
* `piles.length` is **even**.
* `1 <= piles[i] <= 500`
* `sum(piles[i])` is **odd**.

# Approaches
## Brute-Force Recursion (Minimax)
This approach models the game using a recursive function that represents the choices of the current player. At each step, a player chooses the pile that maximizes their final score relative to the opponent. This is a classic minimax strategy. The function calculates the maximum score difference the current player can achieve from a given sub-array of piles.
**Time:** O(2^n), where n is the number of piles. For each subproblem, we make two recursive calls, leading to an exponential number of operations. · **Space:** O(n), where n is the number of piles. This is due to the maximum depth of the recursion call stack.
**Pros:** Conceptually simple and directly translates the game's rules into code.; Serves as a good foundation for more optimized dynamic programming solutions.
**Cons:** Extremely inefficient due to a large number of redundant calculations for the same subproblems.; Will result in a 'Time Limit Exceeded' error on most platforms for non-trivial input sizes.
### Explanation
We define a recursive function, say `solve(i, j)`, which returns the maximum score difference the current player can obtain from the piles in the range `[i, j]`. The current player can either take `piles[i]` or `piles[j]`. If the player takes `piles[i]`, their score increases by `piles[i]`. The opponent will then play on the subproblem `[i+1, j]` and will get a score difference of `solve(i+1, j)`. So, the current player's net score difference from this move is `piles[i] - solve(i+1, j)`. Similarly, if the player takes `piles[j]`, their net score difference is `piles[j] - solve(i, j-1)`. Since the player plays optimally, they will choose the move that maximizes their score difference. The initial call is `solve(0, n-1)`. Alice wins if this value is greater than 0. This approach recomputes the same subproblems multiple times, leading to an exponential time complexity.
```java
class Solution {
    public boolean stoneGame(int[] piles) {
        return solve(piles, 0, piles.length - 1) > 0;
    }

    private int solve(int[] piles, int i, int j) {
        if (i == j) {
            return piles[i];
        }
        
        int takeFirst = piles[i] - solve(piles, i + 1, j);
        int takeLast = piles[j] - solve(piles, i, j - 1);
        
        return Math.max(takeFirst, takeLast);
    }
}
```
### Algorithm
- Create a recursive helper function `solve(piles, i, j)` that returns the maximum score difference a player can get from piles `i` to `j`.
- **Base Case:** If `i == j`, there's only one pile left. The current player takes it, so return `piles[i]`.
- **Recursive Step:** The current player has two choices:
  1. Take `piles[i]`: Their score difference will be `piles[i]` minus the score difference the *next* player gets from the remaining piles `[i+1, j]`. This is `piles[i] - solve(piles, i + 1, j)`.
  2. Take `piles[j]`: Similarly, the score difference is `piles[j] - solve(piles, i, j - 1)`.
- The player chooses the move that maximizes their score difference. So, `solve(i, j)` returns `max(choice1, choice2)`.
- The initial call is `solve(piles, 0, piles.length - 1)`. Alice wins if this result is greater than 0.

## Dynamic Programming
This approach optimizes the brute-force recursion by using dynamic programming to avoid recomputing results for the same subproblems. We can implement this using either a top-down (memoization) or bottom-up (tabulation) method. Both will have the same time and space complexity. This approach correctly solves the general version of the stone game.
**Time:** O(n^2), as there are O(n^2) subproblems `(i, j)`, and each is computed once in constant time. · **Space:** O(n^2) for the DP table (`dp` or `memo`). The recursive stack space in the memoized version is also O(n), making the total O(n^2).
**Pros:** Guarantees an optimal solution by exploring all possibilities efficiently.; Much more efficient than brute-force recursion, making it feasible for the given constraints.; Avoids recursion overhead and potential stack overflow in the bottom-up version.
**Cons:** Requires O(n^2) space, which can be substantial for large `n`.; While optimal for the general problem, it's overkill for this specific version with its special constraints.
### Explanation
The core idea is to solve for smaller sub-ranges of piles first and use those results to solve for larger ranges. Let `dp[i][j]` be the maximum score difference the current player can achieve from the piles in the range `[i, j]`. The recurrence relation is `dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])`.

**Top-Down (Memoization):** This is a direct optimization of the recursive solution. We use a 2D array `memo` to store the results of `solve(i, j)`. Before computing, we check the `memo` table. If the result exists, we return it; otherwise, we compute it, store it, and then return.
```java
// Top-Down DP with Memoization
class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        Integer[][] memo = new Integer[n][n];
        return solve(piles, 0, n - 1, memo) > 0;
    }

    private int solve(int[] piles, int i, int j, Integer[][] memo) {
        if (i > j) return 0;
        if (memo[i][j] != null) return memo[i][j];
        
        int takeFirst = piles[i] - solve(piles, i + 1, j, memo);
        int takeLast = piles[j] - solve(piles, i, j - 1, memo);
        
        memo[i][j] = Math.max(takeFirst, takeLast);
        return memo[i][j];
    }
}
```
**Bottom-Up (Tabulation):** This approach builds the solution iteratively. We fill a 2D `dp` table, usually starting from the smallest subproblems (length 1) and building up to the full problem (length `n`).
```java
// Bottom-Up DP
class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = piles[i];
        }
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] > 0;
    }
}
```
### Algorithm
- The logic is based on solving subproblems of increasing length.
- Create a 2D DP table `dp` of size `n x n`, where `dp[i][j]` will store the max score difference for `piles[i...j]`.
- Iterate `len` (subproblem length) from 1 to `n`.
- Inside, iterate `i` (start index) from 0 to `n - len`.
- Calculate `j = i + len - 1` (end index).
- **Base Case (`len=1`):** `dp[i][i] = piles[i]`.
- **Recursive Step (`len>1`):** `dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])`.
- After the loops, `dp[0][n-1]` holds the result for the entire game. Return `dp[0][n-1] > 0`.

## Space-Optimized Dynamic Programming
We can optimize the space complexity of the bottom-up DP approach from O(n^2) to O(n). When calculating the values for a certain subproblem length, we only need the results from the immediately smaller length. This dependency allows us to discard older results and use only a 1D DP array.
**Time:** O(n^2). The nested loops for `len` and `i` remain the same as in the 2D DP approach. · **Space:** O(n) for the 1D DP array.
**Pros:** More space-efficient than the standard DP approach.; Maintains the O(n^2) time efficiency while reducing memory footprint.
**Cons:** The logic for updating the 1D array can be slightly harder to reason about compared to the 2D DP table.; Time complexity is still O(n^2).
### Explanation
Instead of a 2D `dp` table, we use a 1D array, say `dp[n]`. `dp[i]` will store the result for the subproblem of the current length starting at index `i`. We iterate over `len` from 2 to `n`. In the inner loop, we update the `dp` array for the current length. The recurrence becomes `dp[i] = max(piles[i] - dp[i+1], piles[j] - dp[i])`. Note that when we calculate the new `dp[i]`, the `dp[i+1]` and `dp[i]` on the right side are values from the previous length's calculation. We initialize the `dp` array with the base cases for `len=1`: `dp[i] = piles[i]`. Then, we loop `len` from 2 to `n` and `i` from 0 to `n-len`, updating `dp[i]` based on the formula.
```java
class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[] dp = new int[n];
        
        for (int i = 0; i < n; i++) {
            dp[i] = piles[i];
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i] = Math.max(piles[i] - dp[i + 1], piles[j] - dp[i]);
            }
        }

        return dp[0] > 0;
    }
}
```
### Algorithm
- Create a 1D DP array `dp` of size `n`.
- Initialize `dp` with the values of `piles` (this represents the base case for subproblems of length 1).
- Iterate `len` from 2 to `n`.
- Inside, iterate `i` from 0 to `n - len`.
- Update `dp[i]` using the recurrence `dp[i] = max(piles[i] - dp[i+1], piles[j] - dp[i])`, where `j = i + len - 1`.
- The values `dp[i+1]` and `dp[i]` on the right side refer to the values from the previous `len` iteration.
- After the loops, `dp[0]` will hold the final result for the whole game. Return `dp[0] > 0`.

## Mathematical Insight
This approach leverages the specific constraints of the problem to arrive at a solution without simulating the game. By analyzing the game's structure (even number of piles, odd total sum), we can prove that the first player, Alice, always has a winning strategy.
**Time:** O(1). The solution is based on a mathematical proof and is independent of the input size. · **Space:** O(1). No extra space is used.
**Pros:** Extremely efficient, providing an instant solution.; Demonstrates a deep understanding of the game's mathematical properties.; Requires no extra space.
**Cons:** This solution is highly specific to the given constraints and would not work if the constraints were different (e.g., an odd number of piles or an even total sum).
### Explanation
The key insight lies in partitioning the piles based on their original indices: even-indexed piles (`piles[0], piles[2], ...`) and odd-indexed piles (`piles[1], piles[3], ...`). Let `sum_even` be the total stones in even-indexed piles and `sum_odd` be the total in odd-indexed piles. The total number of stones, `sum_even + sum_odd`, is given to be odd. This implies that `sum_even` cannot be equal to `sum_odd`.

Alice, as the first player, can enforce a strategy. Because the number of piles `n` is even, the first pile (`piles[0]`) and the last pile (`piles[n-1]`) have different index parities (even and odd). Alice can choose one. After her move, Bob is left with two ends that have the same original index parity. No matter which one Bob chooses, he will leave Alice with one even-indexed end and one odd-indexed end on her next turn. This pattern continues.

This means Alice can decide at the start: 'I will only take piles from even original indices' or 'I will only take piles from odd original indices'. She can always execute her chosen strategy. 

- Strategy 1: Take `piles[0]` first, and on every subsequent turn, take the available pile that was at an even index. Her total score will be `sum_even`.
- Strategy 2: Take `piles[n-1]` first, and on every subsequent turn, take the available pile that was at an odd index. Her total score will be `sum_odd`.

Since `sum_even != sum_odd`, Alice can simply choose the strategy that corresponds to the larger sum. As she can guarantee she gets the larger share, and there are no ties, she always wins.
```java
class Solution {
    public boolean stoneGame(int[] piles) {
        return true;
    }
}
```
### Algorithm
- Analyze the game's constraints: `piles.length` is even, and `sum(piles)` is odd.
- Realize that Alice, the first player, can always force a win.
- She can choose to collect either all the stones from the piles at even indices or all the stones from piles at odd indices.
- Since the total sum is odd, the sum of even-indexed piles and odd-indexed piles cannot be equal.
- Alice can calculate both sums and choose the strategy that yields the larger sum.
- Therefore, Alice always wins. Return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean stoneGame(int[] piles) {
    int n = piles.length;
    int[][] f = new int[n][n];
    for (int i = 0; i < n; ++i) {
      f[i][i] = piles[i];
    }
    for (int i = n - 2; i >= 0; --i) {
      for (int j = i + 1; j < n; ++j) {
        f[i][j] = Math.max(piles[i] - f[i + 1][j], piles[j] - f[i][j - 1]);
      }
    }
    return f[0][n - 1] > 0;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool stoneGame(vector<int> &piles) {
    int n = piles.size();
    int f[n][n];
    memset(f, 0, sizeof(f));
    for (int i = 0; i < n; ++i) {
      f[i][i] = piles[i];
    }
    for (int i = n - 2; ~i; --i) {
      for (int j = i + 1; j < n; ++j) {
        f[i][j] = max(piles[i] - f[i + 1][j], piles[j] - f[i][j - 1]);
      }
    }
    return f[0][n - 1] > 0;
  }
};

```

### Python

```python
class Solution:
    def stoneGame(self, piles: List[int]) -> bool: n = len(piles) f = [[0] * n for _ in range(n)] for i, x in enumerate(piles): f[i][i] = x for i in range(n - 2, - 1, - 1): for j in range(i + 1, n): f[i][j] = max(piles[i] - f[i + 1][j], piles[j] - f[i][j - 1]) return f[0][n - 1] > 0

```