Interval DPInterval DP

01Why it exists

Reach for it when you see:A contiguous run of things, merging two neighbouring segments, where the last step splits, parenthesisation, bursting balloons, palindromes, triangulation, a dp[i][j] that covers an interval, filling shortest intervals first.

02The core idea

The state in interval DP is a contiguous range: dp[i][j] is the best answer when you only consider elements i through j. It fits problems where the answer for a whole range can be assembled from the answers for a left part and a right part, and the way you split them is to enumerate the split point k: dp[i][j] = best over k of (dp[i][k] ⊕ dp[k+1][j] + the cost of joining those two parts). Intervals of length 1 are usually the base case, and the answer sits in dp[0][n−1].

The trick is choosing, for each interval, a "decision" that leaves the two sides independent of each other. Take Burst Balloons: popping a balloon scores left neighbour × itself × right neighbour, and the neighbours change as balloons disappear. Enumerating "which balloon pops first" does not work, because once it is gone the balloons on either side become each other's neighbours and the sub-problems are no longer independent. Enumerating "which balloon k pops last" does work: inside (i, j), everything popped before k lies entirely to its left or entirely to its right, so when k finally pops its neighbours are exactly i and j, and the two sides are completely independent — dp[i][j] = max(dp[i][k] + dp[k][j] + a[i]·a[k]·a[j]). Every possible popping order has exactly one "last balloon", so enumerating k misses nothing.

The fill order matters. Everything dp[i][j] reads is a shorter interval, so the outer loop runs over interval length from short to long and the inner loop enumerates the start i. The alternative is to run i downwards and j upwards. There are O(n²) states and each enumerates O(n) split points, giving O(n³) time and O(n²) space, which is workable up to around n ≤ 500. Some problems — optimal binary search trees, merges satisfying the quadrangle inequality — can restrict the range of k with Knuth's optimisation and drop to O(n²).

The usual traps: filling the table with a plain "i ascending, j ascending" double loop, which reads dp[k+1][j] before it has been computed; mixing up open and closed intervals, since Burst Balloons uses the open interval (i, j) with 1s padded on both ends while matrix chain multiplication uses the closed interval [i, j], and the boundaries and the range of k differ between them; and forgetting that the merge cost covers the whole range — merging adjacent piles costs the range sum, which needs a prefix-sum array to fetch in O(1). How this relates to other lessons: when any two piles can be merged, greedy Huffman coding is already optimal, and it is the restriction to adjacent merges that forces interval DP. Longest palindromic subsequence can also be seen as the LCS of a string and its reverse, but writing it directly as an interval state is more natural — and the memoised recursion and the table are the same thing.

03The algorithm

1. 1Define dp[i][j] as the best answer for an interval, decide whether the interval is open or closed, and pad the ends with sentinels where that helps (Burst Balloons pads with 1).
2. 2Fill in the base cases: intervals of length 1 for a closed interval, or intervals with nothing between the two ends for an open one.
3. 3Run length from small to large in the outer loop, enumerate the start i in the inner loop, and derive j.
4. 4Enumerate the split point — or the "last step" — k: dp[i][j] = best(dp[i][k] ⊕ dp[k+1][j] + merge cost). Record the winning k if you need to reconstruct the solution, and precompute costs such as a range sum with a prefix-sum array.
5. 5The answer is dp[0][n−1], and following the recorded k values recursively rebuilds the parenthesisation or the order of operations.

04Interactive demo

Burst Balloons with nums = [3, 1, 5, 8], padded at both ends with 1 to give [1, 3, 1, 5, 8, 1]. Each dp[i][j] in the table is the best score for bursting every balloon between i and j, filled shortest interval first. Each step assumes some balloon k is the last one burst inside that interval: in the row of balloons above, blue is k, yellow marks the two ends of the interval — which are exactly k's neighbours when it pops — and grey are the ones already burst by the sub-problems. In the table, blue is the cell being filled, yellow are the two sub-intervals it reads, and the small digit in the bottom-right corner records the chosen k. The final answer is dp[0][5] = 167.

05Code

Python has Burst Balloons, matrix chain multiplication with the parenthesisation reconstructed, and longest palindromic subsequence written as memoised recursion — two ways of writing the same interval state, side by side. C++ has Burst Balloons and "merge adjacent piles", where the merge cost is the whole range's sum, showing how a prefix-sum array makes that an O(1) lookup.

from functools import lru_cache


def max_coins(nums):
    """Burst Balloons: pad both ends with 1. dp[i][j] = best score for bursting everything inside (i, j)."""
    a = [1] + nums + [1]
    n = len(a)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):                    # short intervals first, so every sub-interval is ready
        for i in range(n - length):
            j = i + length
            dp[i][j] = max(dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]   # k is the last one burst
                           for k in range(i + 1, j))
    return dp[0][n - 1]


def matrix_chain(dims):
    """Matrix i is dims[i-1] × dims[i]. Returns (fewest scalar multiplications, best parenthesisation)."""
    n = len(dims) - 1
    cost = [[0] * (n + 1) for _ in range(n + 1)]
    split = [[0] * (n + 1) for _ in range(n + 1)]
    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            cost[i][j] = float("inf")
            for k in range(i, j):                 # the final multiply joins A_i..A_k with A_k+1..A_j
                c = cost[i][k] + cost[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
                if c < cost[i][j]:
                    cost[i][j], split[i][j] = c, k

    def paren(i, j):                              # rebuild the parentheses from the recorded splits
        k = split[i][j]
        return f"A{i}" if i == j else f"({paren(i, k)}{paren(k + 1, j)})"

    return cost[1][n], paren(1, n)


def longest_palindrome_subseq(s):
    """The same interval state as memoisation: the arguments are the two ends of the interval."""
    @lru_cache(maxsize=None)
    def go(i, j):
        if i > j:
            return 0
        if i == j:
            return 1
        if s[i] == s[j]:
            return go(i + 1, j - 1) + 2           # ends match, so take both into the palindrome
        return max(go(i + 1, j), go(i, j - 1))    # otherwise drop one end
    return go(0, len(s) - 1)


if __name__ == "__main__":
    print(max_coins([3, 1, 5, 8]))                # 167 (same as the interactive demo)
    print(matrix_chain([10, 30, 5, 60]))          # (4500, '((A1A2)A3)'); the other way costs 27000
    print(longest_palindrome_subseq("character")) # 5 (carac, for one)

06Practice

• LeetCode 516Longest Palindromic Subsequence (matching ends go straight in)Medium
• LeetCode 877Stone Game (a two-player game on an interval)Medium
• LeetCode 1039Minimum Score Triangulation of Polygon (enumerate the vertex that forms a triangle with the two ends)Medium
• LeetCode 312Burst Balloons (enumerate the balloon burst last)Hard
• LeetCode 1547Minimum Cost to Cut a Stick (sort the cut points and it becomes interval DP)Hard
• LeetCode 1000Minimum Cost to Merge Stones (merging K piles at a time adds a dimension to the state)Hard