Interval DP

🎯 Interval DP & Partition DP: The Art of Breaking Problems Into Pieces

Imagine you have a long chocolate bar. You want to break it into tiny squares, but each break costs energy. How do you break it smartly to use the least energy?

🍫 The Chocolate Bar Story

Let’s say you have a chocolate bar with 5 squares in a row. You want to break it into individual pieces. Every time you break, it costs 1 coin multiplied by the length of the piece you’re breaking.

Here’s the magic question: In what ORDER should you break to spend the fewest coins?

This is Interval DP — finding the best way to handle a range of things by trying every possible way to split it!

🎪 What is Interval DP?

Simple Idea: You have a row of items (like beads on a string). You want to do something with the WHOLE row. But you can only work with smaller pieces first.

🧩 The Core Pattern

Think of it like this:

[-------whole problem-------]
    ↓ try splitting here
[--left--] + [--right--]

You try EVERY possible split point. For each split:

1. Solve the left piece
2. Solve the right piece
3. Combine them
4. Pick the best combination!

📦 Real-Life Analogy: Merging Stone Piles

Imagine you have 4 piles of stones in a row:

Pile 1    Pile 2    Pile 3    Pile 4
  3         7         2         5

Rule: You can only merge adjacent piles (neighbors). The cost to merge = sum of stones in both piles.

Goal: Merge all piles into ONE pile with minimum cost.

🤔 Why Order Matters

Bad order:

1. Merge pile 1+2 → Cost: 3+7 = 10 → New pile: 10
2. Merge 10+3 → Cost: 10+2 = 12 → New pile: 12
3. Merge 12+4 → Cost: 12+5 = 17 → New pile: 17
4. Total: 10 + 12 + 17 = 39

Better order:

1. Merge pile 3+4 → Cost: 2+5 = 7 → New pile: 7
2. Merge pile 1+2 → Cost: 3+7 = 10 → New pile: 10
3. Merge 10+7 → Cost: 17 → Final pile: 17
4. Total: 7 + 10 + 17 = 34 ✨

Same piles, different order, different cost!

🔧 The Interval DP Recipe

# dp[i][j] = best answer for
#            the range from i to j

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

        # Try every split point k
        for k in range(i, j):
            left = dp[i][k]
            right = dp[k+1][j]
            combine_cost = cost(i, j, k)

            dp[i][j] = best(
                dp[i][j],
                left + right + combine_cost
            )

🎓 Key Insight

We build answers for small ranges first, then use them to solve bigger ranges!

Length 1: [0], [1], [2], [3]
Length 2: [0,1], [1,2], [2,3]
Length 3: [0,1,2], [1,2,3]
Length 4: [0,1,2,3] ← Final answer!

🎭 Classic Example: Matrix Chain Multiplication

You have matrices: A(10×20), B(20×30), C(30×40)

Cost to multiply two matrices: rows × common × cols

Question: What order minimizes operations?

Option 1: (A × B) × C

• A × B costs: 10 × 20 × 30 = 6,000
• Result × C costs: 10 × 30 × 40 = 12,000
• Total: 18,000

Option 2: A × (B × C)

• B × C costs: 20 × 30 × 40 = 24,000
• A × Result costs: 10 × 20 × 40 = 8,000
• Total: 32,000

Option 1 wins! Same answer, but 14,000 fewer operations!

🎨 Partition DP: The Special Case

Partition DP is when you split something into exactly K parts.

🍕 Pizza Cutting Analogy

You have a pizza with toppings worth different points. You want to cut it into exactly 3 slices to maximize the value.

Each slice has a “score” based on toppings. But adjacent toppings might create bonus points!

📐 Partition DP Pattern

# dp[i][k] = best way to partition
#            first i elements into k parts

for i in range(1, n+1):
    for k in range(1, K+1):
        for j in range(k-1, i):
            # Last partition: j+1 to i
            dp[i][k] = best(
                dp[i][k],
                dp[j][k-1] + value(j+1, i)
            )

🎯 Classic Partition DP: Painter’s Problem

Story: You have a fence with sections that need painting. You have K painters. Each painter paints a continuous section.

The time to finish = the slowest painter.

Goal: Assign sections so the slowest painter finishes fastest!

Example

Fence sections take: [10, 20, 30, 40]

With 2 painters:

• Option A: [10, 20] and [30, 40] → Times: 30 and 70 → Max: 70
• Option B: [10, 20, 30] and [40] → Times: 60 and 40 → Max: 60
• Option C: [10] and [20, 30, 40] → Times: 10 and 90 → Max: 90

Option B wins! Slowest painter takes 60 units.

🧮 The Partition DP Code

def painter_partition(sections, K):
    n = len(sections)

    # prefix[i] = sum of first i sections
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + sections[i]

    # dp[i][k] = min time for
    # first i sections with k painters
    dp = [[float('inf')] * (K+1)
          for _ in range(n+1)]
    dp[0][0] = 0

    for i in range(1, n+1):
        for k in range(1, min(i, K)+1):
            for j in range(k-1, i):
                # Painter k does j+1 to i
                time = prefix[i] - prefix[j]
                worst = max(dp[j][k-1], time)
                dp[i][k] = min(dp[i][k], worst)

    return dp[n][K]

🌟 When to Use Interval DP vs Partition DP

graph TD
    A["Problem has a&lt;br&gt;range/sequence?"] -->|Yes| B{Fixed number<br>of parts?}
    B -->|No| C["Interval DP&lt;br&gt;Try all splits"]
    B -->|Yes, K parts| D["Partition DP&lt;br&gt;Track part count"]
    C --> E["Stone Merging&lt;br&gt;Matrix Chain&lt;br&gt;Balloon Burst"]
    D --> F["Painter Problem&lt;br&gt;Book Allocation&lt;br&gt;Array Splitting"]

🎪 Interval DP: Balloon Burst

You have balloons with numbers. When you burst balloon i, you get:

coins = nums[left] × nums[i] × nums[right]

Goal: Burst all balloons to maximize coins!

The Trick: Think Backwards!

Instead of “which to burst first,” think “which to burst LAST in this range?”

If balloon k is the LAST one burst in range [i,j]:

• Left side [i, k-1] is already burst
• Right side [k+1, j] is already burst
• When we burst k: neighbors are i-1 and j+1!

def maxCoins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    for length in range(1, n-1):
        for i in range(1, n - length):
            j = i + length - 1
            for k in range(i, j+1):
                coins = nums[i-1]*nums[k]*nums[j+1]
                dp[i][j] = max(
                    dp[i][j],
                    dp[i][k-1] + coins + dp[k+1][j]
                )

    return dp[1][n-2]

🎓 Key Takeaways

Interval DP Checklist ✅

1. Problem involves a range or sequence
2. You need to find best way to split/merge
3. Build from small ranges to big ranges
4. Try every possible split point

Partition DP Checklist ✅

1. Must divide into exactly K parts
2. Each part is contiguous (no gaps)
3. Track both position AND part count
4. Often involves min-max or sum problems

🚀 Practice Problems

1. Stone Merging — Merge stones with minimum cost
2. Matrix Chain — Multiply matrices optimally
3. Balloon Burst — Pop balloons for maximum coins
4. Painter’s Partition — Divide work among K workers
5. Palindrome Partitioning — Split into fewest palindromes

🎯 The Golden Rule

“For Interval DP, think: What happens if I split HERE?” “For Partition DP, think: Where does the Kth group START?”

You’re not just solving a problem — you’re exploring every possible universe of splits and picking the best one! 🌟