Stone Game VII: Dynamic Programming on Subarrays

Alice and Bob take turns playing a game with a row of stones. Each stone has a positive integer value. On each turn, a player removes either the leftmost or rightmost stone. The player's score for that turn is the sum of the remaining stones after the removal. Alice goes first, and both players play optimally. Return the maximum difference in score that Alice can achieve over Bob.

This is LeetCode 1690: Stone Game VII, and it is one of the cleanest examples of interval dynamic programming applied to game theory. The pattern it teaches shows up whenever two players compete over a shrinking range of elements.

Why this problem matters

Game theory problems on arrays come up frequently in interviews, and they almost always reduce to interval DP. The idea is always the same: two players alternate turns, each choosing optimally, and you need to compute the outcome of perfect play. Stone Game VII adds a twist by scoring based on the remaining sum rather than the value of the stone you pick. This forces you to track prefix sums alongside your DP table.

Once you understand this pattern, you can apply the same framework to problems like "Stone Game" (LeetCode 877), "Stone Game II" (LeetCode 1140), "Predict the Winner" (LeetCode 486), and any problem where two players compete over a subarray.

The key insight

Define dp[i][j] as the maximum score difference the current player can achieve on the subarray stones[i..j]. On each turn, the current player can remove the left stone or the right stone. If they remove the left stone (stones[i]), they score the sum of stones[i+1..j], and then the opponent gets to play on that smaller subarray. If they remove the right stone (stones[j]), they score the sum of stones[i..j-1], and the opponent plays next.

The key is that the opponent's best result on the remaining subarray is subtracted from the current player's score. So the recurrence is:

• Remove left: sum(i+1, j) - dp[i+1][j]
• Remove right: sum(i, j-1) - dp[i][j-1]
• dp[i][j] = max(remove left, remove right)

The subtraction is what makes this elegant. Because both players use the same strategy (maximize their own advantage), the current player's net advantage is their immediate score minus whatever advantage the opponent will achieve on the remaining subarray.

Use a prefix sum array to compute sum(i, j) in O(1).

The solution

def stone_game_vii(stones: list[int]) -> int:
    n = len(stones)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + stones[i]

    def range_sum(i: int, j: int) -> int:
        return prefix[j + 1] - prefix[i]

    dp = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            remove_left = range_sum(i + 1, j) - dp[i + 1][j]
            remove_right = range_sum(i, j - 1) - dp[i][j - 1]
            dp[i][j] = max(remove_left, remove_right)

    return dp[0][n - 1]

The prefix sum array lets you compute the sum of any subarray in constant time. prefix[j + 1] - prefix[i] gives you the sum from index i to index j inclusive.

The DP table is filled bottom-up by subarray length. For length 1, dp[i][i] = 0 because when only one stone remains, the player who removes it scores 0 (no remaining stones). For each longer subarray, you try removing from the left or right and take the better option.

The subtraction - dp[i+1][j] accounts for the opponent playing optimally on the remaining subarray. Whatever advantage the opponent gains on the smaller subarray is subtracted from your advantage. This single line is what encodes the entire minimax logic without needing separate "maximizer" and "minimizer" branches.

Visual walkthrough

Let's trace through stones = [5, 3, 1, 6, 2, 4] to see how the game unfolds. Green highlights mark Alice's removals, and orange highlights mark Bob's.

Notice that Alice consistently tries to remove the stone that leaves the highest possible remaining sum, while Bob does the same. The DP solution evaluates every possible sequence of moves and finds the guaranteed optimal outcome. In this case, Alice can always achieve a difference of 12 with perfect play.

Complexity analysis

Time is O(n^2) because you fill a 2D DP table with entries for every pair (i, j) where i is at most j. There are roughly n^2 / 2 such pairs, and each takes O(1) work thanks to the prefix sum.

Space is O(n^2) for the DP table. You can optimize this to O(n) by noticing that each row of the DP table only depends on the row below it, but the O(n^2) version is clearer and sufficient for the constraint of n up to 1000.

The building blocks

1. Prefix sums for range queries

The foundation of this solution is computing subarray sums in O(1). You build a prefix sum array once, then answer any range query with a single subtraction.

prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + stones[i]

def range_sum(i: int, j: int) -> int:
    return prefix[j + 1] - prefix[i]

This is the same prefix sum technique you use in dozens of problems. The +1 offset avoids special-casing index 0. Once this is in place, you never need to loop over a subarray to compute its sum.

2. Interval DP with minimax

The core game theory pattern: define the DP over intervals, and encode the opponent's optimal play by subtracting the DP value of the smaller interval.

for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        remove_left = range_sum(i + 1, j) - dp[i + 1][j]
        remove_right = range_sum(i, j - 1) - dp[i][j - 1]
        dp[i][j] = max(remove_left, remove_right)

The outer loop iterates by subarray length, ensuring that smaller subproblems are solved before larger ones. The max chooses the better move for the current player. The subtraction of dp[i+1][j] or dp[i][j-1] accounts for the opponent playing just as smartly on the remaining subarray.

Edge cases

Before submitting, think through these scenarios:

• Two stones: The answer is abs(stones[0] - stones[1]). The first player removes the smaller stone to score the larger one, and the second player scores 0.
• All stones equal: Every move scores the same amount, so the answer is 0 because the players alternate and their scores cancel out.
• Stones sorted in ascending or descending order: The optimal strategy depends on whether the larger values cluster at one end. The DP handles this automatically.
• Single large stone surrounded by small ones: The player who removes the neighbor of the large stone forces the opponent into a worse position. Again, the DP handles this without special logic.
• n = 1: Not possible per the constraints (n is at least 2), but dp[0][0] = 0 would be correct since removing the only stone leaves nothing to score.

From understanding to recall

You now understand how interval DP encodes optimal play for two players on a subarray. The recurrence is short: compute the score for removing each end, subtract the opponent's best response, and take the maximum. The prefix sum handles range queries in O(1). The whole solution is roughly 15 lines of Python.

But reproducing those 15 lines under pressure is where most people struggle. Which index goes into the prefix sum? Is it prefix[j+1] - prefix[i] or prefix[j] - prefix[i-1]? Do you subtract dp[i+1][j] or add it? These small details are the difference between solving the problem in 10 minutes and staring at a whiteboard for 30.

Spaced repetition closes this gap. You write the prefix sum setup, the interval DP loop, and the minimax subtraction from memory. Each time you practice, the pattern gets faster and more automatic. After a few sessions, you see "game theory on subarrays" and the template flows out without hesitation.

Related posts

• House Robber - A foundational 1D DP problem that teaches optimal substructure on arrays
• Coin Change - Classic DP on values, building intuition for defining states and transitions
• Edit Distance - 2D DP on two sequences, showing how interval-style thinking extends to string problems

CodeBricks breaks Stone Game VII into its prefix sum and interval DP building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a game theory DP problem shows up in your interview, you do not think about it. You just write it.