Alice and Bob continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.
Alice and Bob take turns, with Alice starting first.
On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X). Initially, M = 1.
The game continues until all the stones have been taken.
Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.
Example 1:
Input: piles = [2,7,9,4,4]
Output: 10
Explanation:
2 + 4 + 4 = 10 stones in total.2 + 7 = 9 stones in total.So we return 10 since it's larger.
Example 2:
Input: piles = [1,2,3,4,5,100]
Output: 104
Constraints:
1 <= piles.length <= 1001 <= piles[i] <= 104Problem Overview: You are given an array of piles where each element represents stones in that pile. Two players take turns taking the first X piles where 1 ≤ X ≤ 2M, and M updates to max(M, X) after each move. Both players play optimally. The goal is to compute the maximum stones Alice (the first player) can collect.
Approach 1: Dynamic Programming with Memoization (O(n^3) time, O(n^2) space)
This is a classic optimal-play problem from game theory. Define a state dp(i, M) representing the maximum stones the current player can obtain starting from pile index i with parameter M. For each state, try taking X piles where 1 ≤ X ≤ 2M. After taking those piles, the opponent plays optimally, so your gain equals totalRemaining - dp(i + X, max(M, X)). Precompute suffix or prefix sums using prefix sums so the remaining stones can be calculated in O(1). Memoization stores results for each (i, M) pair to avoid recomputation. There are roughly O(n^2) states and up to 2M transitions per state, giving O(n^3) time.
Approach 2: Bottom-Up Dynamic Programming (O(n^3) time, O(n^2) space)
The same state transition can be implemented iteratively. Create a DP table where dp[i][M] stores the maximum stones the current player can collect from index i. Iterate indices from the end of the array toward the start because future states depend on later piles. For each state, evaluate every possible X choice in the range 1..2M. Use a precomputed suffix sum so you can instantly compute the total remaining stones and subtract the opponent's optimal result. Bottom-up DP avoids recursion overhead and can be easier to reason about during debugging, though the asymptotic complexity remains O(n^3).
Recommended for interviews: The memoized top-down dynamic programming solution is the most common interview answer. It shows you recognize the problem as a minimax-style DP and know how to model states with (index, M). Starting with the recursive formulation demonstrates understanding of the game strategy, while memoization reduces exponential exploration to polynomial time. If time allows, converting the same recurrence to bottom-up DP shows deeper mastery of dynamic programming state transitions.
In this approach, the problem is viewed as a decision-making process for Alice, where she wants to maximize her stones given Bob will try his best to minimize them. We can use Dynamic Programming (DP) to remember the maximum stones Alice can get from any position with a given M value.
The state dp[i][M] represents the maximum stones Alice can get starting from the i-th pile with a given M.
X = 1 to X = 2M piles.This Python solution uses a recursive helper function with memoization to store and reuse results for subproblems. It calculates Alice's optimal score by considering all possibilities of taking piles, updating the maximum number of stones Alice can secure.
Python
JavaScript
Java
Time Complexity: O(n3) due to two nested loops over the pile range and repeated evaluation of states.
Space Complexity: O(n2) for storing computed states in the memoization table.
A direct iterative solution (Non-memoization) that uses Dynamic Programming to build the solution from smaller subproblems towards larger problems. We create an array dp[i][M] where each entry records the maximum stones Alice can get starting at position i with parameter M. This approach calculates every step systematically, using previously solved smaller cases.
dp[i][M], calculate the possible maximum value by considering taking 1 to 2M piles in each iteration.This C solution uses a bottom-up approach with prefix sums to rapidly compute the sum of stones from any position onward. It fills up a DP table where each cell provides the best decision possible. The primary loop fills these using iterative tuning.
Time Complexity: O(n3), iterating over each subproblem space.
Space Complexity: O(n2) for the DP table tracking best decisions.
Since the player can take all the stones from the first X piles each time, that is, they can take the stones from an interval, we can first preprocess a prefix sum array s of length n+1, where s[i] represents the sum of the first i elements of the array piles.
Then we design a function dfs(i, m), which represents the maximum number of stones that the current player can take when they can start from index i of the array piles, and the current M is m. Initially, Alice starts from index 0, and M=1, so the answer we need to find is dfs(0, 1).
The calculation process of the function dfs(i, m) is as follows:
s[n] - s[i];x piles of the remaining ones, where 1 leq x leq 2m, and the maximum number of stones they can take is s[n] - s[i] - dfs(i + x, max(m, x)). That is to say, the number of stones that the current player can take is the number of all the remaining stones minus the number of stones that the opponent can take in the next round. We need to enumerate all x, and take the maximum value as the return value of the function dfs(i, m).To avoid repeated calculations, we can use memoization search.
Finally, we return dfs(0, 1) as the answer.
The time complexity is O(n^3), and the space complexity is O(n^2). Here, n is the length of the array piles.
Python
Java
C++
Go
TypeScript
Python
| Approach | Complexity |
|---|---|
| Dynamic Programming with Memoization | Time Complexity: O(n3) due to two nested loops over the pile range and repeated evaluation of states. |
| Bottom-Up Dynamic Programming | Time Complexity: O(n3), iterating over each subproblem space. |
| Prefix Sum + Memoization Search | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Memoization | O(n^3) | O(n^2) | Best for interviews. Natural recursive formulation with caching of (index, M) states. |
| Bottom-Up Dynamic Programming | O(n^3) | O(n^2) | Useful when recursion depth is a concern or when implementing iterative DP tables. |
Stone Game II - Leetcode 1140 - Python • NeetCodeIO • 30,981 views views
Watch 9 more video solutions →Practice Stone Game II with our built-in code editor and test cases.
Practice on FleetCode