# LeetCode 877: Stone Game

## Problem Restatement

Alice and Bob play a game with an even number of stone piles arranged in a row.

Each pile has a positive number of stones.

Alice moves first. On each turn, a player must take one entire pile from either the left end or the right end of the row.

The game ends when all piles are taken.

The player with more stones wins.

The total number of stones is odd, so the game cannot end in a tie. We need to return `true` if Alice wins when both players play optimally. LeetCode gives the constraints that the number of piles is even and the total number of stones is odd.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `piles`, an array of positive integers |
| Output | `true` if Alice wins, otherwise `false` |
| Number of piles | Even |
| Tie possible | No, because the total number of stones is odd |
| Players | Alice moves first, Bob moves second |

Example function shape:

```python
def stoneGame(self, piles: list[int]) -> bool:
    ...
```

## Examples

Example 1:

```text
Input: piles = [5,3,4,5]
Output: true
```

Alice can win.

One possible play:

| Turn | Player | Takes | Remaining | Score |
|---|---|---:|---|---|
| 1 | Alice | 5 | `[3,4,5]` | Alice = 5 |
| 2 | Bob | 5 | `[3,4]` | Bob = 5 |
| 3 | Alice | 4 | `[3]` | Alice = 9 |
| 4 | Bob | 3 | `[]` | Bob = 8 |

Alice has `9`, Bob has `8`, so Alice wins.

Example 2:

```text
Input: piles = [2,1]
Output: true
```

Alice takes `2`.

Bob takes `1`.

Alice wins.

## First Thought: Simulate Choices

At each turn, a player has two choices:

1. Take the left pile.
2. Take the right pile.

A naive recursive solution can try both choices for every turn.

But this creates many repeated subproblems. The same remaining interval of piles can be reached through different earlier choices.

For example, from:

```text
[5,3,4,5]
```

After some choices, both players may reach the same middle interval:

```text
[3,4]
```

So we should model the game by intervals.

## Key Insight

The remaining game state is fully described by two indices:

```text
i = left boundary
j = right boundary
```

So `piles[i:j+1]` is the current row of remaining piles.

Instead of tracking Alice and Bob separately, we track the score difference from the current player's point of view.

Let:

```text
dp[i][j] = maximum score difference the current player can achieve over the opponent using piles[i..j]
```

A positive value means the current player can end ahead.

A negative value means the current player will end behind.

When the current player chooses the left pile, they gain `piles[i]`, then the opponent becomes the current player on interval `i + 1 .. j`.

The opponent can then achieve `dp[i + 1][j]` more than the current player from that smaller interval.

So the net difference for taking left is:

```text
piles[i] - dp[i + 1][j]
```

Taking right gives:

```text
piles[j] - dp[i][j - 1]
```

Therefore:

```text
dp[i][j] = max(
    piles[i] - dp[i + 1][j],
    piles[j] - dp[i][j - 1]
)
```

## Algorithm

Create a 2D table `dp`.

For a single pile, the current player takes it:

```python
dp[i][i] = piles[i]
```

Then fill larger intervals by length.

For each interval `[i, j]`:

1. Compute the result if the current player takes the left pile.
2. Compute the result if the current player takes the right pile.
3. Store the better score difference.

At the end, `dp[0][n - 1]` is the best score difference Alice can force for the whole game.

If it is positive, Alice wins.

## Correctness

The table entry `dp[i][j]` represents the maximum score difference the current player can force from the interval `piles[i..j]`.

For the base case, when `i == j`, there is one pile left. The current player takes it, so the score difference is exactly `piles[i]`.

For a larger interval, the current player has only two legal moves: take `piles[i]` or take `piles[j]`.

If the current player takes `piles[i]`, the opponent plays next on `piles[i + 1..j]`. Since `dp[i + 1][j]` is the opponent's best score difference from that interval, the current player's net advantage is `piles[i] - dp[i + 1][j]`.

The same reasoning gives `piles[j] - dp[i][j - 1]` when taking the right pile.

The current player chooses the better of these two moves, so the recurrence computes the best possible score difference.

The table is filled from shorter intervals to longer intervals, so every needed smaller interval has already been computed.

Thus, `dp[0][n - 1]` gives Alice's best possible score difference over Bob for the full game. If it is greater than zero, Alice wins.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | There are `O(n^2)` intervals |
| Space | `O(n^2)` | The DP table stores one value per interval |

## Implementation

```python
class Solution:
    def stoneGame(self, piles: list[int]) -> bool:
        n = len(piles)
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = piles[i]

        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1

                take_left = piles[i] - dp[i + 1][j]
                take_right = piles[j] - dp[i][j - 1]

                dp[i][j] = max(take_left, take_right)

        return dp[0][n - 1] > 0
```

## Code Explanation

We create the table:

```python
dp = [[0] * n for _ in range(n)]
```

`dp[i][j]` stores the best score difference the current player can force from `piles[i]` through `piles[j]`.

The base case is:

```python
for i in range(n):
    dp[i][i] = piles[i]
```

With one pile, the current player takes that pile.

Then we process intervals by length:

```python
for length in range(2, n + 1):
```

This ensures smaller intervals are computed before larger intervals.

For each interval:

```python
j = i + length - 1
```

The current player may take the left pile:

```python
take_left = piles[i] - dp[i + 1][j]
```

Or the right pile:

```python
take_right = piles[j] - dp[i][j - 1]
```

We store the better result:

```python
dp[i][j] = max(take_left, take_right)
```

Finally:

```python
return dp[0][n - 1] > 0
```

If Alice can force a positive score difference, Alice wins.

## Mathematical Shortcut

For this specific LeetCode problem, Alice can always win.

The reason is that the number of piles is even. Alice can decide, on her first move, whether she wants to take all piles that originally had even indices or all piles that originally had odd indices.

Because the total sum is odd, one of those two groups has a larger total.

Alice can force herself to take the larger group by choosing the correct end on every turn.

So the accepted solution can be:

```python
class Solution:
    def stoneGame(self, piles: list[int]) -> bool:
        return True
```

This is valid for the given constraints, but the interval DP version is more useful for learning because it also works for many related game problems where the shortcut does not apply.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.stoneGame([5, 3, 4, 5]) is True
    assert s.stoneGame([2, 1]) is True
    assert s.stoneGame([1, 2, 3, 1]) is True
    assert s.stoneGame([7, 8, 8, 10]) is True
    assert s.stoneGame([3, 9, 1, 2]) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[5,3,4,5]` | Standard example with several choices |
| `[2,1]` | Smallest valid number of piles |
| `[1,2,3,1]` | Requires optimal choice |
| `[7,8,8,10]` | Even number of piles with close values |
| `[3,9,1,2]` | Large middle value affects decisions |