Interval DP: Burst Balloons and Stone Merging

Interval DP Logic

The core philosophy of Interval DP is addressing problems on a range $[i, j]$. The calculation order follows this sequence: Iterate Interval Length $\to$ Iterate Left Bound $\to$ Iterate Split Point.

// Universal Template
for (int len = 2; len <= n; len++) {            // Loop through interval length
    for (int i = 0; i + len - 1 < n; i++) {     // Loop through start index
        int j = i + len - 1;                    // End index
        for (int k = i; k < j; k++) {          // Loop through split point
            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + cost);
        }
    }
}

Longest Palindromic Subsequence (LeetCode 516)

dp[i][j] = length of the longest palindromic subsequence in s[i..j].

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1; // Single char is a palindrome of 1
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

Burst Balloons (LeetCode 312)

dp[i][j] = maximum coins obtained by bursting all balloons within the (open) interval (i, j).

Key: Decide the LAST balloon k to be burst. Since k is the last one, balloons i and j are still present as neighbors.

public 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 N = n + 2;
    int[][] dp = new int[N][N];
    for (int len = 2; len < N; len++) {
        for (int i = 0; i + len - 1 < N; i++) {
            int j = i + len - 1;
            for (int k = i + 1; k < j; k++) {
                dp[i][j] = Math.max(dp[i][j], 
                    dp[i][k] + arr[i] * arr[k] * arr[j] + dp[k][j]);
            }
        }
    }
    return dp[0][N - 1];
}

Stone Merging (Classic Interval DP)

Merge $n$ piles of stones into one. Each merge step combines two adjacent piles with cost equal to the sum of the combined piles. Minimize the total cost.

public int mergeStones(int[] stones) {
    int n = stones.length;
    // Prefix Sum for efficient range sum calculations
    int[] prefix = new int[n + 1];
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + stones[i];
    
    int[][] dp = new int[n][n];
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;
            int totalWeight = prefix[j + 1] - prefix[i];
            for (int k = i; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + totalWeight);
            }
        }
    }
    return dp[0][n - 1];
}

At a Glance Comparison Table