We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Stone Game II

Number: 1240

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Meta, Uber, Bloomberg

Problem Description

Alice and Bob play a game with a row of stone piles. Each pile has a positive number of stones. Starting with M = 1, on a player’s turn they can take all stones from the first X remaining piles (1 <= X <= 2M), and then update M to max(M, X). The players take turns until all the stones are taken, and both play optimally. The goal is to determine the maximum number of stones Alice can get.

Key Insights

  • Use dynamic programming to simulate the game state; define dp(i, m) as the maximum stones the current player can obtain starting from index i with the current limit m.
  • Precompute suffix sums so that the total stones from index i to the end can be retrieved in O(1).
  • The recurrence is based on the observation that while the current player takes X piles, the opponent then gets dp(i+X, max(m, X)). Thus, the current player’s net gain is suffix[i] - dp(i+X, max(m, X)).
  • Iterate over all allowed moves (X from 1 to min(2*m, n-i)) and choose the move that maximizes the current player's stones.
  • Memoization is crucial to avoid recomputation as the state is defined by two parameters (current index and current M).

Space and Time Complexity

Time Complexity: O(n^3) in the worst-case scenario where n is the number of piles (n ≤ 100), since for each state (O(n^2) states) we might iterate over up to O(n) moves. Space Complexity: O(n^2) for the memoization table.

Solution

We solve the problem using recursion with memoization. The main idea is to compute dp(i, m), representing the maximum stones a player can obtain starting from index i when she is allowed to take up to 2*m piles. We precompute suffix sums to quickly get the sum of stones from any index to the end. For every valid move (taking X piles), the current player's gain will be the total stones from index i (i.e., suffix[i]) minus the optimal result from the opponent (dp(i+X, max(m, X))). The final answer is then represented by dp(0, 1). This approach uses a top-down dynamic programming strategy with caching.

Code Solutions

# Function to compute maximum stones for Alice using recursion with memoization.
def stoneGameII(piles):
    n = len(piles)
    
    # Precompute suffix sums: suffix[i] = sum(piles[i] ... piles[n-1])
    suffix = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix[i] = piles[i] + suffix[i + 1]
    
    # Memoization dictionary: key is (i, m) and value is maximum stones current player can get.
    memo = {}
    
    # dp(i, m): maximum stones for current player starting at index i with limit m.
    def dp(i, m):
        # Base case: No more piles left.
        if i >= n:
            return 0
        # If remaining piles can all be taken.
        if 2 * m >= n - i:
            return suffix[i]
        if (i, m) in memo:
            return memo[(i, m)]
        
        best = 0
        # Try all possible moves (take X piles)
        for x in range(1, min(2 * m, n - i) + 1):
            # The opponent's best result when we take x piles
            opponent = dp(i + x, max(m, x))
            # Current player's best gain is total remaining minus opponent's gain.
            best = max(best, suffix[i] - opponent)
        memo[(i, m)] = best
        return best
    
    return dp(0, 1)

# Example usage:
# piles = [2,7,9,4,4]
# print(stoneGameII(piles))  # Output: 10
← Back to All Questions