DPAlgorithmaka range DP, substring DP, split-point DP

Interval (Range) DP

State is a contiguous range [l, r]; the answer is built by choosing a split point or the last element removed inside the range.

▶ VisualizePattern: Dynamic ProgrammingPractice (3)
Progress

Overview

Interval DP applies when a problem on a contiguous segment [l, r] decomposes into problems on strictly shorter segments. The state is dp[l][r], there are O(n²) states, and the transition usually tries every split k in [l, r) (O(n)), giving O(n³) — hence typical constraints n ≤ 100–500. Some transitions are O(1) (palindromic substrings: dp[l][r] = s[l]==s[r] and dp[l+1][r-1]), giving O(n²) and allowing n ≤ 5000.

The crucial modelling trick is choosing what the split means. In Matrix Chain Multiplication k is the position of the last multiplication. In Burst Balloons k is the last balloon burst in (l, r) — thinking "first" instead of "last" fails because bursting a balloon changes the neighbours of the rest, while bursting it last means its neighbours are exactly l and r. Other members: Minimum Cost to Merge Stones, Stone Game, Strange Printer, Remove Boxes (with an extra dimension), Palindrome Partitioning II, Optimal BST, Minimum Score Triangulation.

Iteration order is by increasing interval length, so all sub-intervals are ready; top-down Memoization (Top-Down DP) is often cleaner because the order is implicit.

intervalrangeO(n³)split pointpalindromesmatrix chain

Intuition

A mental model before the formal terms.

Think of a long strip of paper you must cut into pieces, where every cut costs something depending on the piece being cut. The cheapest way to reduce the whole strip is: pick the very first cut somewhere, then optimally cut each of the two halves. Since the halves are independent, you only need the best cost of every possible sub-strip — a table indexed by (left end, right end).

Burst Balloons inverts the order: instead of "what happens first" ask "which balloon is left standing last in this range". Once you decide that, the range splits cleanly into two independent sub-ranges, and the last balloon's reward is computed against the fixed boundary balloons l and r.

How it works

  1. State: dp[l][r] = answer for the segment [l, r] (inclusive or exclusive boundaries — pick one and be consistent; exclusive boundaries with padding sentinels simplify Burst Balloons).
  2. Transition: dp[l][r] = best over k in (l, r) of dp[l][k] + dp[k][r] + cost(l, k, r) — or a direct O(1) step in from both ends when the structure is palindrome-like.
  3. Base cases: empty or single-element intervals: dp[i][i] = 0 (no work) or 1/true (single char is a palindrome).
  4. Order: for len from 2 to n, for l from 0 to n - len: r = l + len - 1. Table: 2D, only l ≤ r used. Answer: dp[0][n-1] (or dp[0][n+1] with padding).
  5. Optimization: Knuth's optimization brings some O(n³) interval DPs to O(n²) when the optimal split is monotone; rarely needed in interviews.

Why it works

Whatever the optimal sequence of operations on [l, r], one operation is last (or first), and it splits the range into pieces whose operations are independent of each other. Each piece must be handled optimally (otherwise substitute a better handling), so trying every last operation and recursing is exact.

Increasing-length order is a topological order since every transition reads strictly shorter intervals.

Recognition

How to tell a problem wants this.

  • Operations on a contiguous segment that remove/merge/cut elements and change the structure for the rest ("burst", "merge adjacent piles", "remove boxes", "parenthesize").
  • Questions about substrings or subarrays where the answer for [l, r] depends on [l+1, r-1] or on a split inside.
  • Constraints n ≤ 100–500 (cubic) or n ≤ 5000 with an O(1) transition.
  • Two-player games on a line of items where players take from the ends (Stone Game / Predict the Winner).
“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Matrix Chain Multiplication visualization.

10
0
30
1
5
2
60
3
A1A2A3
A10··
A2·0·
A3··0
1/9A1..A3 have shapes 10×30, 30×5, 5×60. A single matrix needs 0 multiplications, so the diagonal is 0. Only the upper triangle (i ≤ j) is used.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn Matrix Chain Multiplication →
1dp[i][i] = 0
2for len in 2 .. n:
3  for i in 1 .. n-len+1: j = i+len-1
4    dp[i][j] = ∞
5    for k in i .. j-1:
6      cost = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]
7      if cost < dp[i][j]: dp[i][j] = cost; split[i][j] = k
8return dp[1][n]
Variables
n3
Complexity
best O(n³)
avg O(n³)
worst O(n³)
space O(n²)
Speed

Pseudocode

1# burst balloons: pad nums with 1 on both ends
2# dp[l][r] = max coins from bursting everything strictly between l and r
3for len in 2..n+1:
4  for l in 0..n+1-len:
5    r = l + len
6    for k in l+1..r-1:              # k = last balloon burst in (l, r)
7      dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + a[l]*a[k]*a[r])
8return dp[0][n+1]

Implementations

1import math
2 
3# Interval DP: the state is a RANGE [i, j], and the transition picks a split
4# point or peels an end. Ranges are solved shortest-first, so every sub-range
5# a transition needs is already final.
6# Representative example: burst balloons, plus longest palindromic subsequence.
7 
8 
91 · dp[i][j] = best score obtainable from the open interval (i, j)
10def burst_balloons(input_nums: list[int]) -> int:
11    # Pad with 1s so the boundary cases need no special handling
12    nums = [1] + list(input_nums) + [1]
13    n = len(nums)
14    dp = [[0] * n for _ in range(n)]
15 
162 · Grow by interval length, so shorter ranges are always ready
17    for length in range(2, n):
18        for i in range(n - length):
19            j = i + length
203 · k is the LAST balloon burst inside (i, j), so i and j survive
21            best = 0
22            for k in range(i + 1, j):
23                best = max(best, dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])
24            dp[i][j] = best
25    return dp[0][n - 1]
26 
27 
284 · Same shape, different transition: peel the two ends instead of splitting
29def longest_palindromic_subsequence(s: str) -> int:
30    n = len(s)
31    if n == 0:
32        return 0
33    dp = [[0] * n for _ in range(n)]
34    for i in range(n):
35        dp[i][i] = 1
36    for length in range(2, n + 1):
37        for i in range(n - length + 1):
38            j = i + length - 1
39            dp[i][j] = dp[i + 1][j - 1] + 2 if s[i] == s[j] else max(dp[i + 1][j], dp[i][j - 1])
40    return dp[0][n - 1]
41 
42 
435 · Minimum cost to merge adjacent stones — the same length-first sweep
44def merge_stones(a: list[int]) -> int:
45    n = len(a)
46    if n <= 1:
47        return 0
48    prefix = [0] * (n + 1)
49    for i, x in enumerate(a):
50        prefix[i + 1] = prefix[i] + x
51    dp = [[0] * n for _ in range(n)]
52    for length in range(2, n + 1):
53        for i in range(n - length + 1):
54            j = i + length - 1
55            best = math.inf
56            for k in range(i, j):
57                best = min(best, dp[i][k] + dp[k + 1][j])
58            dp[i][j] = int(best) + prefix[j + 1] - prefix[i]  # plus the cost of this merge
59    return dp[0][n - 1]
Walkthrough
  1. [1] + list(input_nums) + [1] copies and pads without touching the caller's list.
  2. The inner minimisation accumulates into a local best and writes dp[i][j] once, which avoids repeated list indexing in the innermost loop.
  3. math.inf is a float, so int(best) converts back before the integer arithmetic in merge_stones — using a large integer sentinel would avoid the round trip.
  4. The palindromic variant uses a conditional expression for the two-branch recurrence, keeping the body to one line.
  5. range(n - length + 1) and range(n - length) differ by one because the burst-balloons interval is open (i, j) while the palindromic one is closed [i, j] — a genuine source of off-by-one errors.
Complexity (this implementation)
time O(n^3) for the split-based variants; O(n^2) for the peel-based palindromic one · space O(n^2)

The n^3 triple loop is pure Python and is the slowest entry in this group; functools.lru_cache on a recursive form is often clearer at the same cost.

Language notes
  • [[0] * n for _ in range(n)] is mandatory; [[0] * n] * n aliases one row n times.
  • functools.lru_cache on a recursive solve(i, j) expresses interval DP very naturally and handles the ordering automatically — at the cost of O(n^2) cache entries and O(n) recursion depth.
  • math.inf is a float; mixing it into an integer table means the table becomes float-typed unless converted back.
  • Hoisting dp[i] into a local before the innermost loop is the usual CPython speed-up for a 2D DP.
Common mistakes in this language
  • Aliasing rows with [[0] * n] * n.
  • Leaving math.inf in an integer table so downstream comparisons become float comparisons.
  • Mixing the open-interval and closed-interval range bounds between the two variants.
Language differences that matter here
  • The infinity sentinel is cleanest in JS/TS (Infinity) and Python (math.inf, though it is a float); C++ needs INT_MAX plus the discipline never to add to it before overwriting.
  • 2D table construction aliases by default in Python ([[0]*n]*n) and JS/TS (fill with an array), and never in C++.
  • Padding the input: Python [1] + list(x) + [1] and JS/TS [1, ...x, 1] are one-liners that copy; C++ takes the vector by value and inserts, which is the same idea spelled differently.
  • Only Python offers a genuinely different formulation via functools.lru_cache on a recursive solve(i, j), which handles the length-first ordering implicitly rather than requiring the loop discipline.

Complexity

Best
—
Average
—
Worst
O(n³) with a split-point transition; O(n²) with an O(1) transition
Space
O(n²)

Knuth or divide-and-conquer optimization can reduce O(n³) to O(n²) when the split point is monotone.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Contiguous ranges that decompose by a split point or by peeling both ends.
  • Parenthesization / merge order problems (matrix chain, merging stones, polygon triangulation).
  • Palindrome-structure questions on substrings.
Avoid it when
  • n is large (≥ 10^4) — O(n²) states alone are too many; look for a greedy, a stack, or a linear DP.
  • Segments are independent and never interact — a 1D (Linear) DP over prefixes suffices.
  • The operation does not change the structure for remaining elements — then order does not matter and a simpler formulation exists.

Alternatives

1D (Linear) DP2D (Two-Sequence) DPDivide and ConquerMonotonic StackMatrix Chain Multiplication

Common mistakes

  • Filling the table in l, r order instead of by length, so dp[l][k] or dp[k][r] is still zero when read.
  • Choosing the "first" operation as the split when the structure requires "last" (Burst Balloons).
  • Off-by-one in inclusive vs exclusive boundaries; mixing the two within one solution.
  • Forgetting boundary sentinels (padding with 1s) and special-casing the edges instead.

Interview patterns

  • Burst Balloons, Matrix Chain Order, Minimum Cost to Merge Stones, Minimum Score Triangulation.
  • Longest Palindromic Subsequence, Palindromic Substrings count, Palindrome Partitioning II.
  • Stone Game / Predict the Winner (score difference DP on [l, r]).
  • Strange Printer, Remove Boxes (interval DP with an extra "count of equal on the right" dimension).
Interview questions on this
Mock interviews

Example problems

Longest Palindromic SubstringmediumBurst BalloonshardMatrix Chain Multiplicationhard