Interval DP

The Magic of Interval DP & Partition DP 🎯

The Pizza Slice Story

Imagine you have a long pizza with different toppings on each slice. You want to eat the whole pizza, but here’s the catch: you can only eat one slice at a time from either end (left or right). Each time you eat a slice, you get points based on how yummy it is!

This is Interval DP - solving problems where you work on a range (like slices 2 to 5) and find the best answer by trying all possible ways to split or shrink that range.

What is Interval DP?

Interval DP is a special type of Dynamic Programming where:

1. You have a sequence (like an array or string)
2. You solve for ranges [i, j] (from position i to position j)
3. You build bigger ranges from smaller ranges

The Core Idea 💡

Think of it like this:

“To solve a big puzzle (range i to j), I first solve all the smaller puzzles inside it, then combine them!”

The Magic Formula

dp[i][j] = best answer for range [i, j]

We fill this table diagonally - starting with length 1, then length 2, then length 3, and so on.

graph TD
    A["Length 1: dp[0,0], dp[1,1], dp[2,2]..."] --> B["Length 2: dp[0,1], dp[1,2], dp[2,3]..."]
    B --> C["Length 3: dp[0,2], dp[1,3], dp[2,4]..."]
    C --> D["...until full range dp[0,n-1]"]

Real Example: Burst Balloons 🎈

Problem: You have balloons numbered 0 to n-1. Each balloon has coins written on it. When you burst balloon i, you get: coins[left] × coins[i] × coins[right]

What’s the maximum coins you can collect?

Why Regular DP Fails

If we just think “which balloon to burst first?”, it gets messy! After bursting one balloon, the neighbors change. It’s chaos!

The Interval DP Trick ✨

Instead of thinking “what to burst first”, we think “what to burst LAST” in each range!

Why? Because if balloon k is the last one burst in range [i, j]:

• All balloons between i and k are already gone
• All balloons between k and j are already gone
• Balloon k sees only the boundaries: nums[i-1] and nums[j+1]

The Code

function maxCoins(nums) {
  // Add 1 at both ends
  const n = nums.length;
  const arr = [1, ...nums, 1];

  // dp[i][j] = max coins for
  // range (i, j) exclusive
  const dp = Array(n + 2).fill(null)
    .map(() => Array(n + 2).fill(0));

  // Try all range lengths
  for (let len = 1; len <= n; len++) {
    for (let i = 1; i + len <= n + 1; i++) {
      const j = i + len - 1;

      // Try each balloon as LAST
      for (let k = i; k <= j; k++) {
        const coins = arr[i-1] * arr[k] * arr[j+1];
        const left = dp[i][k-1];
        const right = dp[k+1][j];

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

  return dp[1][n];
}

Step-by-Step for [3, 1, 5, 8]

Answer: 167 coins! 🎉

What is Partition DP?

Partition DP is Interval DP’s cousin. Instead of working on ranges, we focus on splitting an array into groups.

The Core Question

“What’s the best way to divide this array into K groups?”

The Magic Formula

dp[i][k] = best answer using first i elements
           split into exactly k groups

Key Difference from Interval DP

Real Example: Partition Array for Maximum Sum

Problem: Split array into groups of at most K elements. Replace all elements in each group with the maximum of that group. Find maximum total sum.

Example: arr = [1, 15, 7, 9, 2, 5, 10], k = 3

Best partition: [15, 15] + [9, 9, 9] + [10, 10] = 30 + 27 + 20 = 77

The Approach

graph TD
    A["dp[i] = max sum for first i elements"] --> B["For each i, try all last group sizes"]
    B --> C["Last group: j to i #40;size 1 to k#41;"]
    C --> D["dp[i] = max#40;dp[j-1] + maxVal × groupSize#41;"]

The Code

function maxSumAfterPartitioning(arr, k) {
  const n = arr.length;
  const dp = Array(n + 1).fill(0);

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

    // Try last group of size 1 to k
    for (let j = 1; j <= Math.min(i, k); j++) {
      maxVal = Math.max(
        maxVal,
        arr[i - j]
      );

      dp[i] = Math.max(
        dp[i],
        dp[i - j] + maxVal * j
      );
    }
  }

  return dp[n];
}

Classic Interval DP: Matrix Chain Multiplication

Problem: You have matrices A₁, A₂, …, Aₙ. Find the minimum multiplications needed.

Key Insight: Order of multiplication matters!

A(10×30) × B(30×5) × C(5×60)

(A × B) × C = 10×30×5 + 10×5×60 = 4500
A × (B × C) = 30×5×60 + 10×30×60 = 27000

Difference: 22,500 operations! 😱

The Code

function matrixChainOrder(dims) {
  const n = dims.length - 1;
  const dp = Array(n).fill(null)
    .map(() => Array(n).fill(0));

  // Length of chain
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i < n - len + 1; i++) {
      const j = i + len - 1;
      dp[i][j] = Infinity;

      // Try all split points
      for (let k = i; k < j; k++) {
        const cost = dp[i][k] + dp[k+1][j]
          + dims[i] * dims[k+1] * dims[j+1];

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

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

Palindrome Partitioning II

Problem: Given a string, find minimum cuts to make all parts palindromes.

Example: "aab" → ["aa", "b"] → 1 cut

Two-Step Approach

1. Pre-compute: Which substrings are palindromes?
2. Partition DP: Find minimum cuts

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

  // Step 1: isPalin[i][j] = true
  // if s[i..j] is palindrome
  const isPalin = Array(n).fill(null)
    .map(() => Array(n).fill(false));

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

  // Step 2: dp[i] = min cuts for s[0..i]
  const dp = Array(n).fill(0);

  for (let i = 0; i < n; i++) {
    if (isPalin[0][i]) {
      dp[i] = 0; // No cut needed
    } else {
      dp[i] = i; // Max cuts = i

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

  return dp[n - 1];
}

The Time Complexity Pattern

When to Use Interval DP vs Partition DP

graph TD
    A["Problem involves a sequence?"] -->|Yes| B["Working on ranges [i,j]?"]
    A -->|No| E["Use other DP types"]

    B -->|Yes| C["INTERVAL DP"]
    B -->|No| D["Splitting into K groups?"]

    D -->|Yes| F["PARTITION DP"]
    D -->|No| E

Interval DP Signals 🚦

• “Minimum/maximum for range i to j”
• “Merge adjacent elements”
• “Remove from ends”
• “Burst/pop in sequence”

Partition DP Signals 🚦

• “Divide into K parts”
• “Split array optimally”
• “Minimum cuts needed”
• “Group elements together”

Summary: Your Toolbox 🧰

The Golden Rule 🌟

Start small, build big. Solve for small ranges/groups first, then combine them to solve bigger ones!

Practice Problems

1. Stone Game - Remove stones from ends
2. Minimum Score Triangulation - Split polygon optimally
3. Palindrome Partitioning - Minimum cuts
4. Paint House III - Group houses into neighborhoods

You now have the power to tackle any Interval DP or Partition DP problem! Remember: the key is always to find what decisions you’re making and how smaller subproblems combine into bigger ones.

Happy coding! 🚀