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.
Python Example
def min_merge_cost(values):
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.
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.
When To Use It
Use interval DP when a problem repeatedly combines or splits contiguous parts of a sequence.