Stone Game V: Interval DP with Prefix Sums

There are several stones in a row, and each stone has a value given in the array stoneValue. Alice and Bob play a game. On each round, Alice splits the remaining stones into two non-empty groups by choosing any split point. The group with the larger total value gets thrown away. If the two groups have equal sums, Alice decides which group to throw away. The sum of the smaller group (the one that was not thrown away) gets added to Alice's score, and the game continues on that smaller group. Alice wants to maximize her total score.

This is LeetCode 1563: Stone Game V, and it is a clean example of interval DP combined with prefix sums. If you have worked through Minimum Cost to Cut a Stick or Burst Balloons, the interval DP structure will feel familiar. The twist here is the comparison between left and right sums, which determines which half survives.

Why this problem is tricky

Your first instinct might be to try greedy: always split so the smaller side is as large as possible. But that does not work because the remaining stones affect future splits. A split that looks suboptimal now might leave a better arrangement for later rounds.

The key insight is that this is an interval DP problem. Define dp[i][j] as the maximum score Alice can earn starting from the subarray stoneValue[i..j]. For every possible split point k in that range, you compute the left sum (stoneValue[i..k]) and right sum (stoneValue[k+1..j]), then apply the game rules:

• If the left sum is smaller, the left side gets added to the score, and you continue playing on the right side. But wait, you actually keep the smaller side and throw away the larger side. So the score contribution is left_sum + dp[i][k].
• If the right sum is smaller, the score contribution is right_sum + dp[k+1][j].
• If the sums are equal, Alice can choose either side, so you take the max of both options.

You want prefix sums to compute range sums in O(1) instead of O(n).

Python solution

def stoneGameV(stoneValue: list[int]) -> int:
    n = len(stoneValue)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + stoneValue[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
            for k in range(i, j):
                left_sum = prefix[k + 1] - prefix[i]
                right_sum = prefix[j + 1] - prefix[k + 1]

                if left_sum < right_sum:
                    dp[i][j] = max(dp[i][j], left_sum + dp[i][k])
                elif left_sum > right_sum:
                    dp[i][j] = max(dp[i][j], right_sum + dp[k + 1][j])
                else:
                    dp[i][j] = max(dp[i][j], left_sum + max(dp[i][k], dp[k + 1][j]))

    return dp[0][n - 1]

The outer loop iterates over subarray lengths from 2 up to n. For each subarray [i, j], you try every split point k from i to j-1. The prefix array lets you grab left and right sums instantly. By the time you compute dp[i][j], all shorter subarrays are already filled.

Understanding the recurrence

The recurrence has three branches, and each one deserves attention:

Left sum is smaller (left_sum is less than right_sum): The left side gets thrown away. Its sum is added to Alice's score. The game continues on the left portion [i, k] because that is what remains after throwing away the larger right portion. Score = left_sum + dp[i][k].

Right sum is smaller (left_sum is greater than right_sum): The right side gets thrown away. Score = right_sum + dp[k+1][j].

Sums are equal: Alice gets to choose which side to throw away. She picks whichever continuation yields a higher total score: left_sum + max(dp[i][k], dp[k+1][j]).

Notice that Alice always scores the value of the smaller (or equal) portion, but the game continues on that same smaller portion. This is because the larger portion gets discarded. The remaining stones are the ones from the smaller side.

Visual walkthrough

Let's trace through stoneValue = [6, 2, 3, 4, 5, 5] step by step, building up the DP table from small subarrays to the full array.

Complexity analysis

Time: O(n^3). There are O(n^2) subarrays, and for each one you try up to O(n) split points. With n up to 500, this is 125 million operations in the worst case. Python might be tight, but the constant factor is small since the inner loop is just arithmetic and comparisons. In C++ or Java this runs comfortably.

Space: O(n^2) for the DP table and the prefix sum array (which is O(n), dominated by the table).

The building blocks

This problem is built on two reusable patterns:

Interval DP. You define dp[i][j] over subarrays and fill the table by increasing interval length. At each interval, you try every split point and combine two smaller subproblems. This same skeleton appears in Burst Balloons, Matrix Chain Multiplication, Minimum Cost to Cut a Stick, and many other problems. The only thing that changes is what happens at the split point. Once the template is in muscle memory, you can focus entirely on the problem-specific recurrence.

Prefix sums for range queries. Computing sum(stoneValue[i..k]) in O(1) via prefix[k+1] - prefix[i] is essential for keeping the overall complexity at O(n^3) instead of O(n^4). Prefix sums show up in sliding window problems, subarray sum queries, and anywhere you need fast range aggregation. Building the prefix array is a one-liner, but forgetting it is a common source of TLE.

Edge cases to watch for

• Two stones: stoneValue = [5, 3]. Only one split. Left = 5, right = 3. Right is smaller, score = 3. dp[0][1] = 3.
• All equal values: stoneValue = [4, 4, 4, 4]. Every split yields equal sums at some level. Alice always gets to choose, and the score is deterministic.
• One very large stone: stoneValue = [1, 1, 1, 100]. The large stone dominates. Most splits will have the right side larger, so Alice collects the small left sums.
• Descending values: stoneValue = [10, 8, 6, 4, 2]. Splitting near the right end gives a small right portion, while splitting near the left gives a small left portion. The DP explores all options.
• n = 1: A single stone cannot be split. The answer is 0. (The constraints say n is at least 1.)

From understanding to recall

You now understand why interval DP fits this problem, how the three-branch recurrence works, and why prefix sums are necessary. But understanding is not the same as fluency. In an interview, you need to set up the prefix array, write the triple loop by interval length, and implement the left-vs-right comparison without hesitating over which sum goes where.

The interval DP template is the same across a family of problems, but the details of each recurrence are different enough to trip you up if you have not drilled them individually. Stone Game V's three-branch comparison is distinct from Burst Balloons' multiplication or Cut a Stick's additive cost. You need to practice each variant until the differences are automatic.

Spaced repetition is the most efficient way to get there. You write the solution from scratch at increasing intervals, and each rep strengthens the specific neural pathway for this problem's recurrence. After a few reps, you see "compare left and right sums, keep the smaller side" and your hands know the code.

The interval DP pattern is one of roughly 60 reusable building blocks in the CodeBricks system. Learning them individually and drilling them with spaced repetition is far more effective than grinding problems randomly and hoping the patterns stick.

Related posts

• Coin Change - A classic 1D DP problem that introduces the idea of building up solutions from smaller subproblems
• Edit Distance - 2D string DP where each cell depends on three neighbors, a natural stepping stone toward interval DP
• Longest Increasing Subsequence - Another foundational DP problem that builds pattern recognition for subsequence and subarray reasoning