Burst Balloons

Problem Statement

You’re a balloon-busting strategist with an array of balloons, each worth its value times its neighbors’ values when burst. Burst all balloons in any order to maximize your coin haul! This hard-level DP brain-bender is a popping puzzle—plan your bursts for the ultimate score.

Example

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

Output: 167 (Order: 1,5,3,8 → 1*3*5 + 1*5*8 + 1*3*8 + 1*8*1 = 15+40+24+8)

Input: nums = [1, 5]

Output: 10 (1*5*1 = 10)

Input: nums = [3]

Output: 3 (1*3*1 = 3)

Code

public class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n + 2];
        arr[0] = 1; arr[n + 1] = 1;
        for (int i = 0; i < n; i++) arr[i + 1] = nums[i];
        int[][] dp = new int[n + 2][n + 2];
        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++) {
                    dp[left][right] = Math.max(dp[left][right], 
                        dp[left][k-1] + arr[left-1] * arr[k] * arr[right+1] + dp[k+1][right]);
                }
            }
        }
        return dp[1][n];
    }
}
            

def max_coins(nums):
    n = len(nums)
    arr = [1] + nums + [1]  # Add boundaries
    dp = [[0] * (n + 2) for _ in range(n + 2)]
    for len_ in range(1, n + 1):
        for left in range(1, n - len_ + 2):
            right = left + len_ - 1
            for k in range(left, right + 1):
                dp[left][right] = max(dp[left][right], 
                    dp[left][k-1] + arr[left-1] * arr[k] * arr[right+1] + dp[k+1][right])
    return dp[1][n]
            

function maxCoins(nums) {
    let n = nums.length;
    let arr = [1, ...nums, 1];
    let dp = Array(n + 2).fill().map(() => Array(n + 2).fill(0));
    for (let len = 1; len <= n; len++) {
        for (let left = 1; left <= n - len + 1; left++) {
            let right = left + len - 1;
            for (let k = left; k <= right; k++) {
                dp[left][right] = Math.max(dp[left][right], 
                    dp[left][k-1] + arr[left-1] * arr[k] * arr[right+1] + dp[k+1][right]);
            }
        }
    }
    return dp[1][n];
}
            

Explanation

• DP Insight: dp[left][right] = max coins from bursting balloons in range [left, right].
• Flow: For each subarray, try bursting each balloon last and maximize coins using neighbors.
• Boundaries: Add 1s at ends to handle edge cases.
• Example Walkthrough: [3,1,5] → dp[1][3]=35 (burst 1 last: 1*3*5 + dp[1][0] + dp[2][2]).
• Relevance: Reverse thinking—burst last instead of first—unlocks this tricky DP.

Note