Partition DP

Every DP so far has had a state built from prefixes — dp[i] answers a question about the first i elements. Partition DP breaks that: the state is a range [i, j], and the recurrence loops over every possible way to split that range in two.

It is the hardest DP shape that regularly appears in interviews, and it is hard for a specific reason: the obvious recurrence is wrong. Thinking about which element to process first gives a subproblem you cannot solve independently. Thinking about which element is processed last gives one you can. That inversion is the whole pattern, and everything else follows from it.

What you’ll learn

• The range-state recurrence, and the loop over split points that defines it.
• Why “think about the last operation” is the reframe that makes it work.
• Why the fill order must be by increasing range length, not by row.
• Burst Balloons, and the sentinel trick that makes its subproblems independent.

The cue

You are looking at partition DP when…

• You must split a sequence into groups and the cost of a group depends on its whole contents — not on a per-element rule.
• Or you combine adjacent items repeatedly until one remains: multiply matrices, merge stones, burst balloons, cut a rod.
• Or the question is about a range rather than a prefix: “the best way to parenthesise”, “the minimum cost to triangulate”.

The structural test: does the answer for [i, j] decompose into [i, k] + [k+1, j] for some split point k you must search over? If yes, this is partition DP and the state is two indices.

The reframe that makes it solvable: ask which item is handled last, not first. Handling the first item leaves a remainder whose cost depends on what was already removed — the subproblems are not independent. Fixing the last one splits the range into two halves that never interact, which is exactly what DP requires.

Reach for something else when the state is a prefix (ordinary 1-D or 2-D DP), or when groups are formed by a per-element rule with no interaction (that is usually greedy).

Visual intuition

Partition DP fills a table indexed by (i, j) — but unlike LCS it fills by diagonal, because dp[i][j] depends on shorter ranges strictly inside it. The dependency arrows here are the same idea one dimension over:

dpTwo-index DP: every cell reads only cells already computedthe dependency discipline partition DP shares

rows: a = "ABCB"cols: b = "BDCA"

1def lcs(a, b):2    m, n = len(a), len(b)3    dp = [[0] * (n + 1) for _ in range(m + 1)]4    for i in range(1, m + 1):5        for j in range(1, n + 1):6            if a[i - 1] == b[j - 1]:7                dp[i][j] = dp[i - 1][j - 1] + 1     # diagonal + 18            else:9                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])10    return dp[m][n]

base caseRow 0 and column 0 are all zeros: the longest common subsequence with an empty string is empty. Those sentinels are why the loops can start at 1 and never test for out-of-range indices.

Play‹›1/34⟲

LCS reads the cell above, left and diagonal, so a row-major fill is safe. Partition DP reads every cell strictly INSIDE its range, which a row-major fill would not have computed yet — hence looping over range length first. The discipline is the same: never read a cell before you write it.

The template

partition_dp.py

def matrix_chain(dims):
    """dims has n+1 entries for n matrices; matrix i is dims[i] x dims[i+1]."""
    n = len(dims) - 1
    dp = [[0] * n for _ in range(n)]
 
    # LENGTH first. dp[i][j] needs shorter ranges inside it.
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float("inf")
            for k in range(i, j):                   # the split point
                cost = (dp[i][k] + dp[k + 1][j]
                        + dims[i] * dims[k + 1] * dims[j + 1])
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n - 1]
 
 
def burst_balloons(nums):                            # LC 312
    # Sentinel 1s so every subproblem has real neighbours.
    vals = [1] + nums + [1]
    n = len(vals)
    dp = [[0] * n for _ in range(n)]
 
    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            for last in range(left + 1, right):      # LAST balloon burst here
                dp[left][right] = max(
                    dp[left][right],
                    dp[left][last] + dp[last][right]
                    + vals[left] * vals[last] * vals[right],
                )
    return dp[0][n - 1]
 
 
print(matrix_chain([10, 30, 5, 60]))        # expect 4500
print(burst_balloons([3, 1, 5, 8]))         # expect 167

Why “last” and not “first”

Burst Balloons is the cleanest illustration. Bursting balloon i earns left * i * right where left and right are its current neighbours, and neighbours change as balloons pop.

Try fixing the first balloon to burst. You earn its points, then face a shorter array — but the two sides are now adjacent to each other, so what happens on the left changes the scores available on the right. The subproblems are entangled and there is no valid recurrence.

Now fix the last balloon k in the range (left, right). When k is burst, every other balloon in that range is already gone, so its neighbours are exactly vals[left] and vals[right] — the range boundaries, which never move. And the balloons strictly inside (left, k) and (k, right) were burst before k without ever being adjacent to each other, because k sat between them the whole time.

That independence is the whole reason the recurrence is valid

dp[left][right] is defined as the best score from bursting everything strictly between left and right, leaving those two standing. That definition is what makes dp[left][k] + dp[k][right] a legal sum: the two subranges are separated by k, so they never influence each other’s neighbours.

Get the definition wrong — make it inclusive, or fix the first balloon — and no amount of index fiddling recovers it. State the definition before writing code.

Dry run

burst_balloons([3, 1, 5, 8]), so vals = [1, 3, 1, 5, 8, 1].

Ranges of length 2 hold no interior balloons, so they are 0. Length 3 has exactly one choice:

range	interior	score
(0,2)	balloon 3	1·3·1 = 3
(1,3)	balloon 1	3·1·5 = 15
(2,4)	balloon 5	1·5·8 = 40
(3,5)	balloon 8	5·8·1 = 40

Length 4 must compare split points. Take (1,4) — interior balloons 1 and 5:

last burst	recurrence	value
k=2 (value 1)	dp[1][2] + dp[2][4] + 3·1·8	0 + 40 + 24 = 64
k=3 (value 5)	dp[1][3] + dp[3][4] + 3·5·8	15 + 0 + 120 = **135**

So dp[1][4] = 135 — burst the 1 first, then the 5 while it still has 3 and 8 as neighbours. Continuing to the full range (0,5) gives 167.

Two things worth noticing:

• The winning choice is not the largest immediate score. Bursting 8 first looks attractive and is wrong. Greedy fails here, which is why it is DP.
• dp[1][4] needed dp[1][3] and dp[2][4] — both length 3, both strictly shorter. A row-major fill would not have computed dp[2][4] before reaching dp[1][4], which is why the outer loop is over length.

Complexity

Problem	State	Transition	Total
Matrix chain (LC 1039 shape)	$O(n^2)$ ranges	$O(n)$ split points	$O(n^3)$
Burst Balloons (LC 312)	$O(n^2)$	$O(n)$	$O(n^3)$
Merge Stones (LC 1000)	$O(n^2 k)$	$O(n)$	$O(n^3 k)$
Palindrome Partitioning II (LC 132)	$O(n)$	$O(n)$	$O(n^2)$

$O(n^3)$ is the signature of this family, and it is the reason constraints sit around n ≤ 500. Seeing n ≤ 100 or n ≤ 500 alongside a “split the range” problem is a strong hint that a cubic partition DP is intended rather than something to optimise away.

The variant map

Variant	State	What the split means	Canonical problem
Matrix chain	dp[i][j]	where to place the outermost parenthesis	classic MCM
Burst balloons	dp[l][r] exclusive	which balloon is burst last	312 Burst Balloons
Merge stones	dp[i][j][m]	split into m piles	1000 Minimum Cost to Merge Stones
Min cuts to palindromes	dp[i] (prefix!)	last cut position	132 Palindrome Partitioning II
Triangulation	dp[i][j]	which vertex completes the triangle	1039 Minimum Score Triangulation
Guess number cost	dp[i][j]	which number to guess first	375 Guess Number Higher or Lower II

Not every “partition” problem needs a 2-D state

LC 132 asks for the minimum cuts to split a string into palindromes, and its state is a prefix: dp[i] is the answer for s[:i], and the transition loops over the last cut. That is $O(n^2)$, not $O(n^3)$.

The distinguishing question: does the cost of a piece depend on both endpoints interacting with what surrounds it (2-D state), or only on the piece itself (1-D state with a loop)? Palindrome-ness depends only on the piece, so 1-D suffices. Matrix multiplication cost depends on the boundary dimensions, so it does not.

Pitfalls

• Filling row-major instead of by range length. dp[i][j] reads cells strictly inside [i, j], which a row-major order has not written yet. The result is a table full of zeros silently treated as valid answers.
• Fixing the first item rather than the last. The subproblems become entangled and there is no correct recurrence. This is the defining conceptual error.
• Inclusive versus exclusive range boundaries. Burst Balloons wants dp[l][r] = “burst everything strictly between”. Mixing conventions mid-solution produces off-by-one scores that look almost right.
• Forgetting the sentinel 1s in LC 312. Without them, balloons at the array edges have no neighbour and the multiplication needs special cases at every boundary.
• Trying greedy. Bursting the largest balloon first is intuitive and wrong. If you cannot prove an exchange argument, it is DP.
• Assuming $O(n^3)$ is too slow. With n ≤ 500 it is roughly $10^8$ — tight but intended. Check the constraint before optimising.

Interview follow-ups

They ask	What they’re checking	The answer
“Why think about the last operation, not the first?”	The core insight	Fixing the last one leaves two subranges separated by it, so they never affect each other’s neighbours. Fixing the first leaves two halves that become adjacent, and the subproblems entangle
“Why loop over length in the outer loop?”	Dependency discipline	dp[i][j] depends on strictly shorter ranges inside it. Row-major order reads cells that have not been written
“What is the complexity, and why?”	Precision	$O(n^2)$ states × $O(n)$ split points = $O(n^3)$. That cubic is the family’s signature and explains the small constraints
“Why the sentinel 1s in Burst Balloons?”	Practical detail	So every subrange has real boundary neighbours and the score formula needs no edge cases. Multiplying by 1 is the identity, so they never change a result
“Could this be greedy?”	Whether you test your instincts	No — bursting the largest first is locally optimal and globally wrong. There is no valid exchange argument
“Write it top-down instead”	Flexibility	Memoised recursion on (left, right) is often easier here, because the recursion naturally visits shorter ranges first and the length-ordering problem disappears

Practice

4 problems

0 easy1 medium3 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○1039Minimum Score Triangulation of Polygonmedium
• ○132Palindrome Partitioning IIhard
• ○312Burst BalloonshardNeetCode 150
• ○1000Minimum Cost to Merge Stoneshard

Exercises

LC 312 — Burst Balloons · Hard

pch.exerciseTag pch.exerciseTitle

LC 1039 — Minimum Score Triangulation · Medium

pch.exerciseTag pch.exerciseTitle

LC 132 — Palindrome Partitioning II · Hard (the 1-D case)

pch.exerciseTag pch.exerciseTitle

Self-check

pch.quizTag Partition DP — self-check

1. In Burst Balloons, why fix the LAST balloon burst in a range rather than the first?

   A It is an arbitrary convention; either works B Because when k is burst last, every other balloon in the range is gone, so its neighbours are the fixed range boundaries — and the two subranges never affect each other C Because the last balloon always scores most D To make the loop bounds simpler
   pch.quizShowAnswer

   B — Because when k is burst last, every other balloon in the range is gone, so its neighbours are the fixed range boundaries — and the two subranges never affect each other — Fixing the first leaves two halves that become adjacent, so what happens on one side changes the scores available on the other. The subproblems entangle and there is no valid recurrence.

2. Why must the outer loop iterate over range LENGTH?

   A For cache efficiency B Because dp[i][j] depends on strictly shorter ranges inside it, which a row-major fill has not written yet C Because the table is triangular D It does not matter
   pch.quizShowAnswer

   B — Because dp[i][j] depends on strictly shorter ranges inside it, which a row-major fill has not written yet — Row-major order reads uncomputed zeros and treats them as valid answers, so the output is wrong with no error. Length-first guarantees every dependency is already written.

3. What is the complexity of this family, and what does it tell you about the constraints?

   A O(n^2) — two indices B O(n^3): O(n^2) ranges times O(n) split points — which is why constraints sit near n <= 500 C O(2^n) D O(n log n)
   pch.quizShowAnswer

   B — O(n^3): O(n^2) ranges times O(n) split points — which is why constraints sit near n <= 500 — The cubic is the signature. Seeing n <= 100 or n <= 500 next to a split-the-range problem is the statement hinting that a cubic partition DP is intended, not something to optimise away.

4. Why pad Burst Balloons with sentinel 1s?

   A To handle the empty input B So every subrange has real boundary neighbours and the score formula needs no edge cases — and multiplying by 1 never changes a result C To make the array length even D To mark burst balloons
   pch.quizShowAnswer

   B — So every subrange has real boundary neighbours and the score formula needs no edge cases — and multiplying by 1 never changes a result — Without them, balloons at the array edges have a missing neighbour and every multiplication needs a boundary check. The 1s are the multiplicative identity, so they are free.

5. LC 132 asks for minimum palindrome cuts and is only O(n^2). Why is it not cubic?

   A Because strings are shorter than arrays B Because its state is a PREFIX, not a range — palindrome-ness depends only on the piece itself, not on how it interacts with its surroundings C Because it uses memoisation D It is actually O(n^3)
   pch.quizShowAnswer

   B — Because its state is a PREFIX, not a range — palindrome-ness depends only on the piece itself, not on how it interacts with its surroundings — That distinction is the useful test: if a piece's cost depends on both endpoints interacting with what surrounds it you need a 2-D state; if it depends only on the piece, a 1-D state with a loop suffices.

Recall card

• Cue — split a range and search over the split point; or combine adjacent items repeatedly. State is dp[i][j], two indices.
• The reframe — fix which item is handled last, never first. That is what makes the two subranges independent.
• Recurrence — dp[i][j] = best over k in (i, j) of dp[i][k] + dp[k][j] + cost(i, k, j).
• Fill order — range length outermost, then i. Row-major reads uncomputed cells.
• Complexity — $O(n^3)$: $O(n^2)$ states × $O(n)$ splits. Expect n ≤ 500.
• Sentinels — pad with identity values so boundaries need no special case.
• 1-D exception — if a piece’s cost depends only on the piece (palindromes), a prefix state gives $O(n^2)$.

Recap

• Partition DP is the shape where the state is a range and the transition searches every split — the hardest DP shape that appears regularly in interviews.
• The single insight is “think about the last operation”. Everything else, including the loop order and the sentinels, follows from wanting independent subproblems.
• Fill by increasing range length, because each cell depends on shorter ranges strictly inside it.
• $O(n^3)$ is expected, not a failure — the constraints are sized for it.
• Top-down memoisation is often easier to write here, since the recursion visits shorter ranges first automatically.

Next: Bitmask and Tree DP — when the state is a set rather than an index.