Problem Description

Alice and Bob are playing a stone game where they take turns, with Alice going first.

The game setup:

• There are n stones arranged in a row, each with a value given by stones[i]
• On each turn, a player can remove either the leftmost or rightmost stone from the row
• When a player removes a stone, they receive points equal to the sum of all remaining stones' values
• The game continues until all stones are removed

The scoring works like this: If a player removes a stone when there are other stones left, their score increases by the sum of those remaining stones. For example, if stones are [5, 3, 1, 4] and a player removes the leftmost stone (5), they get 3 + 1 + 4 = 8 points.

Both players play optimally, but with different objectives:

• Alice wants to maximize the score difference (her score minus Bob's score)
• Bob wants to minimize the score difference (since he knows he'll lose, he wants to lose by as little as possible)

Given an array stones where stones[i] represents the value of the i-th stone from the left, you need to return the difference between Alice's and Bob's scores when both play optimally.

For example, if stones = [5, 3, 1, 4, 2]:

• The game might proceed with players strategically choosing which stones to remove
• Each choice affects not only their own score but also limits the opponent's future options
• The final result would be the difference: (Alice's total score) - (Bob's total score)

Intuition

When thinking about this game, we need to consider that both players are playing optimally but with opposing goals. This is a classic game theory problem where we need to think recursively about the best moves.

The key insight is that at any state of the game, we can represent it by which stones remain. If stones from index i to j are still in the row, the current player needs to decide whether to take the leftmost stone at index i or the rightmost stone at index j.

When a player removes a stone, they score points equal to the sum of the remaining stones. This means if we remove stone at index i, we get the sum of stones from i+1 to j. If we remove stone at index j, we get the sum of stones from i to j-1. We can efficiently calculate these sums using a prefix sum array.

The crucial realization is that this is a zero-sum game - one player's gain is the other player's loss. After a player makes their move and scores some points, the game state changes and it becomes the opponent's turn. The opponent will then try to maximize their own advantage from that new state.

This leads us to think about the problem recursively: for any game state (i, j), we want to find the maximum score difference the current player can achieve. When the current player takes a stone and scores some points, they add those points to their score, but then the opponent plays optimally from the resulting state. So the score difference is:

• Points gained from this move
• Minus the best score difference the opponent can achieve from the resulting state

Since the opponent is also trying to maximize their own score difference from their perspective, we need to subtract their optimal result from our gain. This gives us the recurrence relation where dfs(i, j) represents the maximum score difference the current player can achieve when stones from index i to j remain.

The base case is when i > j, meaning no stones are left, so the score difference is 0.

To avoid recalculating the same game states multiple times, we use memoization to cache the results of each (i, j) state we compute.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming with memoization to solve this game theory problem. Here's how the implementation works:

Step 1: Prefix Sum Calculation

First, we create a prefix sum array s using accumulate(stones, initial=0). This gives us:

• s[0] = 0
• s[i] = stones[0] + stones[1] + ... + stones[i-1]

This allows us to calculate the sum of any subarray in O(1) time. For stones from index i to j, the sum is s[j+1] - s[i].

Step 2: Recursive Function with Memoization

We define dfs(i, j) to represent the maximum score difference the current player can achieve when stones from index i to j remain.

The function works as follows:

• Base Case: If i > j, there are no stones left, so return 0.

• Recursive Case: The current player has two choices:

  1. Remove the leftmost stone (at index i):

     • The player scores s[j+1] - s[i+1] (sum of stones from i+1 to j)
     • The game continues with stones from i+1 to j, where the opponent plays
     • The score difference becomes: s[j+1] - s[i+1] - dfs(i+1, j)
     • We subtract dfs(i+1, j) because the opponent will maximize their own score difference from that state

  2. Remove the rightmost stone (at index j):

     • The player scores s[j] - s[i] (sum of stones from i to j-1)
     • The game continues with stones from i to j-1
     • The score difference becomes: s[j] - s[i] - dfs(i, j-1)

• The player chooses the option that maximizes their score difference: max(a, b)

Step 3: Memoization with @cache

The @cache decorator automatically memoizes the function results, preventing redundant calculations for the same (i, j) pairs. This reduces the time complexity from exponential to O(n²).

Step 4: Final Answer

We call dfs(0, len(stones) - 1) to get the maximum score difference when starting with all stones. After getting the result, we clear the cache with dfs.cache_clear() to free memory.

The time complexity is O(n²) because we have at most n² unique states (i, j), and each state is computed once. The space complexity is also O(n²) for storing the memoization cache.

Example Walkthrough

Let's walk through a small example with stones = [3, 7, 2] to illustrate how the solution works.

Initial Setup:

• Prefix sum array: s = [0, 3, 10, 12]
  • s[0] = 0
  • s[1] = 3
  • s[2] = 3 + 7 = 10
  • s[3] = 3 + 7 + 2 = 12

Game Tree (Alice starts first):

We need to compute dfs(0, 2) - the maximum score difference when all stones are available.

Computing dfs(0, 2): Alice has two choices:

1. Remove left stone (value 3):

   • Alice scores: s[3] - s[1] = 12 - 3 = 9 (sum of remaining stones [7, 2])
   • Game continues with dfs(1, 2) (Bob's turn)
   • Score difference: 9 - dfs(1, 2)

2. Remove right stone (value 2):

   • Alice scores: s[2] - s[0] = 10 - 0 = 10 (sum of remaining stones [3, 7])
   • Game continues with dfs(0, 1) (Bob's turn)
   • Score difference: 10 - dfs(0, 1)

Computing dfs(1, 2): Bob has two choices with stones [7, 2]:

1. Remove left stone (value 7):

   • Bob scores: s[3] - s[2] = 12 - 10 = 2 (sum of remaining stone [2])
   • Game continues with dfs(2, 2) (Alice's turn)
   • Score difference: 2 - dfs(2, 2)

2. Remove right stone (value 2):

   • Bob scores: s[2] - s[1] = 10 - 3 = 7 (sum of remaining stone [7])
   • Game continues with dfs(1, 1) (Alice's turn)
   • Score difference: 7 - dfs(1, 1)

Computing dfs(2, 2): Only stone at index 2 remains:

• Remove it: score = s[3] - s[3] = 0 (no other stones left)
• Result: 0 - dfs(3, 2) = 0 - 0 = 0

Computing dfs(1, 1): Only stone at index 1 remains:

• Remove it: score = s[2] - s[2] = 0 (no other stones left)
• Result: 0 - dfs(2, 1) = 0 - 0 = 0

Back to dfs(1, 2):

• Option 1: 2 - 0 = 2
• Option 2: 7 - 0 = 7
• Bob chooses max: dfs(1, 2) = 7

Computing dfs(0, 1): Bob has two choices with stones [3, 7]:

1. Remove left stone (value 3): scores 7, then dfs(1, 1) = 0, difference = 7 - 0 = 7
2. Remove right stone (value 7): scores 3, then dfs(0, 0) = 0, difference = 3 - 0 = 3

• Bob chooses max: dfs(0, 1) = 7

Final computation of dfs(0, 2):

• Option 1: 9 - 7 = 2
• Option 2: 10 - 7 = 3
• Alice chooses max: dfs(0, 2) = 3

Result: The maximum score difference Alice can achieve is 3.

Verification: If Alice removes the right stone first (optimal play):

• Alice scores 10 (removes stone 2, gets sum of [3,7])
• Bob scores 7 (removes stone 7, gets sum of [3])
• Alice scores 0 (removes stone 3, no stones left)
• Total: Alice = 10, Bob = 7, Difference = 3 ✓

Solution Implementation

Time and Space Complexity

The time complexity of this code is O(n^2), where n is the number of stones.

The recursive function dfs(i, j) explores all possible subarray ranges [i, j] of the stones array. Since i can range from 0 to n-1 and j can range from 0 to n-1 with the constraint i <= j, there are approximately n^2/2 unique states. Due to the @cache decorator, each state is computed only once. The work done per state is O(1) (calculating prefix sums and making recursive calls that are already cached). Therefore, the overall time complexity is O(n^2).

The space complexity is O(n^2). This comes from two sources:

1. The memoization cache stores the result for each unique (i, j) pair, which requires O(n^2) space
2. The recursion stack depth in the worst case is O(n) when we recursively remove stones one by one
3. The prefix sum array s takes O(n) space

Since O(n^2) dominates, the total space complexity is O(n^2).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Score Calculation - Using Stone Value Instead of Remaining Sum

A very common mistake is misunderstanding how scoring works in this problem. Many people incorrectly assume that when you remove a stone, you get points equal to that stone's value.

Wrong Understanding:

# INCORRECT: Thinking you score the value of the removed stone
score_when_removing_left = stones[i] - dfs(i+1, j)
score_when_removing_right = stones[j] - dfs(i, j-1)

Correct Understanding:

# CORRECT: You score the sum of ALL REMAINING stones after removal
score_when_removing_left = sum(stones[i+1:j+1]) - dfs(i+1, j)
score_when_removing_right = sum(stones[i:j]) - dfs(i, j-1)

The problem states: "When a player removes a stone, they receive points equal to the sum of all remaining stones' values." This means if you remove a stone, you DON'T get that stone's value - you get the sum of everything else that's left.

2. Inefficient Sum Calculation Without Prefix Sums

Computing the sum of remaining stones repeatedly leads to O(n³) time complexity:

Inefficient Approach:

def dfs(i, j):
    if i > j:
        return 0
  
    # O(n) operation for each recursive call
    remove_left_score = sum(stones[i+1:j+1]) - dfs(i+1, j)
    remove_right_score = sum(stones[i:j]) - dfs(i, j-1)
  
    return max(remove_left_score, remove_right_score)

Efficient Solution with Prefix Sums:

# Precompute prefix sums once
prefix_sum = list(accumulate(stones, initial=0))

def dfs(i, j):
    if i > j:
        return 0
  
    # O(1) operation using prefix sums
    remove_left_score = prefix_sum[j+1] - prefix_sum[i+1] - dfs(i+1, j)
    remove_right_score = prefix_sum[j] - prefix_sum[i] - dfs(i, j-1)
  
    return max(remove_left_score, remove_right_score)

3. Confusing Score Difference with Individual Scores

Another pitfall is trying to track Alice's and Bob's individual scores separately, rather than working with the score difference directly.

Overcomplicated Approach:

def dfs(i, j, is_alice_turn):
    if i > j:
        return (0, 0)  # (alice_score, bob_score)
  
    if is_alice_turn:
        # Calculate Alice's best move...
        alice_score, bob_score = ...
    else:
        # Calculate Bob's best move...
        alice_score, bob_score = ...
  
    return (alice_score, bob_score)

Cleaner Difference-Based Approach:

def dfs(i, j):
    # Returns the maximum score difference the current player can achieve
    if i > j:
        return 0
  
    # Each player maximizes their own score difference
    return max(
        score_from_left - dfs(i+1, j),
        score_from_right - dfs(i, j-1)
    )

The key insight is that both players use the same strategy: maximize their own score minus opponent's score. This allows us to use a single recursive function without tracking whose turn it is.

4. Forgetting to Clear Cache (Memory Leak in Multiple Test Cases)

When using @cache decorator in platforms that run multiple test cases, forgetting to clear the cache can cause memory issues:

# Without cache clearing - potential memory leak
def stoneGameVII(self, stones):
    @cache
    def dfs(i, j):
        # ... implementation ...
  
    return dfs(0, len(stones) - 1)
    # Cache persists across test cases!

# With proper cache clearing
def stoneGameVII(self, stones):
    @cache
    def dfs(i, j):
        # ... implementation ...
  
    result = dfs(0, len(stones) - 1)
    dfs.cache_clear()  # Important for multiple test cases
    return result