Dynamic Programming • Patterns

Interval DP

A structural pattern for solving problems where the solution for an interval [i, j] depends on breaking it down into smaller sub-intervals.

Try Interactive Simulator

Overview

Interval DP is used when you can merge adjacent items. The cost of merging a large interval depends on where you split it into two smaller chunks.

Length Iteration

Unlike linear DP, we don't iterate `i` from 0 to N. We iterate over the LENGTH of the interval, from 2 to N, because larger intervals depend on smaller ones.

The K Split

For a fixed interval `[i, j]`, we test every possible split point `k`. We combine the optimal answer for `[i, k]` and `[k+1, j]`.

Use Cases

Classic problems include Matrix Chain Multiplication, Burst Balloons, Minimum Cost to Merge Stones, and Optimal Binary Search Trees.

A[0]

A[1]

A[2]

A[3]

[0,0]	[0,1]	[0,2]	[0,3]
	[1,1]	[1,2]	[1,3]
		[2,2]	[2,3]
			[3,3]

Code Tracker

:::

1for (let i = 0; i < n; i++) {

2 dp[i][i] = 0; // Base cases

3}

4for (let len = 2; len <= n; len++) {

5 for (let i = 0; i <= n - len; i++) {

6 let j = i + len - 1;

7 dp[i][j] = Infinity;

8 for (let k = i; k < j; k++) {

9 let cost = dp[i][k] + dp[k+1][j] + mergeCost(i, k, j);

10 dp[i][j] = Math.min(dp[i][j], cost);

11 }

12 }

13}

Interval Dp

Interval Dp

Interval DP

Overview

Length Iteration

The K Split

Use Cases

Interval DP

Overview

Length Iteration

The K Split

Use Cases