Interval DP

Interval DP solves problems on subarrays/substrings by considering all possible split points within an interval.

General Pattern

// dp[i][j] = optimal value for interval [i, j]
// Base case: dp[i][i] = 0 or some initial value
// Transition: Try all split points k in [i, j]

for (int len = 2; len <= n; len++) {        // interval length
    for (int i = 0; i <= n - len; i++) {     // start index
        int j = i + len - 1;                 // end index
        for (int k = i; k < j; k++) {        // split point
            dp[i][j] = optimize(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i,k,j));
        }
    }
}

Matrix Chain Multiplication

Given matrices A1, A2, ..., An, find the minimum number of scalar multiplications needed to compute the product.

// p[] = dimensions, p[0] x p[1], p[1] x p[2], ..., p[n-1] x p[n]
// dp[i][j] = min cost to multiply matrices i to j
public int matrixChainOrder(int[] p) {
    int n = p.length - 1;  // number of matrices
    int[][] dp = new int[n][n];
    
    // Base case: cost to multiply single matrix = 0
    // dp[i][i] = 0 (already initialized)
    
    // Fill for chain lengths 2 to n
    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;
            
            for (int k = i; k < j; k++) {
                // Cost = dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1]
                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];
}

Trace Example

p = [10, 30, 5, 60] → 3 matrices: 10x30, 30x5, 5x60

len=2: dp[0][1] = 10*30*5 = 1500
       dp[1][2] = 30*5*60 = 9000

len=3: dp[0][2] = min(
         dp[0][0] + dp[1][2] + 10*5*60 = 0 + 9000 + 3000 = 12000,
         dp[0][1] + dp[2][2] + 10*30*60 = 1500 + 0 + 18000 = 19500
       ) = 12000

Answer: 12000 (multiply as (A1 x A2) x A3)

Minimum Score Triangulation

// Minimum score triangulation of polygon
public int minScoreTriangulation(int[] values) {
    int n = values.length;
    int[][] dp = new int[n][n];
    
    for (int len = 2; len < n; len++) {
        for (int i = 0; i < n - len; i++) {
            int j = i + len;
            dp[i][j] = Integer.MAX_VALUE;
            
            for (int k = i + 1; k < j; k++) {
                int cost = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }
    
    return dp[0][n - 1];
}

Key Insights for Interval DP

1. Order of computation: Length 2 first, then length 3, etc.
2. Split point: Try all possible k to find optimal split
3. Cost function: Depends on the specific problem
4. Base case: Single element intervals have 0 cost

Palindrome Partitioning II

Minimum cuts needed to partition a string such that every substring is a palindrome.

// dp[i] = minimum cuts for s[0..i]
public int minCut(String s) {
    int n = s.length();
    boolean[][] isPalin = new boolean[n][n];
    int[] dp = new int[n];
    
    // Precompute palindrome table
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) {
                if (len <= 3 || isPalin[i + 1][j - 1]) {
                    isPalin[i][j] = true;
                }
            }
        }
    }
    
    // Compute minimum cuts
    for (int i = 0; i < n; i++) {
        if (isPalin[0][i]) {
            dp[i] = 0;  // No cut needed if whole prefix is palindrome
        } else {
            dp[i] = i;  // Maximum cuts (cut at every position)
            for (int j = 0; j < i; j++) {
                if (isPalin[j + 1][i]) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
    }
    
    return dp[n - 1];
}

Longest Palindromic Substring

// dp[i][j] = true if s[i..j] is palindrome
public String longestPalindrome(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    int start = 0, maxLen = 1;
    
    // Base case: single character
    for (int i = 0; i < n; i++) dp[i][i] = true;
    
    // Check for length 2
    for (int i = 0; i < n - 1; i++) {
        if (s.charAt(i) == s.charAt(i + 1)) {
            dp[i][i + 1] = true;
            start = i;
            maxLen = 2;
        }
    }
    
    // Check for length 3 and above
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                if (len > maxLen) {
                    start = i;
                    maxLen = len;
                }
            }
        }
    }
    
    return s.substring(start, start + maxLen);
}

Burst Balloons

// Maximum coins from bursting balloons
// Coins = nums[left] * nums[i] * nums[right] for burst balloon i
public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] newNums = new int[n + 2];
    newNums[0] = 1;
    newNums[n + 1] = 1;
    for (int i = 0; i < n; i++) newNums[i + 1] = nums[i];
    
    int[][] dp = new int[n + 2][n + 2];
    
    // Fill for all interval lengths
    for (int len = 1; len <= n; len++) {
        for (int left = 1; left <= n - len + 1; left++) {
            int right = left + len - 1;
            
            for (int k = left; k <= right; k++) {
                int coins = newNums[left - 1] * newNums[k] * newNums[right + 1]
                           + dp[left][k - 1] + dp[k + 1][right];
                dp[left][right] = Math.max(dp[left][right], coins);
            }
        }
    }
    
    return dp[1][n];
}

Interval DP Pattern Summary

Problem	dp[i][j]	Transition
Matrix Chain	Min cost for matrices i..j	min(dp[i][k] + dp[k+1][j] + cost)
Burst Balloons	Max coins for balloons i..j	max(dp[left][k-1] + dp[k+1][right] + cost)
Palindrome Partition	Min cuts for s[0..i]	min(dp[j] + 1) if s[j+1..i] is palindrome
Longest Palindrome	Is s[i..j] palindrome?	s[i]==s[j] && dp[i+1][j-1]