Stone Game VII

Stone Game VII

What is this problem about?

Stone Game VII involves an array of stones. In each turn, a player removes either the first or the last stone and receives points equal to the sum of the remaining stones. Alice wants to maximize the difference between her score and Bob's score, and Bob wants to minimize it.

Why is this asked in interviews?

Google and Dunzo ask this to assess your skills in Dynamic Programming and the use of Prefix Sums to optimize range queries. It's a "Medium" difficulty problem that requires you to correctly define a minimax recursive relationship and handle the state transitions efficiently.

Algorithmic pattern used

The Algorithmic pattern used is Interval Dynamic Programming.

• State: dp[i][j] is the maximum relative score the current player can get from the subarray piles[i...j].
• Transition: A player can remove piles[i] (getting sum(i+1, j) - dp[i+1][j]) or remove piles[j] (getting sum(i, j-1) - dp[i][j-1]).
• Optimization: Use a Prefix Sum array to calculate the sum of the remaining stones in $O(1)$ time.

Example explanation (use your own example)

Piles: [5, 3, 1, 4, 2].

• Alice can remove 5 (gets $3+1+4+2 = 10$ points) or remove 2 (gets $5+3+1+4 = 13$ points).
• If she takes 2, Bob is left with [5, 3, 1, 4]. He will then make a move to maximize his own score (which minimizes the difference for Alice).
• By using DP, we calculate the best possible relative score for every possible subarray, starting from those of length 2 and building up to the full array.

Common mistakes candidates make

• Wait, how many stones? Forgetting that the score is the sum of the remaining stones, not the one you picked.
• Space complexity: Using an $O(N^2)$ DP table when $N$ is 1000 is fine, but for larger $N$, you might need to optimize to $O(N)$ space.
• Redundant sums: Calculating the sum of a range using a loop inside the DP transition, which makes the overall complexity $O(N^3)$.
• Base case: Not realizing that for a single stone, the score gained is 0 (as no stones remain).

Interview preparation tip

This is a standard "minimax" problem. The core formula score_now - best_future_score_of_opponent is a common pattern for zero-sum games where the goal is to maximize a difference.