Interval DP, also called Range DP, is used when the problem is about a continuous range of an array or string.

Instead of asking:

“What is the answer up to index i?”

we ask:

“What is the answer for the range [i...j]?”

The main idea is:

Solve smaller ranges → try every split → combine them → solve bigger ranges.

Pattern Table

Pattern	Typical Question	Main Idea
Matrix Chain Multiplication	Minimum multiplication cost	Try every split
Burst Balloons	Maximum coins	Choose last balloon
Cut Stick	Minimum cutting cost	Try every cut
Merge Stones	Minimum merge cost	Merge smaller ranges
Palindrome Partitioning	Minimum cuts	Try every partition
Optimal BST	Minimum search cost	Try every root
Strange Printer	Minimum turns	Merge matching characters
Remove Boxes	Maximum points	Interval + extra state

Mental Trigger

“Range [i...j] + split/partition + smaller ranges” → Interval DP

1. Generic Interval DP Template (Base)

This is the main template to understand.

public int intervalDP(int[] arr) {
    int n = arr.length;

    int[][] dp = new int[n][n];

    // length = current interval length
    for (int length = 2; length <= n; length++) {

        for (int i = 0; i + length - 1 < n; i++) {

            int j = i + length - 1;

            dp[i][j] = Integer.MAX_VALUE;

            // Try every split
            for (int k = i; k < j; k++) {

                int cost =
                    dp[i][k]
                    + dp[k + 1][j]
                    + extraCost(i, k, j);

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

    return dp[0][n - 1];
}

def interval_dp(arr):
    n = len(arr)

    dp = [[0] * n for _ in range(n)]

    # length = current interval length
    for length in range(2, n + 1):

        for i in range(0, n - length + 1):

            j = i + length - 1

            dp[i][j] = float('inf')

            # Try every split
            for k in range(i, j):

                cost = (
                    dp[i][k]
                    + dp[k + 1][j]
                    + extra_cost(i, k, j)
                )

                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]

int intervalDP(vector<int>& arr) {
    int n = arr.size();

    vector<vector<int>> dp(n, vector<int>(n));

    // length = current interval length
    for (int length = 2; length <= n; length++) {

        for (int i = 0; i + length - 1 < n; i++) {

            int j = i + length - 1;

            dp[i][j] = INT_MAX;

            // Try every split
            for (int k = i; k < j; k++) {

                int cost = dp[i][k]
                    + dp[k + 1][j]
                    + extraCost(i, k, j);

                dp[i][j] =
                    min(dp[i][j], cost);
            }
        }
    }

    return dp[0][n - 1];
}

function intervalDP(arr) {
  const n = arr.length;

  const dp = Array.from({ length: n }, () =>
    new Array(n).fill(0)
  );

  // length = current interval length
  for (let length = 2; length <= n; length++) {
    for (let i = 0; i + length - 1 < n; i++) {
      const j = i + length - 1;

      dp[i][j] = Infinity;

      // Try every split
      for (let k = i; k < j; k++) {
        const cost =
          dp[i][k] +
          dp[k + 1][j] +
          extraCost(i, k, j);

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

  return dp[0][n - 1];
}

What Does `dp[i][j]` Mean?

dp[i][j]

means:

Answer for the range from i to j.

Example:

Array:

0   1   2   3   4
A   B   C   D   E

dp[1][3]

means:

B C D

The Most Important Part

For every range:

for (int k = i; k < j; k++)

we try:

[i ... k] | [k+1 ... j]

Example:

A B C D

Possible splits:

A | B C D

A B | C D

A B C | D

Interval DP = dp[i][j] + try every split k.

Pattern 1: Matrix Chain Multiplication (MCM)

Problem Type

Given matrices, find the minimum number of multiplications.

Example:

A × B × C × D

Different parenthesizations have different costs.

Mental Trigger

“Different ways to parenthesize” → MCM

Java Code

public int matrixChain(int[] p) {
    int n = p.length - 1;

    int[][] dp = new int[n][n];

    for (int length = 2; length <= n; length++) {

        for (int i = 0; i + length - 1 < n; i++) {

            int j = i + length - 1;

            dp[i][j] = Integer.MAX_VALUE;

            for (int k = i; k < j; k++) {

                int cost =
                    dp[i][k]
                    + dp[k + 1][j]
                    + p[i] * p[k + 1] * p[j + 1];

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

    return dp[0][n - 1];
}

def matrix_chain(p):
    n = len(p) - 1

    dp = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):

        for i in range(0, n - length + 1):

            j = i + length - 1

            dp[i][j] = float('inf')

            for k in range(i, j):

                cost = (
                    dp[i][k]
                    + dp[k + 1][j]
                    + p[i] * p[k + 1] * p[j + 1]
                )

                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]

int matrixChain(vector<int>& p) {
    int n = p.size() - 1;

    vector<vector<int>> dp(n, vector<int>(n));

    for (int length = 2; length <= n; length++) {

        for (int i = 0; i + length - 1 < n; i++) {

            int j = i + length - 1;

            dp[i][j] = INT_MAX;

            for (int k = i; k < j; k++) {

                int cost = dp[i][k]
                    + dp[k + 1][j]
                    + p[i] * p[k + 1] * p[j + 1];

                dp[i][j] =
                    min(dp[i][j], cost);
            }
        }
    }

    return dp[0][n - 1];
}

function matrixChain(p) {
  const n = p.length - 1;

  const dp = Array.from({ length: n }, () =>
    new Array(n).fill(0)
  );

  for (let length = 2; length <= n; length++) {
    for (let i = 0; i + length - 1 < n; i++) {
      const j = i + length - 1;

      dp[i][j] = Infinity;

      for (let k = i; k < j; k++) {
        const cost =
          dp[i][k] +
          dp[k + 1][j] +
          p[i] * p[k + 1] * p[j + 1];

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

  return dp[0][n - 1];
}

Matrix Chain Multiplication

Find the parenthesization that minimizes scalar multiplications for a chain of matrices.

dp[i][j] = min over split k of dp[i][k] + dp[k+1][j] + p[i-1]·p[k]·p[j]. Fill by increasing interval length so smaller subchains are ready first. O(n³); the answer is dp[1][n] and the split point tells you where to cut.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        for len in 2..n:
                      
                        2
                          for i in 1..n-len+1:
                      
                        3
                            j = i + len - 1
                      
                        4
                            dp[i][j] = min over k in i..j-1 of
                      
                        5
                              dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]
                      
                        6
                        return dp[1][n]

What Changed from the Base?

Base:

dp[i][k]
+ dp[k + 1][j]
+ extraCost

MCM uses:

p[i] * p[k + 1] * p[j + 1]

because multiplying:

left matrix × right matrix

has a specific multiplication cost.

MCM = Interval DP + Try every parenthesization.

Pattern 2: Burst Balloons

Problem Type

Burst balloons to maximize coins.

The important trick:

Think about which balloon is burst LAST.

Why?

If k is the last balloon in [i...j], then the balloons on the left and right are already gone.

Mental Trigger

“Removal order changes the answer” → Think about the last operation.

Java Code

public int maxCoins(int[] nums) {

    int n = nums.length;

    int[] a = new int[n + 2];

    a[0] = 1;
    a[n + 1] = 1;

    for (int i = 0; i < n; i++) {
        a[i + 1] = nums[i];
    }

    int[][] dp = new int[n + 2][n + 2];

    for (int length = 1; length <= n; length++) {

        for (int i = 1; i + length - 1 <= n; i++) {

            int j = i + length - 1;

            for (int k = i; k <= j; k++) {

                int coins =
                    dp[i][k - 1]
                    + dp[k + 1][j]
                    + a[i - 1] * a[k] * a[j + 1];

                dp[i][j] =
                    Math.max(dp[i][j], coins);
            }
        }
    }

    return dp[1][n];
}

def max_coins(nums):
    n = len(nums)

    a = [1] * (n + 2)

    for i in range(n):
        a[i + 1] = nums[i]

    dp = [[0] * (n + 2) for _ in range(n + 2)]

    for length in range(1, n + 1):

        for i in range(1, n - length + 2):

            j = i + length - 1

            for k in range(i, j + 1):

                coins = (
                    dp[i][k - 1]
                    + dp[k + 1][j]
                    + a[i - 1] * a[k] * a[j + 1]
                )

                dp[i][j] = max(dp[i][j], coins)

    return dp[1][n]

int maxCoins(vector<int>& nums) {

    int n = nums.size();

    vector<int> a(n + 2, 1);

    for (int i = 0; i < n; i++) {
        a[i + 1] = nums[i];
    }

    vector<vector<int>> dp(
        n + 2, vector<int>(n + 2));

    for (int length = 1; length <= n; length++) {

        for (int i = 1; i + length - 1 <= n; i++) {

            int j = i + length - 1;

            for (int k = i; k <= j; k++) {

                int coins = dp[i][k - 1]
                    + dp[k + 1][j]
                    + a[i - 1] * a[k] * a[j + 1];

                dp[i][j] =
                    max(dp[i][j], coins);
            }
        }
    }

    return dp[1][n];
}

function maxCoins(nums) {
  const n = nums.length;

  const a = new Array(n + 2).fill(1);

  for (let i = 0; i < n; i++) {
    a[i + 1] = nums[i];
  }

  const dp = Array.from({ length: n + 2 }, () =>
    new Array(n + 2).fill(0)
  );

  for (let length = 1; length <= n; length++) {
    for (let i = 1; i + length - 1 <= n; i++) {
      const j = i + length - 1;

      for (let k = i; k <= j; k++) {
        const coins =
          dp[i][k - 1] +
          dp[k + 1][j] +
          a[i - 1] * a[k] * a[j + 1];

        dp[i][j] = Math.max(dp[i][j], coins);
      }
    }
  }

  return dp[1][n];
}

Burst Balloons (Interval DP)

Compute the maximum coins from bursting balloons i..j using interval DP.

Build dp[i][j] bottom-up: for each interval pick the last balloon k to burst, scoring nums[i-1]*nums[k]*nums[j+1] plus the already-solved subintervals dp[i][k-1] and dp[k+1][j]. Padding the array with 1s at both ends handles the edges. O(n³) time, O(n²) space.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[i][j] = max score bursting balloons i..j
                      
                        2
                        for len in 1..n:
                      
                        3
                          for i in 1..n-len+1:
                      
                        4
                            j = i + len - 1
                      
                        5
                            dp[i][j] = max over k in i..j of
                      
                        6
                              dp[i][k-1] + dp[k+1][j] + nums[i-1]*nums[k]*nums[j+1]
                      
                        7
                        return dp[1][n]

What Changed from the Base?

Base:

Math.min(...)

Burst Balloons:

Math.max(...)

because we want maximum coins.

Also, instead of thinking:

Which balloon should I burst first?

we think:

Which balloon should I burst last?

Burst Balloons = Interval DP + choose the last operation.

Pattern 3: Minimum Cost to Cut a Stick

Minimum Cost to Cut a Stick

Cut a stick at given positions with minimum total cost.

Cost to cut a segment = its length, plus cost of cutting the two resulting pieces. dp[i][j] = min over an internal cut k of (length + dp[i][k] + dp[k][j]). Solve short intervals first. O(n³) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        add 0 and n to cuts -> pts
                      
                        2
                        for len in 2..m:
                      
                        3
                          for i in 0..m-len:
                      
                        4
                            j = i + len
                      
                        5
                            dp[i][j] = min_k( pts[j]-pts[i] + dp[i][k] + dp[k][j] )
                      
                        6
                        return dp[0][m]

Problem Type

A stick has several possible cut positions.

Every cut costs the current length of the stick.

We need the minimum total cost.

Mental Trigger

“Cut a range” + “minimum cost” → Interval DP

Java Code

public int minCost(int n, int[] cuts) {

    int m = cuts.length;

    int[] c = new int[m + 2];

    for (int i = 0; i < m; i++) {
        c[i + 1] = cuts[i];
    }

    c[0] = 0;
    c[m + 1] = n;

    Arrays.sort(c);

    int[][] dp = new int[m + 2][m + 2];

    for (int length = 2; length <= m + 1; length++) {

        for (int i = 0;
             i + length < m + 2;
             i++) {

            int j = i + length;

            dp[i][j] = Integer.MAX_VALUE;

            for (int k = i + 1; k < j; k++) {

                int cost =
                    dp[i][k]
                    + dp[k][j]
                    + (c[j] - c[i]);

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

    return dp[0][m + 1];
}

def min_cost(n, cuts):
    m = len(cuts)

    c = [0] * (m + 2)

    for i in range(m):
        c[i + 1] = cuts[i]

    c[0] = 0
    c[m + 1] = n

    c.sort()

    dp = [[0] * (m + 2) for _ in range(m + 2)]

    for length in range(2, m + 2):

        for i in range(0, m + 2 - length):

            j = i + length

            dp[i][j] = float('inf')

            for k in range(i + 1, j):

                cost = (
                    dp[i][k]
                    + dp[k][j]
                    + (c[j] - c[i])
                )

                dp[i][j] = min(dp[i][j], cost)

    return dp[0][m + 1]

int minCost(int n, vector<int>& cuts) {

    int m = cuts.size();

    vector<int> c(m + 2);

    for (int i = 0; i < m; i++) {
        c[i + 1] = cuts[i];
    }

    c[0] = 0;
    c[m + 1] = n;

    sort(c.begin(), c.end());

    vector<vector<int>> dp(
        m + 2, vector<int>(m + 2));

    for (int length = 2; length <= m + 1; length++) {

        for (int i = 0;
             i + length < m + 2;
             i++) {

            int j = i + length;

            dp[i][j] = INT_MAX;

            for (int k = i + 1; k < j; k++) {

                int cost = dp[i][k]
                    + dp[k][j]
                    + (c[j] - c[i]);

                dp[i][j] =
                    min(dp[i][j], cost);
            }
        }
    }

    return dp[0][m + 1];
}

function minCost(n, cuts) {
  const m = cuts.length;

  const c = new Array(m + 2);

  for (let i = 0; i < m; i++) {
    c[i + 1] = cuts[i];
  }

  c[0] = 0;
  c[m + 1] = n;

  c.sort((x, y) => x - y);

  const dp = Array.from({ length: m + 2 }, () =>
    new Array(m + 2).fill(0)
  );

  for (let length = 2; length <= m + 1; length++) {
    for (let i = 0; i + length < m + 2; i++) {
      const j = i + length;

      dp[i][j] = Infinity;

      for (let k = i + 1; k < j; k++) {
        const cost =
          dp[i][k] +
          dp[k][j] +
          (c[j] - c[i]);

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

  return dp[0][m + 1];
}

What Changed from the Base?

Base:

extraCost(i, k, j)

becomes:

c[j] - c[i]

because the cost of making a cut is the current segment length.

Cut Stick = Try every cut inside the range.

Pattern 4: Merge Stones

Merge Stones (Min Cost)

Merge adjacent piles until one remains, minimizing total cost.

dp[i][j] = min cost to merge piles i..j into one. Cost = sum of the range + best split into left/right merges. Use prefix sums for the range total. O(n³) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        ps = prefix sums of piles
                      
                        2
                        for len in 2..n:
                      
                        3
                          for i in 0..n-len:
                      
                        4
                            j = i + len - 1
                      
                        5
                            dp[i][j] = INF
                      
                        6
                            for k in i..j-1: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])
                      
                        7
                            dp[i][j] += ps[j+1] - ps[i]
                      
                        8
                        return dp[0][n-1]

Problem Type

Merge adjacent piles with minimum total cost.

Example:

[3, 2, 4, 1]

Mental Trigger

“Merge adjacent groups” → Interval DP

Java Code

public int mergeStones(int[] stones) {

    int n = stones.length;

    int[][] dp = new int[n][n];

    int[] prefix = new int[n + 1];

    for (int i = 0; i < n; i++) {
        prefix[i + 1] =
            prefix[i] + stones[i];
    }

    for (int length = 2; length <= n; length++) {

        for (int i = 0;
             i + length - 1 < n;
             i++) {

            int j = i + length - 1;

            dp[i][j] = Integer.MAX_VALUE;

            for (int k = i; k < j; k++) {

                int cost =
                    dp[i][k]
                    + dp[k + 1][j]
                    + prefix[j + 1] - prefix[i];

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

    return dp[0][n - 1];
}

def merge_stones(stones):
    n = len(stones)

    dp = [[0] * n for _ in range(n)]

    prefix = [0] * (n + 1)

    for i in range(n):
        prefix[i + 1] = (
            prefix[i] + stones[i]
        )

    for length in range(2, n + 1):

        for i in range(0, n - length + 1):

            j = i + length - 1

            dp[i][j] = float('inf')

            for k in range(i, j):

                cost = (
                    dp[i][k]
                    + dp[k + 1][j]
                    + prefix[j + 1] - prefix[i]
                )

                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]

int mergeStones(vector<int>& stones) {

    int n = stones.size();

    vector<vector<int>> dp(n, vector<int>(n));

    vector<int> prefix(n + 1, 0);

    for (int i = 0; i < n; i++) {
        prefix[i + 1] =
            prefix[i] + stones[i];
    }

    for (int length = 2; length <= n; length++) {

        for (int i = 0;
             i + length - 1 < n;
             i++) {

            int j = i + length - 1;

            dp[i][j] = INT_MAX;

            for (int k = i; k < j; k++) {

                int cost = dp[i][k]
                    + dp[k + 1][j]
                    + prefix[j + 1] - prefix[i];

                dp[i][j] =
                    min(dp[i][j], cost);
            }
        }
    }

    return dp[0][n - 1];
}

function mergeStones(stones) {
  const n = stones.length;

  const dp = Array.from({ length: n }, () =>
    new Array(n).fill(0)
  );

  const prefix = new Array(n + 1).fill(0);

  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + stones[i];
  }

  for (let length = 2; length <= n; length++) {
    for (let i = 0; i + length - 1 < n; i++) {
      const j = i + length - 1;

      dp[i][j] = Infinity;

      for (let k = i; k < j; k++) {
        const cost =
          dp[i][k] +
          dp[k + 1][j] +
          (prefix[j + 1] - prefix[i]);

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

  return dp[0][n - 1];
}

Note: the classic LeetCode Merge Stones problem has an additional feasibility condition and can require a 3D DP. The above is the simpler adjacent-merge formulation.

What Changed from the Base?

Added prefix sums:

prefix[j + 1] - prefix[i]

to quickly calculate the sum of the current interval.

Merge Stones = Smaller interval costs + cost of merging the whole range.

Pattern 5: Palindrome Partitioning

Palindrome Partitioning

Cut a string into all combinations of palindromic pieces.

At each position try every prefix; keep it only if it is a palindrome, then recurse on the remainder. Non-palindrome prefixes die immediately, pruning the exponential tree. The valid partitions that reach the end are the answers.

TREE VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        partition(start, path):
                      
                        2
                          if start == len(s): output path
                      
                        3
                          for end in start+1 .. len(s):
                      
                        4
                            prefix = s[start:end]
                      
                        5
                            if isPalindrome(prefix):
                      
                        6
                              partition(end, path + [prefix])

There are two common versions, so keep them separate.

Version A: Minimum Cuts

Problem Type

Split a string into the minimum number of palindrome pieces.

Example:

aab

Answer:

aa | b

Minimum cuts:

Mental Trigger

“Minimum cuts” + “palindrome” → Partition DP

Java Code

public int minCut(String s) {

    int n = s.length();

    boolean[][] palindrome =
        new boolean[n][n];

    for (int i = n - 1; i >= 0; i--) {

        for (int j = i; j < n; j++) {

            if (s.charAt(i) == s.charAt(j)
                && (j - i <= 2 ||
                    palindrome[i + 1][j - 1])) {

                palindrome[i][j] = true;
            }
        }
    }

    int[] dp = new int[n];

    Arrays.fill(dp, Integer.MAX_VALUE);

    for (int i = 0; i < n; i++) {

        if (palindrome[0][i]) {
            dp[i] = 0;
            continue;
        }

        for (int j = 0; j < i; j++) {

            if (palindrome[j + 1][i]) {

                dp[i] = Math.min(
                    dp[i],
                    dp[j] + 1
                );
            }
        }
    }

    return dp[n - 1];
}

def min_cut(s):
    n = len(s)

    palindrome = [
        [False] * n for _ in range(n)
    ]

    for i in range(n - 1, -1, -1):

        for j in range(i, n):

            if s[i] == s[j] and (
                j - i <= 2
                or palindrome[i + 1][j - 1]
            ):
                palindrome[i][j] = True

    dp = [float('inf')] * n

    for i in range(n):

        if palindrome[0][i]:
            dp[i] = 0
            continue

        for j in range(i):

            if palindrome[j + 1][i]:
                dp[i] = min(
                    dp[i],
                    dp[j] + 1
                )

    return dp[n - 1]

int minCut(string& s) {

    int n = s.size();

    vector<vector<bool>> palindrome(
        n, vector<bool>(n));

    for (int i = n - 1; i >= 0; i--) {

        for (int j = i; j < n; j++) {

            if (s[i] == s[j]
                && (j - i <= 2 ||
                    palindrome[i + 1][j - 1])) {

                palindrome[i][j] = true;
            }
        }
    }

    vector<int> dp(n, INT_MAX);

    for (int i = 0; i < n; i++) {

        if (palindrome[0][i]) {
            dp[i] = 0;
            continue;
        }

        for (int j = 0; j < i; j++) {

            if (palindrome[j + 1][i]) {

                dp[i] = min(
                    dp[i],
                    dp[j] + 1
                );
            }
        }
    }

    return dp[n - 1];
}

function minCut(s) {
  const n = s.length;

  const palindrome = Array.from(
    { length: n },
    () => new Array(n).fill(false)
  );

  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      if (
        s[i] === s[j] &&
        (j - i <= 2 || palindrome[i + 1][j - 1])
      ) {
        palindrome[i][j] = true;
      }
    }
  }

  const dp = new Array(n).fill(Infinity);

  for (let i = 0; i < n; i++) {
    if (palindrome[0][i]) {
      dp[i] = 0;
      continue;
    }

    for (let j = 0; j < i; j++) {
      if (palindrome[j + 1][i]) {
        dp[i] = Math.min(dp[i], dp[j] + 1);
      }
    }
  }

  return dp[n - 1];
}

What Changed from Base?

Instead of directly using:

dp[i][j]

we first calculate:

palindrome[i][j]

to know whether a range is a palindrome.

Then we use a 1D partition DP for the minimum cuts.

Palindrome Partitioning = Check palindrome ranges + try partition points.

Pattern 6: Optimal Binary Search Tree

Optimal Binary Search Tree

Build a BST with minimum expected search cost.

dp[i][j] = min cost BST from keys i..j. Cost = sum of frequencies in the range + best root's (left cost + right cost). Try every key as root. O(n³) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        freqSum(i,j) = sum of freqs i..j
                      
                        2
                        dp[i][i] = freq[i]
                      
                        3
                        for len in 2..n:
                      
                        4
                          for i in 0..n-len:
                      
                        5
                            j = i + len - 1
                      
                        6
                            dp[i][j] = min_k( freqSum(i,j) + dp[i][k-1] + dp[k+1][j] )
                      
                        7
                        return dp[0][n-1]

Problem Type

Choose the root that gives minimum search cost.

Mental Trigger

“Choose a root from a range” → Interval DP

Java Code

public int optimalBST(int[] freq) {

    int n = freq.length;

    int[][] dp = new int[n][n];

    int[] prefix = new int[n + 1];

    for (int i = 0; i < n; i++) {
        prefix[i + 1] =
            prefix[i] + freq[i];
    }

    for (int length = 1; length <= n; length++) {

        for (int i = 0;
             i + length - 1 < n;
             i++) {

            int j = i + length - 1;

            dp[i][j] = Integer.MAX_VALUE;

            int total =
                prefix[j + 1] - prefix[i];

            for (int root = i; root <= j; root++) {

                int left =
                    root > i ? dp[i][root - 1] : 0;

                int right =
                    root < j ? dp[root + 1][j] : 0;

                dp[i][j] =
                    Math.min(
                        dp[i][j],
                        left + right + total
                    );
            }
        }
    }

    return dp[0][n - 1];
}

def optimal_bst(freq):
    n = len(freq)

    dp = [[0] * n for _ in range(n)]

    prefix = [0] * (n + 1)

    for i in range(n):
        prefix[i + 1] = (
            prefix[i] + freq[i]
        )

    for length in range(1, n + 1):

        for i in range(0, n - length + 1):

            j = i + length - 1

            dp[i][j] = float('inf')

            total = (
                prefix[j + 1] - prefix[i]
            )

            for root in range(i, j + 1):

                left = (
                    dp[i][root - 1] if root > i else 0
                )

                right = (
                    dp[root + 1][j] if root < j else 0
                )

                dp[i][j] = min(
                    dp[i][j],
                    left + right + total
                )

    return dp[0][n - 1]

int optimalBST(vector<int>& freq) {

    int n = freq.size();

    vector<vector<int>> dp(n, vector<int>(n));

    vector<int> prefix(n + 1, 0);

    for (int i = 0; i < n; i++) {
        prefix[i + 1] =
            prefix[i] + freq[i];
    }

    for (int length = 1; length <= n; length++) {

        for (int i = 0;
             i + length - 1 < n;
             i++) {

            int j = i + length - 1;

            dp[i][j] = INT_MAX;

            int total = prefix[j + 1] - prefix[i];

            for (int root = i; root <= j; root++) {

                int left = root > i ? dp[i][root - 1] : 0;

                int right = root < j ? dp[root + 1][j] : 0;

                dp[i][j] =
                    min(
                        dp[i][j],
                        left + right + total
                    );
            }
        }
    }

    return dp[0][n - 1];
}

function optimalBST(freq) {
  const n = freq.length;

  const dp = Array.from({ length: n }, () =>
    new Array(n).fill(0)
  );

  const prefix = new Array(n + 1).fill(0);

  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + freq[i];
  }

  for (let length = 1; length <= n; length++) {
    for (let i = 0; i + length - 1 < n; i++) {
      const j = i + length - 1;

      dp[i][j] = Infinity;

      const total = prefix[j + 1] - prefix[i];

      for (let root = i; root <= j; root++) {
        const left =
          root > i ? dp[i][root - 1] : 0;

        const right =
          root < j ? dp[root + 1][j] : 0;

        dp[i][j] = Math.min(
          dp[i][j],
          left + right + total
        );
      }
    }
  }

  return dp[0][n - 1];
}

What Changed from Base?

The split point is now:

root

instead of a generic k.

We try every possible root:

for (int root = i; root <= j; root++)

Optimal BST = Interval DP + Try every possible root.

Pattern 7: Strange Printer

Strange Printer

Minimum turns to print a string (one char per range, last write wins).

dp[i][j] = min turns for s[i..j]. Skip duplicate leading chars. Try every split k, but if s[k]==s[j] we can merge k into the last-printed segment. O(n³) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[i][i] = 1
                      
                        2
                        for len in 2..n:
                      
                        3
                          for i in 0..n-len:
                      
                        4
                            j = i + len - 1
                      
                        5
                            dp[i][j] = 1 + dp[i+1][j]   // print s[i] separately
                      
                        6
                            for k in i+1..j-1:
                      
                        7
                              if s[k] == s[j]: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j-1])
                      
                        8
                        return dp[0][n-1]

Problem Type

A printer can print a sequence of the same character in one turn.

We want the minimum number of turns.

Mental Trigger

“Print a range” + “same characters can merge” → Interval DP

Java Code

public int strangePrinter(String s) {

    int n = s.length();

    int[][] dp = new int[n][n];

    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    for (int length = 2; length <= n; length++) {

        for (int i = 0;
             i + length - 1 < n;
             i++) {

            int j = i + length - 1;

            dp[i][j] =
                dp[i + 1][j] + 1;

            for (int k = i + 1; k <= j; k++) {

                if (s.charAt(i) == s.charAt(k)) {

                    int middle =
                        k == i + 1
                        ? 0
                        : dp[i + 1][k - 1];

                    dp[i][j] = Math.min(
                        dp[i][j],
                        middle + dp[k][j]
                    );
                }
            }
        }
    }

    return dp[0][n - 1];
}

def strange_printer(s):
    n = len(s)

    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

    for length in range(2, n + 1):

        for i in range(0, n - length + 1):

            j = i + length - 1

            dp[i][j] = (
                dp[i + 1][j] + 1
            )

            for k in range(i + 1, j + 1):

                if s[i] == s[k]:

                    middle = (
                        0 if k == i + 1
                        else dp[i + 1][k - 1]
                    )

                    dp[i][j] = min(
                        dp[i][j],
                        middle + dp[k][j]
                    )

    return dp[0][n - 1]

int strangePrinter(string& s) {

    int n = s.size();

    vector<vector<int>> dp(n, vector<int>(n));

    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    for (int length = 2; length <= n; length++) {

        for (int i = 0;
             i + length - 1 < n;
             i++) {

            int j = i + length - 1;

            dp[i][j] =
                dp[i + 1][j] + 1;

            for (int k = i + 1; k <= j; k++) {

                if (s[i] == s[k]) {

                    int middle = k == i + 1
                        ? 0
                        : dp[i + 1][k - 1];

                    dp[i][j] = min(
                        dp[i][j],
                        middle + dp[k][j]
                    );
                }
            }
        }
    }

    return dp[0][n - 1];
}

function strangePrinter(s) {
  const n = s.length;

  const dp = Array.from({ length: n }, () =>
    new Array(n).fill(0)
  );

  for (let i = 0; i < n; i++) {
    dp[i][i] = 1;
  }

  for (let length = 2; length <= n; length++) {
    for (let i = 0; i + length - 1 < n; i++) {
      const j = i + length - 1;

      dp[i][j] = dp[i + 1][j] + 1;

      for (let k = i + 1; k <= j; k++) {
        if (s[i] === s[k]) {
          const middle =
            k === i + 1 ? 0 : dp[i + 1][k - 1];

          dp[i][j] = Math.min(
            dp[i][j],
            middle + dp[k][j]
          );
        }
      }
    }
  }

  return dp[0][n - 1];
}

What Changed from Base?

Instead of splitting normally:

dp[i][k] + dp[k + 1][j]

we look for another occurrence of the same character:

s.charAt(i) == s.charAt(k)

so the printer can reuse the same turn.

Strange Printer = Interval DP + Merge equal characters.

Pattern 8: Remove Boxes

Remove Boxes

Remove adjacent same-color boxes for k² points, maximizing score.

dp[i][j] (with same-colored boxes to the right) = max score. Remove a box alone, or merge it with a matching box to the right before removing. Interval DP with an extra 'same-color count' dimension. O(n⁴) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dfs(i, j, k):  // k = boxes same color as j on its right
                      
                        2
                          if i > j: return 0
                      
                        3
                          m = j; while m>i && boxes[m-1]==boxes[j]: m--, k++
                      
                        4
                          res = dfs(i, m-1, 0) + (k+1)*(k+1)
                      
                        5
                          for p in i..m-1: if boxes[p]==boxes[j]:
                      
                        6
                            res = max(res, dfs(i,p,0) + dfs(p+1,m-1,k+1))
                      
                        7
                          return res

Problem Type

Remove boxes to maximize points.

The difficult part is that keeping equal-colored boxes together can increase the future score.

So dp[i][j] is not enough.

We also need:

k = number of same-colored boxes attached to the current group

Mental Trigger

“Range + future benefit from keeping a group” → Interval DP + extra state

Java Code

public int removeBoxes(int[] boxes) {

    int n = boxes.length;

    int[][][] dp =
        new int[n][n][n];

    return solve(boxes, 0, n - 1, 0, dp);
}

private int solve(
    int[] boxes,
    int l,
    int r,
    int k,
    int[][][] dp
) {
    if (l > r)
        return 0;

    if (dp[l][r][k] != 0)
        return dp[l][r][k];

    while (l < r &&
           boxes[r] == boxes[r - 1]) {

        r--;
        k++;
    }

    int best =
        solve(boxes, l, r - 1, 0, dp)
        + (k + 1) * (k + 1);

    for (int i = l; i < r; i++) {

        if (boxes[i] == boxes[r]) {

            best = Math.max(
                best,
                solve(boxes, l, i, k + 1, dp)
                + solve(boxes, i + 1, r - 1, 0, dp)
            );
        }
    }

    return dp[l][r][k] = best;
}

def remove_boxes(boxes):
    from functools import lru_cache

    n = len(boxes)

    @lru_cache(maxsize=None)
    def solve(l, r, k):
        if l > r:
            return 0

        while (
            l < r
            and boxes[r] == boxes[r - 1]
        ):
            r -= 1
            k += 1

        best = (
            solve(l, r - 1, 0)
            + (k + 1) * (k + 1)
        )

        for i in range(l, r):

            if boxes[i] == boxes[r]:
                best = max(
                    best,
                    solve(l, i, k + 1)
                    + solve(i + 1, r - 1, 0)
                )

        return best

    return solve(0, n - 1, 0)

int memo[100][100][100];
vector<int> b;

// ponytail: fixed 100x100x100 memo, size to n if inputs grow
int solve(int l, int r, int k) {
    if (l > r)
        return 0;

    if (memo[l][r][k] != 0)
        return memo[l][r][k];

    while (l < r &&
           b[r] == b[r - 1]) {

        r--;
        k++;
    }

    int best =
        solve(l, r - 1, 0)
        + (k + 1) * (k + 1);

    for (int i = l; i < r; i++) {

        if (b[i] == b[r]) {

            best = max(
                best,
                solve(l, i, k + 1)
                + solve(i + 1, r - 1, 0)
            );
        }
    }

    return memo[l][r][k] = best;
}

int removeBoxes(vector<int>& boxes) {
    b = boxes;

    memset(memo, 0, sizeof(memo));

    return solve(0, boxes.size() - 1, 0);
}

function removeBoxes(boxes) {
  const n = boxes.length;

  const memo = Array.from({ length: n }, () =>
    Array.from({ length: n }, () =>
      new Array(n).fill(0)
    )
  );

  function solve(l, r, k) {
    if (l > r) return 0;

    if (memo[l][r][k] !== 0) {
      return memo[l][r][k];
    }

    while (l < r && boxes[r] === boxes[r - 1]) {
      r--;
      k++;
    }

    let best =
      solve(l, r - 1, 0) + (k + 1) * (k + 1);

    for (let i = l; i < r; i++) {
      if (boxes[i] === boxes[r]) {
        best = Math.max(
          best,
          solve(l, i, k + 1) +
            solve(i + 1, r - 1, 0)
        );
      }
    }

    memo[l][r][k] = best;
    return best;
  }

  return solve(0, n - 1, 0);
}

What Changed from Base?

Base:

dp[i][j]

Remove Boxes:

dp[i][j][k]

because we need to remember:

[i...j] = current range
k = extra boxes connected to the current group

Remove Boxes = Interval DP + extra state for the carried group.

Interval DP Pattern Evolution

Basic Interval DP
    |
    |-- dp[i][j]
    |
    ↓
Try every split k
    |
    ↓
Different problems change the "extra information"
    |
    |-- MCM
    |     + multiplication cost
    |
    |-- Burst Balloons
    |     + choose last operation
    |
    |-- Cut Stick
    |     + interval length
    |
    |-- Merge Stones
    |     + range sum
    |
    |-- Palindrome
    |     + palindrome check
    |
    |-- Optimal BST
    |     + choose root
    |
    |-- Strange Printer
    |     + merge equal characters
    |
    |-- Remove Boxes
          + extra state k

Common Interval DP Mistakes

1. Not defining `dp[i][j]`

Before coding, write:

dp[i][j] = ?

For example:

dp[i][j] = minimum cost for range i...j

2. Forgetting to try every split

Wrong:

int k = i;

Interval DP usually needs:

for (int k = i; k < j; k++)

3. Filling the table in the wrong order

You need smaller ranges before larger ranges.

Use:

for (int length = 1; length <= n; length++)

Then:

length 1
   ↓
length 2
   ↓
length 3
   ↓
length 4

4. Using the wrong operation

Some problems maximize:

Math.max(...)

Others minimize:

Math.min(...)

Ask:

Am I maximizing or minimizing?

5. Forgetting special base cases

For example:

dp[i][i] = 0;

or:

dp[i][i] = 1;

depends on what dp[i][j] represents.

Recognition Cheat Sheet

If you see…	Think…
`dp[i][j]` over a range	Interval DP
Try every split	Interval DP
Different parenthesization	MCM
Removal order matters	Burst Balloons
Cut a segment	Cut Stick
Merge adjacent groups	Merge Stones
Minimum palindrome cuts	Palindrome Partitioning
Choose best root	Optimal BST
Same characters can share work	Strange Printer
Future reward depends on a group	Interval DP + extra state

How to Recognize Interval DP

Ask these questions:

1. Is the problem about a range?

[i ... j]

If yes → possible Interval DP.

2. Does an operation split the range?

[i ... k] | [k+1 ... j]

If yes → strong Interval DP signal.

3. Do I need to try every possible split?

for (int k = i; k < j; k++)

If yes → very likely Interval DP.

4. Can smaller ranges solve the bigger range?

small range
     ↓
larger range

If yes → Interval DP.

Earn Premium with Referrals

Pattern Table

Mental Trigger

1. Generic Interval DP Template (Base)

What Does dp[i][j] Mean?

The Most Important Part

Pattern 1: Matrix Chain Multiplication (MCM)

Problem Type

Mental Trigger

Java Code

Matrix Chain Multiplication

What Changed from the Base?

Pattern 2: Burst Balloons

Problem Type

Mental Trigger

Java Code

Burst Balloons (Interval DP)

What Changed from the Base?

Pattern 3: Minimum Cost to Cut a Stick

Minimum Cost to Cut a Stick

Problem Type

Mental Trigger

Java Code

What Changed from the Base?

Pattern 4: Merge Stones

Merge Stones (Min Cost)

Problem Type

Mental Trigger

Java Code

What Changed from the Base?

Pattern 5: Palindrome Partitioning

Palindrome Partitioning

Version A: Minimum Cuts

Problem Type

Mental Trigger

Java Code

What Changed from Base?

Pattern 6: Optimal Binary Search Tree

Optimal Binary Search Tree

Problem Type

Mental Trigger

Java Code

What Changed from Base?

Pattern 7: Strange Printer

Strange Printer

Problem Type

Mental Trigger

Java Code

What Changed from Base?

Pattern 8: Remove Boxes

Remove Boxes

Problem Type

Mental Trigger

Java Code

What Changed from Base?

Interval DP Pattern Evolution

Common Interval DP Mistakes

1. Not defining dp[i][j]

2. Forgetting to try every split

3. Filling the table in the wrong order

4. Using the wrong operation

5. Forgetting special base cases

Recognition Cheat Sheet

How to Recognize Interval DP

1. Is the problem about a range?

2. Does an operation split the range?

3. Do I need to try every possible split?

4. Can smaller ranges solve the bigger range?

Premium Content

My Private Notes

What Does `dp[i][j]` Mean?

1. Not defining `dp[i][j]`