Stone Game II
Medium · Dynamic Programming · Array · Math · Dynamic Programming · Prefix Sum · Game Theory
Problem
Alice and Bob play with piles of stones in a row, where piles[i] is the size of pile i. Both want to end with as many stones as possible. Alice moves first, and a value M starts at 1.
On each turn the current player takes all the stones in the first X remaining piles, where 1 <= X <= 2M. Afterwards M becomes max(M, X). The game ends when every pile has been taken.
Assuming both play optimally, return the maximum number of stones Alice can collect.
Examples
Input: piles = [3,1,5] Output: 4
If Alice takes only the 3, Bob may take 1 and 5. Taking 3 and 1 (X = 2) leaves Bob just the 5, so Alice gets 4.
Input: piles = [1,2,3,4] Output: 5
Alice takes 1; Bob's best reply takes 2 and 3, leaving Alice the 4 for a total of 5.
Input: piles = [2,7] Output: 9
With M = 1 Alice may take two piles, so she takes both: 9.
Constraints
- 1 <= piles.length <= 100
- 1 <= piles[i] <= 10^4
Approaches
- Baseline: full game tree — time exponential, space O(n) for the recursion
Follow-up
The trick "I get everything that is left minus what my opponent gets" turns a two-player game into a one-function recurrence. The use cases keep that trick and change the move rule: a fixed limit of K piles per turn, and a limit that grows by one each turn.
Related problems
Start free on Cariara · Coding problems · System design studio
