877. Stone Game — DSA Atlas

877

MediumTwo-Dimensional Dynamic ProgrammingInterval dynamic programming (game theory)Minimax on interval score difference

Stone Game

Alice and Bob play with an even-length array piles where piles[i] is the number of stones in pile i and the total is odd. They alternate turns, Alice first, each taking a whole pile from either the left or right end. The player with more stones wins. Assuming optimal play, return true if Alice wins.

Open official problem prompt ↗

In plain English

Determine whether Alice, moving first and playing optimally, ends with strictly more stones than Bob.

Picture it like this

Two people splitting a row of gift boxes from the ends, each trying to maximize the net lead; you plan around the swing in the lead rather than counting boxes twice.

Example

Input: piles = [5, 3, 4, 5]
Output: true
Why: Alice takes the right 5; whatever Bob takes, Alice takes the other 5, guaranteeing at least 10 of the 17 stones.

Constraints

2 <= piles.length <= 500piles.length is even1 <= piles[i] <= 500sum(piles) is odd

Pattern lesson

See the pattern, then code

Minimax on interval score difference

↗

Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. Track the score difference for the player to move: take a pile from an end, then subtract the opponent's optimal difference on the rest since turns flip. Alice wins exactly when the full-range difference is positive.

New words, made simpleKnow these before the algorithm

Minimax: Each player maximizes their own result assuming the opponent plays optimally against them.
Score difference: A single number capturing (mover's stones minus opponent's) so the state stays compact.
Parity guarantee: An odd total means no ties are possible, so a positive difference cleanly decides a win.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute-force game tree

Exponential; overlapping subranges recomputed endlessly.

Explore every take-left/take-right branch.

Time O(2^n)Space O(n)

Parity argument

Clever and correct for this exact problem, but it does not generalize and is a proof, not a computation.

With even piles and odd sum, Alice can always grab all odd-indexed or all even-indexed piles, one of which sums higher, so she always wins.

Time O(1)Space O(1)

Best choiceDifference interval DP

General, robust, and the transferable technique interviewers want to see.

dp[i][j] = best margin for the mover on piles[i..j].

Time O(n^2)Space O(n^2)

The rule we keep true

Invariant

dp[i][j] is exactly the maximum stone margin the player to move can secure over the opponent given only piles[i..j] remain.

Why this is correct

Reasoning

Taking an end pile adds its value, after which the opponent faces the remaining range and secures dp of that subrange for themselves, counting against the current player. Maximizing over the two ends gives the mover's best guaranteed margin; a positive full-range margin means Alice finishes ahead.

The algorithm in three movesSay these aloud before coding

1Define dp[i][j] as Alice-vs-opponent best stone difference on piles[i..j]

dp[i][i] = piles[i]

2Base case: a single pile gives difference piles[i]

dp[0][1]=max(5-3,3-5)=2

3Transition: max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])

dp[0][3]=max(5-dp[1][3], 5-dp[0][2]) > 0

4Fill by increasing range length

5Return dp[0][n-1] > 0

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readpiles = [5,3,4,5]

2 · AskSingle piles?

3 · Update statedp[i][i] = piles[i]

4 · ResultDiagonal filled

Key takeaway

Only the two highlighted end piles are takeable on the current turn.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-6Base diagonal
A lone pile is the whole margin for whoever takes it.
2
Lines 7-11Grow ranges
Negate the opponent's sub-range margin to model the turn flip after each take.
3
Lines 12Verdict
A strictly positive full-range margin means Alice wins; ties are impossible by the odd-sum constraint.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Two piles: Alice takes the larger and wins
Odd total guarantees no tie, so > 0 is the correct test
Large equal-looking piles still resolve via the DP

Common beginner mistakes

Using >= 0 like Predict the Winner; here the odd sum means a tie cannot occur, but > 0 remains the semantically correct win test
Adding rather than subtracting the opponent's sub-range dp
Row-major fill order that reads uncomputed cells

Check your understanding

How does this differ from Predict the Winner (486)?

Stone Game

Stone Game

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Two-Dimensional Dynamic Programming