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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Stone Game II

Difficulty: Medium

Problem Description

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.

Key Insights

  • Players can take between 1 and 2M piles of stones on their turn.
  • The value of M increases as players take more piles, allowing for larger moves in subsequent turns.
  • The game alternates between Alice and Bob, requiring a strategy to maximize the total stones collected for Alice, while minimizing the stones collected by Bob.
  • Dynamic programming can be used to calculate the maximum stones Alice can collect based on different choices made at each turn.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

The solution can be approached using dynamic programming. We maintain a 2D array dp where dp[i][m] represents the maximum stones Alice can collect starting from pile i with the current maximum take m.

  1. Initialize the dp array to store results for subproblems.
  2. Use a prefix sum array to quickly compute the total number of stones in any segment of piles.
  3. Iterate through the piles and update the dp table based on the possible moves Alice can make.
  4. Alice's optimal strategy will consider the consequences of Bob's optimal responses after her choices.
  5. The final answer will be found in dp[0][1], representing the maximum stones Alice can collect starting from the first pile with M initialized to 1.

Code Solutions

def stoneGameII(piles):
    n = len(piles)
    dp = [[0] * (n + 1) for _ in range(n)]
    prefix_sum = [0] * (n + 1)

    for i in range(n - 1, -1, -1):
        prefix_sum[i] = prefix_sum[i + 1] + piles[i]

    for i in range(n):
        for m in range(1, n + 1):
            max_stones = 0
            for x in range(1, 2 * m + 1):
                if i + x <= n:
                    max_stones = max(max_stones, prefix_sum[i] - dp[i + x][max(m, x)])
            dp[i][m] = max_stones

    return dp[0][1]
← Back to All Questions