Stone Game
Medium · Dynamic Programming · Array · Math · Dynamic Programming · Game Theory
Problem
Alice and Bob play with an even number of piles of stones in a row; piles[i] is the size of pile i. The total number of stones is odd, so there are no ties.
Players alternate turns, Alice first. On a turn a player removes the entire pile from either the left end or the right end of the row. When no piles remain, the player with more stones wins.
Assuming both play optimally, return true if Alice wins, otherwise false.
Examples
Input: piles = [4,1,2,6] Output: true
Alice takes 6. Whatever Bob takes from [4,1,2], Alice can still finish ahead, for example 6 + 2 against 4 + 1.
Input: piles = [7,2,9,1] Output: true
Alice can take both even-indexed piles, 7 and 9, for 16 against 3.
Constraints
- 2 <= len(piles) <= 500
- len(piles) is even
- 1 <= piles[i] <= 500
- sum(piles) is odd
Approaches
- Baseline: try every sequence of moves — time O(2^n), space O(n)
Follow-up
The parity trick answers who wins, but not by how much, and it breaks as soon as the count can be odd or the rules change. The interval DP survives those changes; the use cases change the scoring (score what remains) and the moves (one to three piles from the left).
Related problems
Start free on Cariara · Coding problems · System design studio
