Stone Game II
MedPrompt
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:
- If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get
2 + 4 + 4 = 10stones in total. - If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get
2 + 7 = 9stones 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] <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the game's logic into a recursive function. The function explores every possible move Alice can make, and for each move, it recursively explores every possible move Bob can make, and so on. This creates a large tree of game states. Since the same game states (defined by the starting pile index i and the value of M) can be reached through different sequences of moves, this method recomputes the optimal strategy for these states multiple times, leading to exponential time complexity.
Algorithm
- Create a recursive function
solve(i, M)that returns the maximum score the current player can get from piles starting at indexiwith the currentM. - Pre-calculate a suffix sum array to quickly find the sum of stones in any range
piles[i:]. - The base case for the recursion is when
iis out of bounds, in which case the score is 0. - In the recursive function, iterate through all possible moves
X(from 1 to2*M). - For each move
X, the current player takesXpiles. The remaining piles are passed to the opponent. The opponent's score will besolve(i + X, max(M, X)). - The current player's score for this move is the total remaining stones (
suffixSum[i]) minus the opponent's score. - The function returns the maximum score found among all possible
Xvalues. - The initial call is
solve(0, 1).
Walkthrough
The core idea is to model the game as a recursive process. The state of the game can be uniquely identified by two parameters: i, the index of the first pile in the remaining sequence, and M, the value that constrains the number of piles a player can take.
We define a function solve(i, M) which calculates the maximum number of stones the current player can obtain starting from piles[i] with the given M.
Since this is a game where both players play optimally, we can use the minimax principle. The current player wants to maximize their score. This is equivalent to choosing a move that minimizes the maximum score the opponent can get from the subsequent state. The total number of stones from pile i onwards is fixed. Let's say this is total_remaining. If the current player makes a move and the opponent is guaranteed to get opponent_score from the remaining piles, the current player's final score will be total_remaining - opponent_score. To maximize their own score, the current player must choose a move that minimizes the opponent's score.
The recurrence relation is:
solve(i, M) = max over X { total_remaining_stones - solve(i + X, max(M, X)) }
where 1 <= X <= 2*M.
To avoid recomputing the sum of remaining piles repeatedly, we can pre-calculate a suffix sum array.
class Solution { int[] suffixSum; int n; public int stoneGameII(int[] piles) { this.n = piles.length; this.suffixSum = new int[n + 1]; for (int i = n - 1; i >= 0; i--) { suffixSum[i] = suffixSum[i + 1] + piles[i]; } return solve(0, 1); } private int solve(int i, int M) { if (i >= n) { return 0; } // Optimization: If the current player can take all remaining piles if (i + 2 * M >= n) { return suffixSum[i]; } int maxScore = 0; // Iterate through all possible moves X for (int X = 1; X <= 2 * M; X++) { // Opponent's score from the remaining piles int opponentScore = solve(i + X, Math.max(M, X)); // Current player's score for this move int currentScore = suffixSum[i] - opponentScore; maxScore = Math.max(maxScore, currentScore); } return maxScore; }}Complexity
Time
Exponential, roughly O(2^n). The recursion tree branches for each possible move, and subproblems are recomputed.
Space
O(n), for the recursion stack depth, where n is the number of piles.
Trade-offs
Pros
Simple to conceptualize and implement.
Directly models the turn-based nature of the game.
Cons
Extremely inefficient due to a large number of overlapping subproblems.
Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
This approach enhances the brute-force recursion by adding memoization, a technique also known as top-down dynamic programming. We store the results of solved subproblems (game states) in a cache or table. When the recursive function encounters a state it has seen before, it retrieves the result from the cache instead of recomputing it. This drastically reduces the number of calculations, pruning the recursion tree and making the solution efficient enough to pass within the given constraints.
Algorithm
- Use the same recursive structure as the brute-force approach.
- Introduce a 2D memoization table,
memo[i][M], to store the results ofsolve(i, M). - Before computing
solve(i, M), check if the result is already in the memoization table. If so, return the stored value. - If the result is not stored, compute it using the same recursive logic as the brute-force method.
- After computing the result, store it in
memo[i][M]before returning it. - The initial call remains
solve(0, 1).
Walkthrough
The state of the game is defined by (i, M). Since the brute-force approach recomputes the solution for the same state multiple times, we can optimize it by storing the results. We use a 2D array, memo[n+1][n+1], where memo[i][M] will store the result of solve(i, M).
The logic of the recursive function solve(i, M) remains the same, but with two additions:
- At the beginning of the function, we check if
memo[i][M]has been computed. If it has, we return the value immediately. - After computing the maximum score for the state
(i, M), we store it inmemo[i][M]before returning.
This ensures that each state (i, M) is solved only once. The number of states is determined by i (from 0 to n) and M (from 1 to n), giving O(n^2) unique states.
class Solution { int[] suffixSum; int[][] memo; int n; public int stoneGameII(int[] piles) { this.n = piles.length; this.suffixSum = new int[n + 1]; for (int i = n - 1; i >= 0; i--) { suffixSum[i] = suffixSum[i + 1] + piles[i]; } // A safe upper bound for M is n. Initialize with 0 as scores are positive. this.memo = new int[n + 1][n + 1]; return solve(0, 1); } private int solve(int i, int M) { if (i >= n) { return 0; } if (memo[i][M] != 0) { return memo[i][M]; } // Optimization: If the current player can take all remaining piles if (i + 2 * M >= n) { return memo[i][M] = suffixSum[i]; } int maxScore = 0; // Try all possible moves X for (int X = 1; X <= 2 * M; X++) { int opponentScore = solve(i + X, Math.max(M, X)); int currentScore = suffixSum[i] - opponentScore; maxScore = Math.max(maxScore, currentScore); } return memo[i][M] = maxScore; }}Complexity
Time
O(n^3). There are O(n^2) states, and each state computation involves a loop of up to O(n) iterations.
Space
O(n^2), for the memoization table and the recursion stack.
Trade-offs
Pros
Efficient enough for the given constraints.
Guarantees finding the optimal solution.
Often more intuitive to write than the bottom-up approach as it follows the logical flow of the game.
Cons
Uses O(n^2) space for the memoization table.
May have higher overhead than the bottom-up iterative approach due to recursion.
This approach, also known as bottom-up dynamic programming, solves the problem iteratively, eliminating recursion. We build a DP table that stores the solution for each subproblem. By filling the table in a specific order (from the end of the game to the beginning), we ensure that when we calculate the solution for a state, the solutions for all the subsequent states it depends on are already available. This method has the same time and space complexity as the memoization approach but can be slightly faster in practice due to the absence of recursion overhead.
Algorithm
- Create a 2D DP table,
dp[n+1][n+1], wheredp[i][M]stores the max stones the current player can get frompiles[i:]with valueM. - Pre-calculate the suffix sum array
suffixSum. - Iterate through the piles index
ifromn-1down to0. - For each
i, iterate throughMfrom1ton. - Inside the loops, calculate
dp[i][M]by trying all possible movesX(from 1 to2*M). - The score for a move
XissuffixSum[i] - dp[i + X][max(M, X)]. The valuedp[i + X][...]is already computed because we iterateibackwards. dp[i][M]is the maximum score over all possibleX.- The final answer is
dp[0][1].
Walkthrough
We can convert the top-down memoized recursion into an iterative solution. We'll use a 2D array dp[n+1][n+1] where dp[i][M] stores the maximum number of stones the current player can get starting from pile i with a given M.
The calculation for dp[i][M] depends on values dp[i+X][...], where X > 0. This dependency on states with a larger i suggests that we should fill our DP table by iterating i from n-1 down to 0.
The recurrence relation remains the same:
dp[i][M] = max_{1<=X<=2M} (suffixSum[i] - dp[i + X][max(M, X)])
We iterate through all states (i, M) and fill the dp table. The base cases dp[n][M] = 0 are handled by initializing the table with zeros.
class Solution { public int stoneGameII(int[] piles) { int n = piles.length; if (n == 0) { return 0; } int[] suffixSum = new int[n + 1]; for (int i = n - 1; i >= 0; i--) { suffixSum[i] = suffixSum[i + 1] + piles[i]; } int[][] dp = new int[n + 1][n + 1]; for (int i = n - 1; i >= 0; i--) { for (int M = 1; M <= n; M++) { // If the current player can take all remaining piles if (i + 2 * M >= n) { dp[i][M] = suffixSum[i]; continue; } int minOpponentScore = Integer.MAX_VALUE; // Try all possible moves X for (int X = 1; X <= 2 * M; X++) { // Opponent's score from the remaining piles // The state (i+X, max(M,X)) is already computed because i+X > i int opponentScore = dp[i + X][Math.max(M, X)]; minOpponentScore = Math.min(minOpponentScore, opponentScore); } dp[i][M] = suffixSum[i] - minOpponentScore; } } return dp[0][1]; }}Complexity
Time
O(n^3). We have three nested loops: `i` from `n` to `0`, `M` from `1` to `n`, and `X` from `1` to `2*M` (at most `2n`).
Space
O(n^2), for the 2D DP table.
Trade-offs
Pros
Highly efficient and guaranteed to be optimal.
Avoids recursion overhead, which can lead to a slight performance improvement over the top-down approach.
No risk of stack overflow for large inputs (though not an issue with n<=100).
Cons
Can be less intuitive to formulate than the recursive top-down approach.
Uses O(n^2) space, same as the memoization approach.
Solutions
Solution
class Solution {private int[] s;private Integer[][] f;private int n;public int stoneGameII(int[] piles) { n = piles.length; s = new int[n + 1]; f = new Integer[n][n + 1]; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + piles[i]; } return dfs(0, 1); }private int dfs(int i, int m) { if (m * 2 >= n - i) { return s[n] - s[i]; } if (f[i][m] != null) { return f[i][m]; } int res = 0; for (int x = 1; x <= m * 2; ++x) { res = Math.max(res, s[n] - s[i] - dfs(i + x, Math.max(m, x))); } return f[i][m] = res; }}class Solution {public: int stoneGameII(vector<int> &piles) { int n = piles.size(); int s[n + 1]; s[0] = 0; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + piles[i]; } int f[n][n + 1]; memset(f, 0, sizeof f); function<int(int, int)> dfs = [&](int i, int m) -> int { if (m * 2 >= n - i) { return s[n] - s[i]; } if (f[i][m]) { return f[i][m]; } int res = 0; for (int x = 1; x <= m << 1; ++x) { res = max(res, s[n] - s[i] - dfs(i + x, max(x, m))); } return f[i][m] = res; }; return dfs(0, 1); }};class Solution: def stoneGameII(self, piles: List[int]) -> int: @ cache def dfs(i, m): if m * 2 >= n - i: return s[n] - s[i] return max(s[n] - s[i] - dfs(i + x, max(m, x)) for x in range(1, m << 1 | 1)) n = len(piles) s = list(accumulate(piles, initial=0)) return dfs(0, 1)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.