Dynamic Programming • Pattern

DP on Partition (Intervals)

Learn how to solve problems where you evaluate every possible sub-interval (partition) of an array by iterating over its length.

Try Interactive Simulator

Overview

Partition DP (Interval DP) is used when the problem can be broken down into sub-problems spanning contiguous intervals `[i, j]`.

Sorting by Length

We process intervals in increasing order of their length. This guarantees that when solving `[i, j]`, all smaller intervals inside it are already solved.

Iterating the Split

For a fixed interval `[i, j]`, we try every possible split point `k`. The cost is usually the cost of the left side, the right side, plus the cost to combine them.

Key Insight

The 3 nested loops (length `len`, start `i`, and split `k`) give the classic O(N^3) time complexity. Memory is a 2D table `dp[i][j]`.

M1

M2

M3

M4

Code Tracker

:::

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

2 for (let i = 1; i <= n - len + 1; i++) {

3 let j = i + len - 1;

4 dp[i][j] = Infinity;

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

6 let cost = dp[i][k] + dp[k+1][j] + costFunc(i, k, j);

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

8 }

9 }

10}

Dp On Partition

Dp On Partition

DP on Partition (Intervals)

Overview

Sorting by Length

Iterating the Split

Key Insight

DP on Partition (Intervals)

Overview

Sorting by Length

Iterating the Split

Key Insight