Stone Game II

Difficulty: Medium Source: NeetCode

Problem

Alice and Bob continue the stone game. The piles are in a row and players alternate turns. On each turn, the current player can take the first X piles where 1 <= X <= 2 * M. After taking, M = max(M, X) for the next turn. Alice goes first with M = 1. Return the maximum number of stones Alice can get.

Example 1: Input: piles = [2, 7, 9, 4, 4] Output: 10

Example 2: Input: piles = [1, 2, 3, 4, 5] Output: 9

Constraints:

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 10^4

Prerequisites

Before attempting this problem, you should be comfortable with:

• Stone Game (877) — simpler version of the same game
• Suffix sums — quickly computing the sum of remaining piles
• Interval/parametric DP — state includes both index and parameter M

1. Brute Force / Recursive

Intuition

At each turn, the current player can take X piles (from 1 to 2M) from the front. After taking, M updates. We track position i and current M. The current player maximises their take; the opponent will do the same. Since both play optimally, the current player gets suffix_sum[i] - opponent_best, where opponent_best is what the opponent collects playing optimally on the rest.

Algorithm

1. Precompute suffix sums.
2. Define dfs(i, M) = max stones the current player can collect starting at index i with parameter M.
3. If i + 2*M >= n, current player takes all remaining piles.
4. Otherwise, try each X from 1 to 2*M; new M' = max(M, X). Opponent plays dfs(i+X, M'). Current player gets suffix[i] - dfs(i+X, M').
5. Return the maximum.

Solution

def stoneGameII(piles):
    n = len(piles)
    suffix = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix[i] = suffix[i + 1] + piles[i]

    def dfs(i, M):
        if i >= n:
            return 0
        if i + 2 * M >= n:
            return suffix[i]  # take all remaining
        best = 0
        for X in range(1, 2 * M + 1):
            new_M = max(M, X)
            opponent = dfs(i + X, new_M)
            best = max(best, suffix[i] - opponent)
        return best

    return dfs(0, 1)


print(stoneGameII([2, 7, 9, 4, 4]))  # 10
print(stoneGameII([1, 2, 3, 4, 5]))  # 9

Complexity

• Time: O(n³) — exponential states without memoization
• Space: O(n) — recursion depth

2. Top-Down DP (Memoization)

Intuition

The same recursive idea, but we cache (i, M) pairs. Since i ranges from 0 to n and M ranges from 1 to n, the table is at most n² states. Each state does O(n) work in the worst case, giving O(n³) total.

Algorithm

1. Same as brute force but wrap in @lru_cache.

Solution

from functools import lru_cache

def stoneGameII(piles):
    n = len(piles)
    suffix = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix[i] = suffix[i + 1] + piles[i]

    @lru_cache(maxsize=None)
    def dfs(i, M):
        if i >= n:
            return 0
        if i + 2 * M >= n:
            return suffix[i]
        best = 0
        for X in range(1, 2 * M + 1):
            new_M = max(M, X)
            opponent = dfs(i + X, new_M)
            best = max(best, suffix[i] - opponent)
        return best

    return dfs(0, 1)


print(stoneGameII([2, 7, 9, 4, 4]))  # 10
print(stoneGameII([1, 2, 3, 4, 5]))  # 9
print(stoneGameII([1]))              # 1


# Bottom-up version
def stoneGameII_bu(piles):
    n = len(piles)
    suffix = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix[i] = suffix[i + 1] + piles[i]

    dp = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(n - 1, -1, -1):
        for M in range(1, n + 1):
            if i + 2 * M >= n:
                dp[i][M] = suffix[i]
            else:
                for X in range(1, 2 * M + 1):
                    new_M = max(M, X)
                    dp[i][M] = max(dp[i][M], suffix[i] - dp[i + X][new_M])

    return dp[0][1]


print(stoneGameII_bu([2, 7, 9, 4, 4]))  # 10
print(stoneGameII_bu([1, 2, 3, 4, 5]))  # 9

Complexity

• Time: O(n³)
• Space: O(n²)

Common Pitfalls

Forgetting the “take all remaining” base case. When i + 2*M >= n, the current player can take everything left. Don’t let your recursion fall through to dfs(i+X, ...) for values of X that overshoot the array.

Not using suffix sums. Computing sum(piles[i:]) inside the recursion makes it O(n⁴). Pre-compute suffix sums to keep it O(n³).

Updating M incorrectly. M becomes max(M, X) after the take, not just X. If you always set M = X, you may undercount the options available to the next player.