Stone Game (LeetCode 877)

The problem

Piles of stones sit in a row. Alice and Bob take turns, Alice first. On each turn a player takes the whole pile from either end of the row. Both play optimally. Return True if Alice ends with more stones than Bob. The row has an even number of piles and the total is odd, so there are no ties.

Input:  piles = [5, 3, 4, 5]
Output: True

Alice takes the left 5. Whatever Bob takes, Alice can take the other 5 next and win 10 to 7 (or better).

How to think about it

Start with brute force. Try every sequence of left/right choices. Each turn has two options, so there are 2ⁿ games. And “Alice plays optimally, Bob plays optimally” means you must take a max at Alice’s turns and a min at Bob’s, which is awkward to track.

The key insight: track the score difference from the mover’s point of view. Let dp(i, j) be the most the current player can finish ahead of the other player, using only piles[i..j]. If you take the left pile, you gain piles[i] and then the opponent becomes “the current player” on i+1..j, so they finish dp(i+1, j) ahead of you. Your net lead is piles[i] - dp(i+1, j). Same for the right end. So:

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

One function serves both players, because it is always “me minus you”.

The game state is just a range. Whatever was taken, what’s left is always a contiguous slice i..j. That gives only O(n²) states.

Which pattern is this? Interval DP with minimax. The tell is “take from either end”: the remaining items form a range, so the state is (i, j).

Approach

1. Define dp(i, j) as above. An empty range (i > j) gives 0.
2. Recurse on both choices and take the max, as in the formula.
3. Memoise with lru_cache, so each (i, j) is solved once.
4. Alice wins exactly when dp(0, n-1) > 0.

Solution

from functools import lru_cache
def stoneGame(piles):
    n = len(piles)
    @lru_cache(None)
    def dp(i, j):
        if i > j: return 0
        # take left or right; the opponent then leads by dp(...) on the rest
        return max(piles[i] - dp(i + 1, j), piles[j] - dp(i, j - 1))
    return dp(0, n - 1) > 0
# stoneGame([5,3,4,5]) -> True

Dry run

The values of dp(i, j) on [5, 3, 4, 5], from short ranges up:

dp(0, 3) = 1 > 0, so Alice wins: True.

Complexity

• Time: O(n²). There are n(n+1)/2 ranges and each does O(1) work.
• Space: O(n²). For the memo, plus O(n) recursion depth. A bottom-up 1-D table can cut this to O(n).

Edge cases and pitfalls

• The maths shortcut. With an even count, Alice can always take all even-indexed or all odd-indexed piles, so return True is correct for this exact problem. Say so, but show the DP: interviewers want it, and follow-ups (odd counts, Stone Game II/VII) break the shortcut.
• Tracking two separate scores (Alice’s and Bob’s) doubles the state and invites max/min mistakes. The difference trick avoids that.
• Sign error: it is piles[i] - dp(...), not +. The opponent’s lead counts against you.
• Large n with recursion can hit depth limits; the bottom-up version avoids that.

Related problems

• Burst Balloons (LeetCode 312): interval DP where you split a range on a middle choice.
• Longest Palindromic Subsequence (LeetCode 516): another dp[i][j] that shrinks from either end.
• Minimum Cost to Cut a Stick (LeetCode 1547): interval DP filled by increasing length.