Interval / Range DP

Suppose you need to multiply a chain of matrices together. Matrix multiplication is associative (you can parenthesize any way you like), but the order of multiplication dramatically affects the total cost. Multiply a $10 \times 30$ matrix by a $30 \times 5$ matrix and you do 1,500 scalar multiplications. But in a chain of three or more matrices, different parenthesizations can differ by orders of magnitude. A greedy approach, always multiplying the cheapest pair first, does not work, because a locally cheap multiplication can force an expensive one later. You need to consider every possible way to split the chain, and that is exactly what interval DP does.

The framework

Interval DP solves problems where the answer for a large range depends on the answers for smaller sub-ranges within it. The state is dp[i][j], representing the optimal answer for the subproblem defined on the contiguous range [i, j]. To compute dp[i][j], you try every possible split point k that divides the range into two smaller pieces, [i, k] and [k+1, j], and combine their answers with whatever cost is incurred at the split.

The critical detail is the iteration order. You cannot compute dp[i][j] until you have already computed dp[i][k] and dp[k+1][j] for every valid k. Since those are shorter intervals, you must iterate by increasing interval length. Start with intervals of length 1 (the base cases), then length 2, then length 3, and so on up to the full range. This guarantees that every subproblem is ready when you need it.

def interval_dp(arr):
    n = len(arr)
    dp = [[0] * n for _ in range(n)]

    # base cases: intervals of length 1
    # (often dp[i][i] = 0 or some initial value)

    for length in range(2, n + 1):          # interval length
        for i in range(n - length + 1):     # start of interval
            j = i + length - 1              # end of interval
            dp[i][j] = float('inf')
            for k in range(i, j):           # split point
                dp[i][j] = min(dp[i][j],
                    dp[i][k] + dp[k+1][j] + cost(i, k, j))
    return dp[0][n - 1]

Three nested loops: the outer loop over interval length, the middle loop over starting position, and the inner loop over split point. This gives the characteristic $O(n^3)$ time complexity of interval DP.

Matrix chain multiplication

The classic interval DP problem. You have matrices $A_1, A_2, \ldots, A_n$ where matrix $A_i$ has dimensions p[i-1] x p[i]. You want to find the parenthesization that minimizes the total number of scalar multiplications.

Define dp[i][j] as the minimum cost to multiply matrices i through j. The base case is dp[i][i] = 0: a single matrix requires no multiplication. For a longer chain, you try every split point k: multiply [i..k] into one result, multiply [k+1..j] into another, then multiply those two results together. The cost of that final multiplication is p[i-1] * p[k] * p[j], because the left result is p[i-1] x p[k] and the right result is p[k] x p[j].

Let us walk through a small example. Suppose we have four matrices with dimensions given by p = [10, 30, 5, 60]. This means $A_1$ is $10 \times 30$, $A_2$ is $30 \times 5$, and $A_3$ is $5 \times 60$.

Base cases: dp[1][1] = dp[2][2] = dp[3][3] = 0.

Length 2 intervals:

• dp[1][2]: only one split at k=1. Cost = dp[1][1] + dp[2][2] + 10*30*5 = 1500.
• dp[2][3]: only one split at k=2. Cost = dp[2][2] + dp[3][3] + 30*5*60 = 9000.

Length 3 interval:

• dp[1][3]: try k=1 and k=2.
• k=1: dp[1][1] + dp[2][3] + 10*30*60 = 0 + 9000 + 18000 = 27000.
• k=2: dp[1][2] + dp[3][3] + 10*5*60 = 1500 + 0 + 3000 = 4500.
• Minimum is 4500.

The optimal strategy is to first multiply A1 and A2 (cost 1500, producing a $10 \times 5$ matrix), then multiply that result by A3 (cost 3000). Total: 4500. The other parenthesization would cost 27000, six times worse. This is why greedy does not work: the cheapest first step (still 1500 for A1*A2) happens to also be the right choice here, but in general, a cheap first step can leave you with an expensive matrix shape for later multiplications.

Burst Balloons

Consider LeetCode 312. Burst Balloons: given an array of balloons with values, burst them one at a time. When you burst balloon i, you gain nums[i-1] * nums[i] * nums[i+1] coins (using the adjacent balloons that have not yet been burst). Find the maximum coins you can collect.

The naive approach, thinking about which balloon to burst first, leads to a mess. Once you burst a balloon, the neighbors change, so the subproblems are not independent. The trick is to think backwards: instead of asking which balloon to burst first, ask which balloon to burst last in the interval [i, j].

If balloon k is the last one burst in the interval [i, j], then at the moment you burst it, all other balloons in [i, j] are already gone. The only neighbors of k that remain are the boundaries outside the interval: nums[i-1] and nums[j+1]. So bursting k last gives you nums[i-1] * nums[k] * nums[j+1] coins, plus the coins from optimally bursting everything in [i, k-1] and [k+1, j].

This reframing makes the subproblems independent. The left and right sub-intervals do not interact because k still exists as a boundary between them until the very end:

def maxCoins(nums):
    nums = [1] + nums + [1]  # add boundary balloons
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    for length in range(1, n - 1):
        for i in range(1, n - length):
            j = i + length - 1
            for k in range(i, j + 1):  # k is the LAST balloon burst
                coins = nums[i-1] * nums[k] * nums[j+1]
                coins += dp[i][k-1] + dp[k+1][j]
                dp[i][j] = max(dp[i][j], coins)
    return dp[1][n - 2]

The insight of "think about what happens last, not first" comes up repeatedly in interval DP. It turns dependent subproblems into independent ones.

Stone merge

Another classic: you have n piles of stones in a row. In each move, you merge two adjacent piles, paying a cost equal to the total number of stones in the merged pile. Find the minimum total cost to merge all piles into one.

This maps directly onto interval DP. Define dp[i][j] as the minimum cost to merge piles i through j into a single pile. When you split at k, you pay the cost to merge [i, k] plus the cost to merge [k+1, j], plus the cost of the final merge which combines the two resulting piles. That final merge costs sum(stones[i..j]) because the resulting pile contains all stones from i to j regardless of how you got there.

def mergeStones(stones):
    n = len(stones)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + stones[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
            dp[i][j] = float('inf')
            for k in range(i, j):
                dp[i][j] = min(dp[i][j],
                    dp[i][k] + dp[k+1][j] + prefix[j+1] - prefix[i])
    return dp[0][n - 1]

The prefix sum array lets us compute sum(stones[i..j]) in $O(1)$, keeping the overall time at $O(n^3)$.

A harder variant is "minimum cost to merge stones into K piles at a time" (LeetCode 1000), where each move merges exactly K adjacent piles. The interval DP still applies, but you need an extra dimension or careful stepping in the split-point loop.

Why $O(n^3)$ and can we do better?

The three nested loops, over length, start position, and split point, each run up to $O(n)$ iterations, giving $O(n^3)$ time. The DP table itself is $O(n^2)$ space.

For the general interval DP problem, $O(n^3)$ is essentially tight. However, for specific problems with additional structure, optimizations exist. The Knuth optimization applies when the optimal split point k for dp[i][j] is monotone. That is, the optimal k for dp[i][j] is between the optimal k for dp[i][j-1] and dp[i+1][j]. When this condition holds, you can narrow the range of k values you try, reducing the total time to $O(n^2)$. Matrix chain multiplication and stone merge both satisfy this condition, though proving it requires verifying the quadrangle inequality on the cost function.

Complexity

Time complexity is $O(n^3)$ for the standard interval DP framework: three nested loops each bounded by n. Space is $O(n^2)$ for the 2D DP table. With the Knuth optimization, time drops to $O(n^2)$ for problems that satisfy the quadrangle inequality, while space remains $O(n^2)$.

Recognizing this pattern

You're probably looking at interval/range DP when:

• The problem operates on a contiguous range and you must pick some order of operations within it: merging, splitting, bursting, parenthesizing.
• The natural subproblem is "best answer for range [i, j]" with a split point k inside it.
• The cost of combining two sub-ranges depends on global properties of those ranges (sum, boundary values), not just on the index.
• Constraints are roughly $n \le 500$: large enough to forbid exponential search, small enough for $O(n^3)$.

Common templates:

• Min-cost split: dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + cost(i, j). Example: Minimum Cost to Merge Stones.
• Pick-last-element framing: flip the recursion so the last operation in [i, j] happens at some k, with boundary multipliers. Example: Burst Balloons.
• Parenthesization / matrix chain: choose where to place the outermost operator. Example: Minimum Score Triangulation of Polygon.
• Two-player range game: dp[i][j] is the current player's score advantage on range [i, j]. Example: Stone Game.
• Min insertions / removals on a range: interval recurrence matching endpoints. Example: Strange Printer.