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 VII

Number: 1808

Difficulty: Medium

Paid? No

Companies: Dunzo

Problem Description

Alice and Bob play a turn-based game on a row of stones, where each stone has a positive integer value. On each turn, a player removes either the leftmost or rightmost stone and scores points equal to the sum of the remaining stones. Alice starts first and aims to maximize the difference between her score and Bob's, while Bob plays optimally to minimize that difference. The task is to determine the final difference in scores if both play optimally.

Key Insights

  • This is a two-player turn-based game and can be modeled as a minimax problem.
  • Dynamic Programming (DP) is useful since the game has overlapping subproblems.
  • Use a DP table dp[l][r] representing the maximum score difference the current player can achieve with stones from l to r.
  • Precompute prefix sums to efficiently calculate the sum of stones in any interval.
  • The recurrence is based on the fact that if a player removes a stone from one end, the score they gain is the sum of the remaining stones minus the optimal outcome of the opponent’s play.
  • The final answer is dp[0][n-1].

Space and Time Complexity

Time Complexity: O(n^2) because we fill an n x n DP table with each cell computed in constant time. Space Complexity: O(n^2) for the DP table and O(n) for the prefix sum array.

Solution

We approach the problem using Dynamic Programming along with a prefix sum array to enable quick range sum queries. The DP state dp[l][r] represents the best score difference the current player can achieve using the subarray of stones from index l to r. For any subarray [l, r], the player can remove the left stone or the right stone. Removing one stone gives a gain equal to the sum of the remaining stones. However, since the opponent plays optimally next, we subtract the opponent's eventual benefit from this immediate gain. Therefore, the recurrence is defined as:

  • If the left stone is removed: gain = (sum of stones from l+1 to r) - dp[l+1][r]
  • If the right stone is removed: gain = (sum of stones from l to r-1) - dp[l][r-1] The optimal play is determined by taking the maximum of these two choices. We fill our DP table from smaller subproblems (shorter intervals) to larger ones, with the answer being in dp[0][n-1].

Code Solutions

# Python implementation for Stone Game VII

def stoneGameVII(stones):
    n = len(stones)
    # Precompute prefix sums: prefix[i] = sum of stones[0] to stones[i-1]
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + stones[i]
    
    # dp[l][r] represents the max difference the current player can obtain 
    # from stones[l] to stones[r]
    dp = [[0] * n for _ in range(n)]
    
    # Fill dp table from smaller intervals to larger ones.
    for length in range(2, n+1):  # length is current interval length
        for l in range(0, n-length+1):
            r = l + length - 1
            # Total sum for stones[l:r+1] is prefix[r+1] - prefix[l]
            # If the player removes the left stone:
            remove_left = (prefix[r+1] - prefix[l+1]) - dp[l+1][r]
            # If the player removes the right stone:
            remove_right = (prefix[r] - prefix[l]) - dp[l][r-1]
            dp[l][r] = max(remove_left, remove_right)
    return dp[0][n-1]

# Example usage:
print(stoneGameVII([5, 3, 1, 4, 2]))  # Expected output: 6
← Back to All Questions