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 VII

Difficulty: Medium

Problem Description

Alice and Bob take turns playing a game, with Alice starting first. There are n stones arranged in a row. On each player's turn, they can remove either the leftmost stone or the rightmost stone from the row and receive points equal to the sum of the remaining stones' values in the row. The winner is the one with the higher score when there are no stones left to remove. Bob found that he will always lose this game, so he decided to minimize the score's difference. Alice's goal is to maximize the difference in the score. Given an array of integers stones where stones[i] represents the value of the i-th stone from the left, return the difference in Alice and Bob's score if they both play optimally.

Key Insights

  • Alice aims to maximize the score difference, while Bob aims to minimize it.
  • The choice of removing either the leftmost or rightmost stone affects the total score for both players.
  • The game is optimal; thus, a dynamic programming approach can be used to calculate the best possible outcomes for both players based on their choices.
  • The accumulated score can be efficiently computed using prefix sums.

Space and Time Complexity

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

Solution

To solve the problem, we can use dynamic programming. We define a 2D array dp where dp[i][j] represents the maximum score difference Alice can achieve over Bob when considering the stones from index i to j. The goal is to fill this table based on which stone (leftmost or rightmost) Alice decides to remove.

  1. Calculate the total sum of all stones.
  2. Initialize a 2D array dp with dimensions n x n to store maximum differences.
  3. Iterate through all possible lengths of the stone segments and fill the dp table:
    • For each segment, calculate the score difference based on Alice's choice of removing either the leftmost or rightmost stone.
  4. The score difference for the whole array (0 to n-1) will be found in dp[0][n-1].

The final difference can be derived from the total score and dp[0][n-1].

Code Solutions

def stoneGameVII(stones):
    n = len(stones)
    total_sum = sum(stones)
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n + 1):  # length of the current segment
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(total_sum - stones[i] - dp[i + 1][j],
                           total_sum - stones[j] - dp[i][j - 1])
    
    return dp[0][n - 1]
← Back to All Questions