Interval DP

Interval DP solves problems on a contiguous range [i, j] of an array or string by combining answers for smaller ranges inside it. The state is the pair of endpoints, and the computation runs from short intervals to long ones.

Intuition

Many "merge", "burst", "cut" or "parenthesize" problems have the same structure: the best way to handle [i, j] depends on how you split it, and each side of the split is an independent smaller problem. Two shapes cover almost everything:

• Split point: f[i][j] = best over k of f[i][k] + f[k+1][j] + cost(i, j, k). Try every place where the last merge happens (or the first cut, or the last element removed). O(n^3).
• Shrink from the ends: f[i][j] comes from f[i+1][j], f[i][j-1] or f[i+1][j-1], depending on what happens to the two end elements. O(n^2).

Since every transition reads strictly shorter intervals, iterating by increasing length (or by i descending and j ascending) guarantees that everything you read is ready.

When to use it in interviews / OAs

• Operations combine adjacent elements (merging neighbors, bursting a balloon whose score depends on its current neighbors).
• The answer for the whole array depends on "which operation happens last" inside a range.
• Palindromes, matching brackets, or removing from either end of a sequence.
• n up to about 100-500: O(n^3) fits; for n up to a few thousand, only the O(n^2) shrink shape fits.

Template 1: merging adjacent piles

Piles stand in a row; merging two adjacent piles costs their combined size, and you repeat until one pile is left. f[i][j] is the best total cost to merge a[i..j] into one pile. Whatever happens, the last merge joins some a[i..k] and a[k+1..j], and it costs sum(a[i..j]) regardless of k. For piles arranged in a circle, double the array and take the best window of length n.

def merge_cost(piles: list[int], circular: bool = False, pick=min) -> int:
    n = len(piles)
    if n <= 1:
        return 0
    a = piles * 2 if circular else piles[:]
    m = len(a)
    prefix = [0] * (m + 1)
    for i, x in enumerate(a):
        prefix[i + 1] = prefix[i] + x
    # f[i][j] = best total cost to merge a[i..j] (inclusive) into one pile
    f = [[0] * m for _ in range(m)]
    for length in range(2, n + 1):
        for i in range(m - length + 1):
            j = i + length - 1
            best_split = pick(f[i][k] + f[k + 1][j] for k in range(i, j))
            f[i][j] = best_split + prefix[j + 1] - prefix[i]
    if circular:
        return pick(f[i][i + n - 1] for i in range(n))
    return f[0][n - 1]

Pass pick=max for the maximum-cost version. Prefix sums make the range sum O(1).

Template 2: think about the last action

Bursting balloon k earns left * v[k] * right, where left and right are its current neighbors. Choosing the first balloon to burst is a dead end: the neighbors of everything else change. Choose the last balloon k in the open interval (i, j) instead: when it bursts, its neighbors are exactly i and j, and the two sides (i, k) and (k, j) never interact.

def burst_balloons(nums: list[int]) -> int:
    v = [1] + nums + [1]  # padding: bursting at the border multiplies by 1
    n = len(v)
    # f[i][j] = best coins from bursting every balloon strictly between i and j
    f = [[0] * n for _ in range(n)]
    for length in range(2, n):  # length = j - i
        for i in range(n - length):
            j = i + length
            f[i][j] = max(f[i][k] + f[k][j] + v[i] * v[k] * v[j] for k in range(i + 1, j))
    return f[0][n - 1]

The open-interval definition (i and j themselves are not burst) is what makes the recurrence clean. The same trick works for cutting a stick (add both ends to the sorted cut positions; the cost of a cut is the current segment length) and for triangulating a convex polygon.

Template 3: shrinking from both ends

The longest palindromic subsequence of s[i..j]: if the end characters match, they wrap a palindrome of s[i+1..j-1]; otherwise drop one of them.

def longest_palindromic_subsequence(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    # f[i][j] = longest palindromic subsequence inside s[i..j]
    f = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):  # i descending, j ascending: shorter ranges first
        f[i][i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                f[i][j] = f[i + 1][j - 1] + 2
            else:
                f[i][j] = max(f[i + 1][j], f[i][j - 1])
    return f[0][n - 1]

When j = i + 1 and the characters match, f[i+1][j-1] is an empty range and stays 0, so no special case is needed.

Complexity

Shape	States	Transition	Total
Split point	O(n^2)	O(n)	O(n^3) time, O(n^2) space
Shrink from ends	O(n^2)	O(1)	O(n^2) time, O(n^2) space

Circular inputs double n, which multiplies the O(n^3) cost by about 8 but keeps the same order of growth.

Common pitfalls

• Wrong iteration order: looping i ascending with j ascending reads f[i+1][...] before it exists. Loop by length, or i from right to left.
• Closed vs open intervals: decide whether i and j are part of the subproblem and keep it consistent; burst balloons only works cleanly with open intervals.
• "First" instead of "last": if choosing the first action changes the cost of later actions, choose the last action instead.
• Circular arrays: forgetting to double the array, or taking windows longer than n.
• Python speed: O(n^3) with n = 300 is about 4.5 million inner steps; fine. With n = 500 it is slow in pure Python, so precompute range sums and avoid creating lists inside the innermost loop.

Interview variations

• Merging piles (adjacent pairs; or K piles at a time, which is only possible when (n - 1) % (K - 1) == 0).
• Burst balloons, minimum cost to cut a stick, minimum score triangulation of a polygon: "last action" splits.
• Longest palindromic subsequence, minimum insertions to make a palindrome (n - LPS).
• Two-player pick-from-either-end games: f[i][j] = max(a[i] - f[i+1][j], a[j] - f[i][j-1]) is the best score difference for the player to move.
• Guess-the-number with minimum worst-case cost: f[i][j] = min over k of k + max(f[i][k-1], f[k+1][j]).
• Counting parenthesizations (ways to evaluate an expression to a value): split at every operator and multiply the counts of both sides.