{x}
blog image

Stone Game VIII

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, while the number of stones is more than one, they will do the following:

  1. Choose an integer x > 1, and remove the leftmost x stones from the row.
  2. Add the sum of the removed stones' values to the player's score.
  3. Place a new stone, whose value is equal to that sum, on the left side of the row.

The game stops when only one stone is left in the row.

The score difference between Alice and Bob is (Alice's score - Bob's score). Alice's goal is to maximize the score difference, and Bob's goal is the minimize the score difference.

Given an integer array stones of length n where stones[i] represents the value of the ith stone from the left, return the score difference between Alice and Bob if they both play optimally.

 

Example 1:

Input: stones = [-1,2,-3,4,-5]
Output: 5
Explanation:
- Alice removes the first 4 stones, adds (-1) + 2 + (-3) + 4 = 2 to her score, and places a stone of
  value 2 on the left. stones = [2,-5].
- Bob removes the first 2 stones, adds 2 + (-5) = -3 to his score, and places a stone of value -3 on
  the left. stones = [-3].
The difference between their scores is 2 - (-3) = 5.

Example 2:

Input: stones = [7,-6,5,10,5,-2,-6]
Output: 13
Explanation:
- Alice removes all stones, adds 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 to her score, and places a
  stone of value 13 on the left. stones = [13].
The difference between their scores is 13 - 0 = 13.

Example 3:

Input: stones = [-10,-12]
Output: -22
Explanation:
- Alice can only make one move, which is to remove both stones. She adds (-10) + (-12) = -22 to her
  score and places a stone of value -22 on the left. stones = [-22].
The difference between their scores is (-22) - 0 = -22.

 

Constraints:

  • n == stones.length
  • 2 <= n <= 105
  • -104 <= stones[i] <= 104

Solution Explanation for LeetCode 1872. Stone Game VIII

This problem involves a two-player game with optimal strategies. The core idea is to leverage dynamic programming or memoization to efficiently explore the decision tree of possible moves. The key observation is that the game's state can be effectively summarized using a prefix sum.

Approach: Dynamic Programming with Prefix Sum

  1. Prefix Sum: Calculate the prefix sum of the stones array. This allows us to quickly compute the sum of any contiguous subarray. The prefix sum array s where s[i] is the sum of stones[0...i].

  2. Dynamic Programming (or Memoization): We work backward from the end of the game.

    • Base Case: When only one stone remains (i == n - 1), the score difference is simply the value of that stone (s[n-1]).

    • Recursive Relation: For a given state with i stones remaining, the current player has two choices:

      • Take all remaining stones: The score difference is s[i] (the sum of all remaining stones) minus the score difference the other player will get in the next turn (which we'll already have calculated).
      • Take a subset of remaining stones: This is equivalent to recursively calling the function for a reduced number of remaining stones. This is where memoization helps avoid redundant calculations.

  3. Iteration: Instead of recursion (which can be less efficient due to function call overhead), we can iterate through the prefix sum array in reverse order to fill our DP table from the base case.

  4. Result: The final result is the maximum score difference Alice can achieve starting from the initial state.

Time and Space Complexity

  • Time Complexity: O(n), where n is the number of stones. We iterate through the prefix sum array once.
  • Space Complexity: O(1) for the iterative DP approach (or O(n) for the recursive approach with memoization, due to the memoization table).

Code Implementation (Python)

from itertools import accumulate
 
class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        n = len(stones)
        s = list(accumulate(stones))  # Prefix sum
        dp = s[-1] # Base case: only one stone left
 
        for i in range(n - 2, 0, -1):
            dp = max(dp, s[i] - dp) # DP relation
 
        return dp

Code Implementation (Java)

import java.util.Arrays;
 
class Solution {
    public int stoneGameVIII(int[] stones) {
        int n = stones.length;
        int[] prefixSum = new int[n];
        prefixSum[0] = stones[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + stones[i];
        }
        int dp = prefixSum[n - 1]; //Base case
        for (int i = n - 2; i > 0; i--) {
            dp = Math.max(dp, prefixSum[i] - dp); //DP relation
        }
        return dp;
    }
}

This iterative dynamic programming solution is highly efficient and avoids unnecessary recursion. The use of prefix sums makes the calculation of the score difference for any subset of stones very fast. The overall time complexity is linear, making it suitable for large input sizes.