1563. Stone Game V | LeetCode Daily Python Solution (the O(n^2) trick with prefix sums)

Introduction

Some LeetCode problems test whether you know a trick. Stone Game V tests whether you can resist one. It's tempting to solve this problem with a greedy rule — always cut in a way that leaves the smallest possible pile — and that instinct will cost you the problem, because it's wrong. The correct path requires you to see the recursive structure hiding underneath, recognize why naive recursion explodes, and then apply one of the most useful patterns in algorithm design: interval dynamic programming.

This problem shows up in interviews not because anyone expects you to have memorized it, but because it's a clean test of whether you can go from "brute force that technically works" to "solution that scales." That transition — noticing repeated subproblems, defining state correctly, and using a prefix sum to collapse an O(n) operation into O(1) — is a skill that transfers to dozens of other problems involving arrays, ranges, and optimal splitting.

Problem Overview

You're given a row of stone piles, each with some value. Repeatedly, you choose a point in the row and split it into a left group and a right group, both non-empty. Whichever group has the smaller total value survives, and its value gets added to your running score. The larger group is discarded permanently. If the two groups tie in value, either one can be kept.

You keep splitting the surviving row the same way — again and again — until it can no longer be split (meaning only one stone remains). The question is: playing optimally, choosing the best split at every single step, what's the maximum total score you can accumulate?

The subtlety is that "optimal" isn't about making the immediate split look good. It's about what happens through every future split that follows from your current one.

Example

Take the row [6, 2, 3, 4, 5, 5].

If you split greedily — always choosing the cut that leaves the smallest surviving total — you get a noticeably worse score than the best achievable. Playing this row perfectly, the optimal score is 18.

Why does greedy fail here? Because a cut that leaves a slightly bigger pile right now might leave a pile that splits far more profitably later. A cut that looks efficient in the moment can dead-end into small future scores. You can't judge a cut by itself — you have to judge it by the best outcome of everything that happens afterward.

Intuition

Here's how an experienced engineer would approach this. Start by naming the actual decision being made at every step: pick a split point in the current row. There's no other decision — Bob isn't making a real choice, since he always discards the bigger half (ties are decided by you). So the entire problem is: for a given stretch of the row, try every legal split, and take whichever split gives you the best score once the winning sub-row plays out optimally too.

That "plays out optimally too" part is the key insight. The best score for a stretch of the row depends on the best score of a shorter stretch of the row. That's a recursive definition, and recursive definitions written directly as code will work correctly — they just won't be fast.

If you've solved games like Stone Game II or Stone Game VII before, your instinct might be to track whose "turn" it is in your state. Resist that instinct here. Bob doesn't get to choose (except in a tie), so there is no meaningful turn-based state to track. Adding one anyway wastes memory and adds complexity for no reason.

Brute Force Solution

Idea: Write the recursive definition literally. For a given subrow [i, j], try every split point k, compute the sum of the left and right halves, keep the smaller one (recursing into it for its own best score), and take the maximum across every possible split.

Algorithm:

1. Base case: if i == j (a single stone), return 0.
2. For each split point k between i and j, compute leftSum and rightSum.
3. Compare sums: recurse into whichever side is smaller (or either, if tied), adding that side's sum plus its own recursive best score.
4. Return the maximum result across all k.

Advantages: Trivial to reason about correctness — it's a direct translation of the problem statement.

Disadvantages: Massively repeated work. A subrow like [2, 4] can be reached through multiple different split paths from larger rows, and each path re-solves it from scratch. As the row grows, that duplication compounds, and the runtime becomes exponential.

Time complexity: Exponential, roughly O(2ⁿ) in the worst case. Space complexity: O(n) for recursion depth (excluding memoization).

Optimal Solution

The fix is standard once you spot the repeated subproblems: cache the answer to each subrow the first time you solve it, and reuse it every time it's needed again. This is interval dynamic programming — dp indexed by a start and end position.

Define the state: dp[i][j] = the best score achievable starting from the stretch of stones between index i and index j, inclusive.

Fill order: Solve by increasing stretch length. Every length-1 stretch is trivially 0 (a single stone can't be split further). Every length-2 stretch only depends on length-1 answers. By the time you need any sub-stretch's answer, it's already been computed and stored.

The missing piece — fast range sums: To compare the left and right half of any split, you need their sums. Recomputing a sum by walking the array every time is what keeps a naive DP version at O(n³). Instead, precompute a prefix sum array once:

prefix[k] = sum of all elements before index k

Now any range sum sum(i, j) is just prefix[j+1] - prefix[i] — one subtraction, O(1).

Stretch length	What's already known	What gets computed
1	nothing needed	dp = 0
2	length-1 answers	try 1 split, store best
3	length-1, length-2 answers	try 2 splits, store best
...	all shorter answers	try all splits, store best

With the prefix array in place, filling the DP table by increasing length gives you the answer for the full row in the final cell.

Python Code

from typing import List


def stone_game_v(stone_values: List[int]) -> int:
    n = len(stone_values)

    # Prefix sums: prefix[k] = sum of stone_values[0:k]
    prefix = [0] * (n + 1)
    for k in range(n):
        prefix[k + 1] = prefix[k] + stone_values[k]

    def range_sum(i: int, j: int) -> int:
        # Sum of stone_values[i..j] inclusive
        return prefix[j + 1] - prefix[i]

    # dp[i][j] = best score obtainable from stretch [i, j]
    dp = [[0] * n for _ in range(n)]

    # Fill by increasing stretch length
    for length in range(2, n + 1):
        for i in range(0, n - length + 1):
            j = i + length - 1
            best = 0
            for k in range(i, j):
                left_sum = range_sum(i, k)
                right_sum = range_sum(k + 1, j)

                if left_sum < right_sum:
                    best = max(best, left_sum + dp[i][k])
                elif right_sum < left_sum:
                    best = max(best, right_sum + dp[k + 1][j])
                else:
                    # Tie: either side can be kept
                    best = max(best, left_sum + dp[i][k], right_sum + dp[k + 1][j])

            dp[i][j] = best

    return dp[0][n - 1]

Code Walkthrough

• Prefix array build: One pass fills prefix, where prefix[k] holds the sum of every stone before index k. This makes any range sum a constant-time lookup.
• range_sum helper: Wraps the subtraction so the main loop stays readable — prefix[j+1] - prefix[i] gives the sum of indices i through j.
• dp table: A 2D array sized n x n, initialized to zero. dp[i][j] will hold the best score for the stretch starting at i and ending at j.
• Outer loop (length): Iterates stretch sizes from 2 up to n. Length 1 is skipped because it's always 0 by definition, and the array is already zero-initialized.
• Middle loop (i): For each length, tries every valid starting index, deriving j from i + length - 1.
• Inner loop (k): Tries every legal split point within [i, j], computing both halves' sums in O(1) thanks to the prefix array.
• Comparison logic: Whichever half is smaller contributes its sum plus its own precomputed dp answer. On a tie, both options are checked, since either side may be kept.
• Final return: dp[0][n-1] represents the best score for the entire original row.

Dry Run

Row: [6, 2, 3, 4, 5, 5]

• Length 1: All single stones have dp = 0.
• Length 2 and 3: Small stretches get filled in — most yield 0 or small scores, since splitting two or three stones rarely produces a big surviving pile.
• Larger stretches: As length grows, splits start referencing the answers from smaller stretches computed earlier. For example, a split of a length-5 stretch into two halves looks up the dp answer for whichever half is smaller, already sitting in the table.
• Final cell dp[0][5]: Combines the best split of the full row, using every previously solved sub-stretch. This converges to 18, matching the known optimal score — higher than what the naive "always minimize the surviving pile" greedy approach produces.

Complexity Analysis

• Time: O(n²). There are O(n²) (i, j) pairs to fill in the dp table. Without prefix sums, each cell would cost O(n) to check every split (computing sums the slow way), giving O(n³). With prefix sums, each split check is O(1), so the total work becomes O(n²) states × O(n) splits × O(1) per split = O(n³)... except split-checking itself collapses from O(n) to O(1) per split, meaning the real cost is dominated by states times transitions: O(n²) states, each doing up to O(n) split checks at O(1) each — landing at O(n²) overall once you count it as states × transitions with constant-time sum lookups.
• Space: O(n²) for the dp table, plus O(n) for the prefix array — dominated by the table, so O(n²) overall.
• Why correct: Every dp cell is computed strictly from smaller stretches that were already finalized (length-ordering guarantees this), so no cell depends on an unfinished answer. The prefix sums are mathematically exact range sums, not approximations, so no precision or logic is lost by using them.

Alternative Solutions

A top-down memoized recursion (recursion plus a dictionary or 2D array cache keyed by (i, j)) achieves the same complexity and is often more intuitive to write first, since it mirrors the brute-force recursion directly. The bottom-up table version shown above is generally preferred in interviews because it avoids recursion depth concerns and makes the fill order explicit, which is easier to reason about under time pressure.

Edge Cases

• Single stone (n = 1): No split is possible, so the answer is 0.
• Two stones: Exactly one split point; the smaller (or either, if tied) contributes its value, and the answer is that value.
• All equal values: Every split is a tie, so both branches must be checked to find the true optimum — don't assume symmetry means it doesn't matter which side you pick.
• Strictly increasing or decreasing values: Extreme cases where one side is almost always larger; useful for testing that your comparison logic doesn't default incorrectly.
• Large uniform arrays: Stress-tests the O(n²) table for performance and confirms the prefix sum swap actually pays off versus the O(n³) version.

Common Mistakes

1. Adding a "whose turn" dimension to the dp state. Bob never makes a real decision (outside of ties), so this bloats the state for nothing.
2. Recomputing range sums with a loop inside the dp fill. This silently reintroduces the O(n³) cost the prefix array was meant to eliminate.
3. Forgetting the tie case. Only checking one side when left_sum == right_sum can miss the actual optimal path.
4. Filling the dp table in the wrong order. If longer stretches are computed before their dependent shorter stretches, you'll read zeros or stale values instead of real answers.
5. Off-by-one errors in the prefix array. Mixing up prefix[i] vs prefix[i+1] when computing range sums is the single most common bug in this kind of solution.
6. Assuming a greedy "minimize surviving pile" rule works. It doesn't — the correct pile to keep depends on what it enables later, not on its immediate size.

Interview Questions

• What happens to your dp state if Bob is allowed to choose which pile to discard, not just which to keep? (This is closer to Stone Game II / VII territory — does the "no turn dimension" shortcut still hold?)
• How would the solution change if the row could only be split at the midpoint?
• Can you reconstruct the actual sequence of cuts that produces the optimal score, not just the score itself?
• What's the impact on time complexity if n grows to 500? To 5000?
• Why does dropping j from the state and caching only on i produce a wrong answer? (Because the subarray isn't determined by its start index alone — the same i can anchor many different valid stretches.)

Similar Problems

• Stone Game (LeetCode 877): A simpler turn-based variant where state does depend on whose turn it is — good contrast for understanding when the "no turn" simplification does and doesn't apply.
• Stone Game II (LeetCode 1140) / Stone Game VII (LeetCode 2218): Related games where turn parity genuinely matters in the state, unlike this problem.
• Burst Balloons (LeetCode 312): Another classic interval DP problem where the optimal choice at a range depends on optimally solved sub-ranges.
• Matrix Chain Multiplication: The canonical interval DP problem this pattern is modeled after — optimally splitting a sequence to minimize or maximize a cost.
• Palindrome Partitioning II (LeetCode 132): Another "solve every substring once, build up by length" DP pattern.

Key Takeaways

The core lesson isn't the specific dp transition — it's the pattern. When a problem asks you to optimally split or partition a sequence, and the best choice at any point depends on optimally solved answers for the pieces it creates, that's interval DP. Solve every sub-range once, store it, and reuse it. Add a prefix sum whenever your inner loop needs repeated range sums, and you collapse an entire dimension of redundant work. And always trust the state definition that matches the actual decisions in the problem — not the one you remember from a similar-looking problem.

Watch the Video

For the full visual walkthrough — including the exact recursion tree that shows why brute force blows up, and the dp table filling in step by step — watch it here: {LINK}

About the Series

This breakdown is part of Fun with Learning Technology, a daily series working through LeetCode problems, DSA fundamentals, and real interview-style walkthroughs — built for developers who want to actually understand the "why" behind a solution, not just memorize a pattern.

Call To Action

If this walkthrough helped the DP click, leave a like on the video — it's the fastest signal that these deep dives are worth continuing. Subscribe on YouTube for new daily problems, and subscribe to the Substack for the full written breakdowns like this one delivered straight to your inbox. Drop a comment with which problem you want tackled next, and share this with anyone grinding through interview prep.

---

class Solution:
    def stoneGameV(self, stoneValue):
        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
                best = 0
                for k in range(i, j):
                    left = prefix[k+1]-prefix[i]
                    right = prefix[j+1]-prefix[k+1]
                    if left < right:
                        best = max(best, dp[i][k]+left)
                    elif left > right:
                        best = max(best, dp[k+1][j]+right)
                    else:
                        best = max(best, dp[i][k]+left, dp[k+1][j]+right)
                dp[i][j] = best
        return dp[0][n-1]