MANG Problem #29: Burst Balloons (Hard)

1. Problem Statement

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. After the burst, the i - 1 and i + 1 then becomes adjacent.

Return the maximum coins you can collect by bursting the balloons wisely.

Input: nums = [3,1,5,8]
Output: 167

2. Approach: Interval DP (Think Backwards)

The main difficulty is that bursting a balloon changes the neighbors of remaining balloons. This "dependency" makes standard DP hard.

The "Aha!" Moment

Instead of asking "Which balloon should I burst first?", ask "Which balloon should I burst LAST in this interval?"

If balloon k is the last to burst in the interval [i, j]:

All balloons between i and k are already gone.
All balloons between k and j are already gone.
Therefore, the neighbors of k when it bursts will be nums[i-1] and nums[j+1].
State: dp[i][j] is the maximum coins we can get from bursting all balloons in the range (i, j).
Transition: dp[i][j] = max(nums[i-1]*nums[k]*nums[j+1] + dp[i][k] + dp[k][j]) for all k in (i, j).

3. Java Implementation

public int maxCoins(int[] nums) {
    // 1. Add virtual boundaries with value 1
    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];

    // 2. Iterate through interval lengths
    for (int len = 1; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            // 3. Try every balloon as the LAST one to burst in [i, j]
            for (int k = i; k <= j; k++) {
                dp[i][j] = Math.max(dp[i][j], 
                    newNums[i - 1] * newNums[k] * newNums[j + 1] + 
                    dp[i][k - 1] + dp[k + 1][j]);
            }
        }
    }

    return dp[1][n];
}

4. 5-Minute "Video-Style" Walkthrough

The Problem: If you burst 1 in [3, 1, 5, 8], you get 3*1*5. Now 3 and 5 are neighbors. The subproblems are no longer independent.
The Solution: By picking the Last balloon, we create two independent subproblems: [i, k-1] and [k+1, j]. Since k is the last to burst, its neighbors are guaranteed to be the balloons just outside our current interval.
The Execution: We build the solution from small intervals (length 1) to large ones. For length 1, the "last balloon" is the only balloon.

5. Interview Discussion

Interviewer: "What is the time complexity?"
You: "O(N^3). We have two loops for the interval boundaries ($O(N^2)$) and an inner loop to pick the last balloon ($O(N)$)."
Interviewer: "Why add 1s at the ends?"
You: "To handle the edge cases where a balloon has no left or right neighbor, simplifying the logic to nums[i-1] * nums[k] * nums[j+1] for every index."