Interval DP

Interval DP solves problems where each state is a contiguous range, usually written as dp[left][right].

It is common in problems about merging, splitting, parenthesizing, or choosing inside a sequence.

Core Idea

The answer for an interval depends on smaller intervals inside it. The algorithm usually fills states by increasing interval length so shorter intervals are ready before longer ones.

A transition may try every possible split point between left and right.

Function Contract

min_merge_cost(values) expects a list of non-negative merge costs or weights.

It returns the minimum total cost to merge the whole contiguous sequence when merging an interval costs the sum of values inside that interval. For an empty list, the example returns 0.

Python Example

def min_merge_cost(values):
    if not values:
        return 0
 
    n = len(values)
    prefix = [0]
    for value in values:
        prefix.append(prefix[-1] + value)
 
    dp = [[0] * n for _ in range(n)]
 
    for length in range(2, n + 1):
        for left in range(n - length + 1):
            right = left + length - 1
            total = prefix[right + 1] - prefix[left]
            dp[left][right] = min(
                dp[left][mid] + dp[mid + 1][right] + total
                for mid in range(left, right)
            )
 
    return dp[0][n - 1]

The state is a range from left to right.

Fill Order

Interval DP usually fills shorter intervals before longer intervals:

length = 1
length = 2
length = 3
continue until length = n

This order works because a long interval depends on smaller intervals inside it.

Why Split Points Appear

Many interval problems ask where the final merge, cut, or choice happens. If the final split is at mid, then the left and right subintervals become smaller subproblems.

Trying all split points is often the direct transition.

Complexity

A table with left and right has O(n^2) states. If each state tries O(n) split points, the time becomes O(n^3). Space is usually O(n^2).

Common Confusions

Interval DP is not just any 2D DP. The two indexes represent boundaries of the same interval.

The fill order matters. Longer intervals depend on shorter intervals.

Another common mistake is using interval DP for non-contiguous choices. Interval DP is specifically about continuous ranges.

When To Use It

Use interval DP when a problem repeatedly combines or splits contiguous parts of a sequence.

Do not use it when the natural subproblem is a prefix, subset, or graph state rather than a range.

The Main Point

Interval DP is for contiguous ranges whose answers depend on smaller contiguous ranges inside them.