Interval DP

1. Introduction: Collapsing the Subarrays

In standard 1D DP, we usually process an array from left to right. We make a decision at index i, and move to i+1.

But what if the problem allows you to make decisions that collapse or merge elements in the middle of the array? For example, what if you pop a balloon at index 3, and suddenly the balloons at index 2 and 4 become neighbors? A standard left-to-right approach completely fails here because the array is dynamically shrinking, and the ends of the array can interact with each other.

This requires Interval DP. Instead of defining the state as "up to index i", we define the state as the interval from index i to index j. We solve small intervals (length 1), then length 2, building our way up until we solve the interval from 0 to N-1 (the whole array).

2. Core Concept: Building from Small to Large

In Interval DP, dp[i][j] represents the optimal answer for the subarray starting at i and ending at j.

To find dp[i][j], we typically try to split the interval at some pivot k (where $i \le k < j$). We solve the left part [i...k], the right part [k+1...j], and add the cost of merging them together. $dp[i][j] = \min_{k} (dp[i][k] + dp[k+1][j] + \text{merge\_cost})$

This is the exact logic behind Matrix Chain Multiplication, the grandfather of all Interval DP problems.

3. Beginner Code Example: Palindrome Partitioning II

Problem Statement: (LeetCode 132) Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s.

While this can be solved with a 1D DP array, understanding the 2D boolean table used to find palindromes is the gateway to Interval logic.

The Insight: A string from i to j is a palindrome IF:

1. s.charAt(i) == s.charAt(j) AND
2. The inner substring from i+1 to j-1 is ALSO a palindrome.

public class PalindromeCuts {
    public static int minCut(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];
        int[] dp = new int[n]; // dp[i] = min cuts for substring s[0...i]
        
        for (int i = 0; i < n; i++) {
            int minCuts = i; // Max cuts is cutting every single letter
            
            // Look backwards from i to 0
            for (int j = 0; j <= i; j++) {
                // If characters match AND (the inner string is a palindrome OR length <= 2)
                if (s.charAt(i) == s.charAt(j) && (i - j <= 2 || isPal[j + 1][i - 1])) {
                    isPal[j][i] = true;
                    
                    if (j == 0) {
                        // The whole string from 0 to i is a palindrome, 0 cuts needed!
                        minCuts = 0;
                    } else {
                        // We make a cut right before j.
                        minCuts = Math.min(minCuts, dp[j - 1] + 1);
                    }
                }
            }
            dp[i] = minCuts;
        }
        return dp[n - 1];
    }
}

4. Intermediate Code Example: Matrix Chain Multiplication (MCM)

Problem Statement: Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.

Multiplying an $A \times B$ matrix by a $B \times C$ matrix costs $A \times B \times C$ operations, and results in an $A \times C$ matrix. Because matrix multiplication is associative, $(A \times B) \times C$ yields the same result as $A \times (B \times C)$, but the number of mathematical operations can be wildly different.

public class MatrixChain {
    // arr[] represents matrix dimensions. 
    // Matrix i has dimensions arr[i-1] x arr[i]
    public static int matrixChainOrder(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        
        // Loop over interval lengths (L)
        // L=2 means multiplying 2 matrices, L=3 means 3 matrices, etc.
        for (int L = 2; L < n; L++) {
            for (int i = 1; i < n - L + 1; i++) {
                int j = i + L - 1;
                dp[i][j] = Integer.MAX_VALUE;
                
                // Try splitting the interval [i...j] at every possible k
                for (int k = i; k <= j - 1; k++) {
                    // Cost = Left part + Right part + Merge cost
                    int cost = dp[i][k] + dp[k + 1][j] + (arr[i - 1] * arr[k] * arr[j]);
                    
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }
        return dp[1][n - 1];
    }
}

Complexity Analysis:

• Time Complexity: $O(N^3)$. Two loops to define the interval boundaries i and j, and a third loop for k to find the split point.
• Space Complexity: $O(N^2)$ for the DP matrix.

5. Advanced Code Example: Burst Balloons

Problem Statement: (LeetCode 312) You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons. If you burst the $i$-th balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, treat it as if there is a balloon with a 1 painted on it. Find the maximum coins you can collect by bursting the balloons wisely.

The Insight: If we think about the first balloon to burst, the array collapses, and the left and right sides suddenly become adjacent. This creates overlapping dependencies that break standard DP. The Trick: Think about the LAST balloon to burst! If balloon k is the last one to burst in the interval [i...j], it means the left sub-interval [i...k-1] and the right sub-interval [k+1...j] have already been completely popped! Therefore, the cost of popping k last is purely nums[i-1] * nums[k] * nums[j+1]. The subproblems are completely independent!

public class BurstBalloons {
    public static int maxCoins(int[] nums) {
        // Pad the array with 1s at both ends to handle edge cases easily
        int n = nums.length;
        int[] padded = new int[n + 2];
        padded[0] = 1;
        padded[n + 1] = 1;
        for (int i = 0; i < n; i++) padded[i + 1] = nums[i];
        
        // dp[i][j] = max coins obtained by bursting balloons strictly BETWEEN i and j (exclusive)
        int[][] dp = new int[n + 2][n + 2];
        
        // L is the interval length
        for (int L = 1; L <= n; L++) {
            for (int i = 1; i <= n - L + 1; i++) {
                int j = i + L - 1;
                
                // k is the index of the LAST balloon to burst in this interval
                for (int k = i; k <= j; k++) {
                    // coins = left side + right side + burst k itself
                    int coins = dp[i][k - 1] + dp[k + 1][j] + (padded[i - 1] * padded[k] * padded[j + 1]);
                    dp[i][j] = Math.max(dp[i][j], coins);
                }
            }
        }
        
        return dp[1][n];
    }
}

Complexity Analysis:

• Time Complexity: $O(N^3)$. Standard Interval DP complexity.
• Space Complexity: $O(N^2)$ for the DP table.

6. Common Mistakes Beginners Make

1. Iterating i from 0 to N and j from i to N (Bottom-Up)

   • The Mistake: Using standard nested loops for a bottom-up Interval DP.
   • Why it's wrong: In Interval DP, to solve dp[i][j], you MUST have already solved all smaller intervals. If you loop i forwards and j forwards, dp[i][j] might require dp[i+1][j], which hasn't been computed yet!
   • The Fix: The outer loop MUST be the length of the interval L (from 1 to $N$). The inner loop is the start index i. This guarantees smaller intervals are processed first.

2. Off-by-One in the Split point k

   • The Mistake: Splitting at k and recursing on [i, k] and [k, j].
   • Why it's wrong: The element at k is duplicated in both subproblems, leading to double-counting.
   • The Fix: Always split at k and recurse on [i, k] and [k+1, j] (or similar mutually exclusive bounds).

7. Interview Q&A

Q1: How do I know a problem requires Interval DP? Answer: If a problem asks you to optimize a process of merging adjacent elements, collapsing elements (where neighbors change), or partitioning a sequence into chunks, and the array size is $\le 500$ (hinting at $O(N^3)$), it is almost certainly Interval DP.

Q2: Can Interval DP be solved Top-Down with Memoization? Answer: YES! In fact, Top-Down Memoization is heavily preferred by many engineers for Interval DP because you don't have to worry about the confusing L, i, j looping structure. You just write a recursive function solve(i, j), put a for(k) loop inside it, and cache the result. It automatically processes the dependencies in the correct order.

Q3: Is Interval DP always $O(N^3)$? Answer: Usually, yes. However, there is a legendary optimization called Knuth's Optimization (used for optimal binary search trees) that can reduce the complexity of certain Interval DP problems from $O(N^3)$ to $O(N^2)$ by restricting the search space of the pivot k. (Rarely asked in interviews, but good to name-drop).

8. Practice Problems

1. Burst Balloons (LeetCode 312)
   • Goal: Master the "think about the LAST element" trick.
2. Minimum Cost Tree From Leaf Values (LeetCode 1130)
   • Hint: Similar to Matrix Chain Multiplication. Merge adjacent leaves into a tree.
3. Palindrome Removal (LeetCode 1246 - Premium)
   • Hint: Find the minimum number of moves to remove palindromic subarrays.

9. Summary

• The Paradigm: State is defined by the boundaries of a subarray [i, j].
• The Transition: Pick a pivot k inside the interval, solve the left and right halves, and combine them.
• The $O(N^3)$ Loop: If writing Bottom-Up, the outer loop MUST be the interval length L.
• Top-Down Alternative: Top-down recursion is often much easier to write and conceptualize for Interval DP because it handles the ordering of subproblem evaluation automatically.