#1872

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Stone Game VIII

Stone Game VIII requires calculating maximum score difference using state transition dynamic programming on prefix sums of stones.

array math dynamic programming prefix sum game theory

Problem Statement

Alice and Bob play a turn-based game with a row of stones. On each turn, a player removes at least two stones from the left, sums their values, and places a new stone equal to that sum on the left. Alice moves first, and the game ends when only one stone remains.

Given an array of integers stones representing the stone values, compute the maximum possible difference between Alice's and Bob's scores assuming both play optimally. The constraints are 2 <= stones.length <= 10^5 and -10^4 <= stones[i] <= 10^4.

Examples

Example 1

Input: stones = [-1,2,-3,4,-5]

Output: 5

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

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

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 Approach

Use prefix sums to preprocess moves

Compute prefix sums of stones so any sum of the first k stones can be retrieved in O(1). This allows calculating the resulting new stone value efficiently for each possible removal move.

State transition dynamic programming

Define dp[i] as the maximum score difference starting with the first i stones removed. Use the recurrence dp[i] = max(dp[i-1], prefixSum[i] - dp[i-1]) to consider keeping the previous optimal or taking the new move. Iterate from i = 2 to n.

Optimize using linear scan

Scan the stones array once while maintaining the dp values in a single pass. No nested loops are needed because the recurrence only depends on the previous dp state, keeping time complexity linear.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) due to single pass DP using prefix sums. Space complexity is O(n) if storing full DP array or O(1) if optimized to keep only previous state.

What Interviewers Usually Probe

Expecting prefix sum usage for move sums
Checking understanding of state transition DP
Looking for handling large n efficiently without nested loops

Common Pitfalls or Variants

Common pitfalls

Ignoring that at least two stones must be removed per move
Incorrectly tracking score difference instead of individual scores
Recomputing prefix sums in inner loops causing TLE

Follow-up variants

Changing score function to product instead of sum
Allowing removal of exactly k stones instead of at least two
Scoring based on alternating stone positions rather than prefix sums

FAQ

What is the main pattern in Stone Game VIII?

State transition dynamic programming using prefix sums is the key pattern to compute optimal score difference.

Can Stone Game VIII be solved without prefix sums?

Technically yes, but recomputing sums repeatedly would be inefficient and likely cause TLE for large n.

Why must at least two stones be removed each turn?

This rule ensures the new stone value is meaningful and prevents trivial moves that break the DP recurrence.

What is the optimal way to track DP states?

Maintain dp[i] representing the maximum difference after removing i stones, updating with dp[i] = max(dp[i-1], prefixSum[i] - dp[i-1]).

How does GhostInterview assist for this problem?

It guides solving Stone Game VIII by enforcing correct DP state updates, prefix sum usage, and avoiding common calculation pitfalls.

terminal

Solution

Solution 1: Prefix Sum + Memoization Search

According to the problem description, each time we take the leftmost $x$ stones, add their sum to our score, and then put a stone with this sum value on the leftmost side, it is equivalent to merging these $x$ stones into a stone with this sum value, and the prefix sum remains unchanged.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(stones) - 1:
                return s[-1]
            return max(dfs(i + 1), s[i] - dfs(i + 1))

        s = list(accumulate(stones))
        return dfs(1)

Solution 2: Prefix Sum + Dynamic Programming

We can also use dynamic programming to solve this problem.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(stones) - 1:
                return s[-1]
            return max(dfs(i + 1), s[i] - dfs(i + 1))

        s = list(accumulate(stones))
        return dfs(1)

Continue Practicing

#1140 stone game ii #1728 cat and mouse ii #1690 stone game vii