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 VIII

Number: 2002

Difficulty: Hard

Paid? No

Companies: Infosys

Problem Description

Given an array of integers representing the values of stones arranged in a row, two players (Alice and Bob) take turns removing a number of stones from the left. On each turn the current player must remove more than one stone (i.e. choose an integer x > 1), add the sum of those removed stones to his/her score, and then place a new stone with that summed value at the beginning of the row. The game stops when only one stone remains. Both players play optimally: Alice maximizes the final difference (Alice’s score minus Bob’s score) and Bob minimizes it. Return the optimal score difference after all moves have been made.

Key Insights

  • The game has an optimal substructure and can be solved using dynamic programming.
  • Precompute the prefix sum array, where prefixSum[i] is the sum of the first (i+1) stones.
  • Define a DP state such that dp[i] represents the maximum score difference that the current player can achieve given that the first (i+1) stones (from the original stones array) have been “formed” into one composite game state.
  • The recurrence relation can be derived from the idea that from position i, a player can choose to remove stones so that his gain is prefixSum[i] and then the opponent will get dp[i+1]. Hence, the recurrence is: • dp[i] = max(prefixSum[i] - dp[i+1], dp[i+1])
  • Note that the game is “forced” to start from index 1 (i.e. the first move by Alice always removes at least 2 stones) so the answer is dp[1].
  • Reverse-order (backward) DP is used since the decision at each “state” depends on the state resulting from taking further moves.

Space and Time Complexity

Time Complexity: O(n) – We iterate over the stones array once to compute the prefix sum and then once more for the DP. Space Complexity: O(n) – Additional space is used for the prefix sum and DP arrays. (This can be optimized to O(1) if only the next DP value is stored.)

Solution

We first compute the prefix sum array for the original stones array. Let prefixSum[i] be the sum of stones from index 0 to i. Then we define a DP array where dp[i] represents the maximum score difference the current player can achieve when the game state is defined by the prefix sum up to index i. The recurrence is defined as:   dp[i] = max(prefixSum[i] - dp[i+1], dp[i+1]) for i from n-2 downto 1, and the base case is dp[n-1] = prefixSum[n-1] (i.e. when there are only two stones left to process a move). Finally, the answer is dp[1] because Alice’s first move must remove at least 2 stones.
The key trick is to realize that at every move, the player’s gain is the sum of the removed stones (obtained from the prefix sum) minus the optimal outcome for the opponent in the remaining state.

Code Solutions

# Python solution with detailed comments.
class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        n = len(stones)
        # Compute prefix sum: prefix_sum[i] is sum of stones[0] to stones[i]
        prefix_sum = [0] * n
        prefix_sum[0] = stones[0]
        for i in range(1, n):
            prefix_sum[i] = prefix_sum[i-1] + stones[i]
        
        # dp[i] represents the maximum score difference achievable from state i,
        # where the state is defined by the prefix sum array starting at index i.
        dp = [0] * n
        # Base: When there is only one stone left, no move is possible.
        # However, since a move must remove at least two stones,
        # the base state is at index n-1 (the last prefix sum).
        dp[n-1] = prefix_sum[n-1]
        
        # Fill dp array backwards starting from the second last index.
        for i in range(n-2, 0, -1):
            # Option 1: Remove stones making current score "prefix_sum[i]"
            # and leave opponent with state dp[i+1].
            # Option 2: Skip making a move here if it is less beneficial,
            # which is represented by dp[i+1].
            dp[i] = max(prefix_sum[i] - dp[i+1], dp[i+1])
        
        # The answer is dp[1] because the first move must remove at least 2 stones.
        return dp[1]
← Back to All Questions