Interval DP

🎪 The Circus Tent Builder’s Guide to Interval & Partition DP

Welcome, young architect! Today we’re going to build circus tents and learn how to solve puzzles by thinking about SECTIONS of things.

🎯 The Big Idea: Breaking Things Into Pieces

Imagine you have a long rope of beads. You want to find the best way to cut it into pieces. That’s what Interval DP and Partition DP help us do!

Simple Analogy: Think of a chocolate bar with squares. Where should you break it to share with friends in the best way?

🏕️ Part 1: Interval DP — The Circus Tent Story

What is Interval DP?

Imagine you’re building a circus tent with poles at different positions. You need to connect poles to make triangle sections. The cost depends on which poles you connect.

Interval DP solves problems where:

• You have a sequence of things (like poles in a row)
• You need to combine adjacent items
• You want the minimum or maximum cost/value

graph TD
    A["Full Problem"] --> B["Left Half"]
    A --> C["Right Half"]
    B --> D["Smaller Pieces"]
    C --> E["Smaller Pieces"]
    D --> F["Single Items"]
    E --> F

🎪 The Magic Formula

For any section from position i to position j:

dp[i][j] = best way to solve section [i...j]

We try every possible split point k between i and j:

// Try all ways to split [i,j]
for (int k = i; k < j; k++) {
    int cost = dp[i][k] + dp[k+1][j]
               + mergeCost(i, k, j);
    dp[i][j] = Math.min(dp[i][j], cost);
}

🔢 Classic Example: Matrix Chain Multiplication

The Story

You have matrices to multiply: A × B × C × D

The catch: The ORDER of multiplying matters for speed!

• (A × B) × (C × D) might be fast
• A × ((B × C) × D) might be slow

We want the fastest order!

Why Order Matters

Multiplying a 10×30 matrix with a 30×5 matrix costs:

10 × 30 × 5 = 1500 operations

Different groupings = Different total costs!

The Solution

int matrixChain(int[] dims) {
    int n = dims.length - 1;
    int[][] dp = new int[n][n];

    // len = length of chain
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;

            // Try each split point k
            for (int k = i; k < j; k++) {
                int 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];
}

Think of it like this:

• We solve small chains first (2 matrices)
• Then medium chains (3 matrices)
• Finally the whole chain

🎈 Example: Burst Balloons

The Story

You have balloons in a row, each with a number. When you burst a balloon, you get:

coins = left × balloon × right

Goal: Burst all balloons to get maximum coins!

The Trick

Instead of thinking “which to burst first”, think:

“Which balloon should be the LAST to burst in this section?”

int maxCoins(int[] nums) {
    int n = nums.length;
    int[] arr = new int[n + 2];
    arr[0] = arr[n + 1] = 1;
    for (int i = 0; i < n; i++) {
        arr[i + 1] = nums[i];
    }

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

    for (int len = 1; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            for (int k = i; k <= j; k++) {
                // k is LAST balloon to burst
                int coins = arr[i-1] * arr[k] * arr[j+1];
                coins += dp[i][k-1] + dp[k+1][j];
                dp[i][j] = Math.max(dp[i][j], coins);
            }
        }
    }
    return dp[1][n];
}

🧩 Part 2: Partition DP — The Pizza Party Story

What is Partition DP?

Imagine you have a long pizza and you need to cut it into exactly K pieces to share with friends. Where should you cut?

Partition DP solves problems where:

• You divide something into K parts
• Each part has a cost or value
• You want to optimize the total

graph TD
    A["Divide into K parts"] --> B["Where to cut?"]
    B --> C["Try position 1"]
    B --> D["Try position 2"]
    B --> E["Try position 3"]
    C --> F["Solve remaining"]
    D --> F
    E --> F

🍕 The Magic Formula

dp[i][k] = best way to partition first i items
           into exactly k groups

For each position, we try all possible places for the last cut:

// dp[i][k] = best partition of [0..i] into k groups
for (int j = k-1; j < i; j++) {
    // Last group is [j+1...i]
    int value = dp[j][k-1] + cost(j+1, i);
    dp[i][k] = Math.min(dp[i][k], value);
}

📚 Classic Example: Painter’s Partition

The Story

You have boards of different lengths and K painters. Each painter paints consecutive boards. The time taken is the sum of board lengths.

Goal: Minimize the maximum time any painter spends.

Example

Boards: [10, 20, 30, 40], Painters: 2

• Painter 1: [10, 20, 30] = 60 time
• Painter 2: [40] = 40 time
• Maximum = 60 ✓

Or:

• Painter 1: [10, 20] = 30 time
• Painter 2: [30, 40] = 70 time
• Maximum = 70 ✗

First split is better!

The Solution

int partition(int[] boards, int k) {
    int n = boards.length;

    // Prefix sums for quick range sum
    int[] prefix = new int[n + 1];
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + boards[i];
    }

    // dp[i][j] = min max time for i boards, j painters
    int[][] dp = new int[n + 1][k + 1];

    // Base: 1 painter takes all boards
    for (int i = 1; i <= n; i++) {
        dp[i][1] = prefix[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 2; j <= Math.min(i, k); j++) {
            dp[i][j] = Integer.MAX_VALUE;

            // Try each split point
            for (int p = j - 1; p < i; p++) {
                int lastPainter = prefix[i] - prefix[p];
                int cost = Math.max(dp[p][j-1], lastPainter);
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }
    return dp[n][k];
}

🎸 Another Example: Palindrome Partitioning

The Story

You have a string. You want to cut it into the minimum number of pieces where each piece is a palindrome (reads same forward and backward).

Example

String: "aab"

• “aa” + “b” = 2 pieces (1 cut) ✓
• “a” + “a” + “b” = 3 pieces (2 cuts) ✗

The Solution

int minCut(String s) {
    int n = s.length();

    // isPal[i][j] = true if s[i..j] is palindrome
    boolean[][] isPal = 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)) {
                isPal[i][j] = (j - i <= 2)
                    || isPal[i+1][j-1];
            }
        }
    }

    // dp[i] = min cuts for s[0..i]
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) {
        if (isPal[0][i]) {
            dp[i] = 0; // Whole thing is palindrome
        } else {
            dp[i] = i; // Worst case: cut everywhere
            for (int j = 1; j <= i; j++) {
                if (isPal[j][i]) {
                    dp[i] = Math.min(dp[i], dp[j-1] + 1);
                }
            }
        }
    }
    return dp[n - 1];
}

🔑 Key Differences

🎯 When to Use What?

Use Interval DP when:

• ✅ You’re combining/merging adjacent things
• ✅ Order of operations matters
• ✅ You need the best way to group a sequence

Use Partition DP when:

• ✅ You’re dividing into K groups
• ✅ Each group is consecutive
• ✅ You want to optimize the total or max

🌟 Pro Tips

1. Start Small: Always solve for length 1, then 2, then 3…

2. Draw It Out: Sketch your intervals on paper first

3. Find the Substructure: Ask “If I split here, what’s left?”

4. Watch for Boundaries: Off-by-one errors are common!

5. Prefix Sums: Often useful for quick range calculations

🎪 Summary: You’re Now a Tent Builder!

Interval DP: You learned to combine circus tent sections to find the cheapest way to build the whole tent.

Partition DP: You learned to divide a pizza into K pieces to make everyone happy.

Both techniques share the same secret:

Try all possible ways to split, and pick the best one!

You’re ready to tackle any interval or partition problem. Go build some amazing things! 🚀