Approach

Burst Balloons

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 ith 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, then treat it as if there is a balloon with a 1 painted on it.

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

Examples

Example 1:

Input: nums = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5   +   3*5*8   +  1*3*8  + 1*8*1 = 167

Example 2:

Input: nums = [1,5]
Output: 10

Constraints

n == nums.length
1 ≤ n ≤ 300
0 ≤ nums[i] ≤ 100

Approach

Key Insight

This is a classic Interval DP problem with a clever twist!

The trick: Instead of thinking "which balloon to burst first?", think "which balloon to burst LAST in each interval?"

Adding virtual balloons with value 1 at both ends simplifies boundary handling.

Solution 1: Interval DP (Bottom-up)

Build solutions for small intervals, then combine for larger intervals.

Algorithm:

Add 1 at both ends: nums = [1, original_nums..., 1]
Create dp[n][n] where dp[i][j] = max coins from bursting balloons in (i, j) (exclusive)
For each interval length from 1 to n-2:
- For each start position i:
  - Try each balloon k as the LAST one to burst in (i, j)
  - dp[i][j] = max(dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j])
Return dp[0][n-1]

Why burst LAST?

When k is burst last, left side (i, k) and right side (k, j) are independent
We know k's neighbors will be i and j (they're the last remaining)
This avoids the dependency nightmare of bursting first

Complexity:

Time: O(n³) - three nested loops
Space: O(n²) - DP table

Solution 2: Top-down Memoization

Recursively solve with memoization.

Algorithm:

Define maxCoins(left, right): max coins bursting balloons in (left, right)
Base case: no balloons between left and right → return 0
Try each balloon k as the last one to burst
Return max of all choices
Memoize results

Complexity:

Time: O(n³)
Space: O(n²) for memo + O(n) recursion stack

Solution 3: Divide and Conquer

Similar to interval DP but with recursive structure.

Algorithm:

For each interval, try all possible last bursts
Divide problem into left and right subproblems
Combine results
Use memoization to avoid recomputation

Complexity:

Time: O(n³) with memoization
Space: O(n²)

Complexity Analysis

| Approach | Time | Space | |----------|------|-------| | Interval DP | O(n³) | O(n²) | | Top-down Memo | O(n³) | O(n²) | | Divide & Conquer | O(n³) | O(n²) |

Pattern Recognition

This problem demonstrates:

Interval DP pattern (build small → large)
"Burst last" vs "burst first" insight
Adding boundary elements to simplify logic
Similar patterns: Matrix Chain Multiplication, Remove Boxes
Key technique: Think backwards to avoid dependencies

Solution

java

1import java.util.*;
2
3class Solution {
4    // Solution 1: Interval DP (Bottom-up)
5    public int maxCoins(int[] nums) {
6        int n = nums.length;
7
8        // Add 1 at both ends to handle boundaries
9        int[] balloons = new int[n + 2];
10        balloons[0] = 1;
11        balloons[n + 1] = 1;
12        for (int i = 0; i < n; i++) {
13            balloons[i + 1] = nums[i];
14        }
15
16        // dp[i][j] = max coins from bursting balloons in interval (i, j) exclusive
17        int[][] dp = new int[n + 2][n + 2];
18
19        // Build from small intervals to large
20        for (int length = 1; length <= n; length++) {
21            for (int left = 0; left < n + 2 - length - 1; left++) {
22                int right = left + length + 1;
23
24                // Try each balloon k as the LAST one to burst in (left, right)
25                for (int k = left + 1; k < right; k++) {
26                    // When k is burst last:
27                    // - Left side (left, k) is already burst
28                    // - Right side (k, right) is already burst
29                    // - k's neighbors are left and right
30                    int coins = balloons[left] * balloons[k] * balloons[right];
31                    coins += dp[left][k] + dp[k][right];
32
33                    dp[left][right] = Math.max(dp[left][right], coins);
34                }
35            }
36        }
37
38        // Return max coins from bursting all balloons between 0 and n+1
39        return dp[0][n + 1];
40    }
41
42    // Solution 2: Top-down Memoization
43    public int maxCoinsMemo(int[] nums) {
44        int n = nums.length;
45        int[] balloons = new int[n + 2];
46        balloons[0] = 1;
47        balloons[n + 1] = 1;
48        for (int i = 0; i < n; i++) {
49            balloons[i + 1] = nums[i];
50        }
51
52        Map<String, Integer> memo = new HashMap<>();
53        return dp(balloons, 0, n + 1, memo);
54    }
55
56    private int dp(int[] balloons, int left, int right, Map<String, Integer> memo) {
57        // Base case: no balloons to burst
58        if (left + 1 == right) {
59            return 0;
60        }
61
62        // Check memo
63        String key = left + "," + right;
64        if (memo.containsKey(key)) {
65            return memo.get(key);
66        }
67
68        int maxCoins = 0;
69
70        // Try each balloon k as the last one to burst
71        for (int k = left + 1; k < right; k++) {
72            int coins = balloons[left] * balloons[k] * balloons[right];
73            coins += dp(balloons, left, k, memo) + dp(balloons, k, right, memo);
74            maxCoins = Math.max(maxCoins, coins);
75        }
76
77        memo.put(key, maxCoins);
78        return maxCoins;
79    }
80
81    // Solution 3: Divide and Conquer with Memo
82    public int maxCoinsDivideConquer(int[] nums) {
83        int n = nums.length;
84        int[] balloons = new int[n + 2];
85        balloons[0] = 1;
86        balloons[n + 1] = 1;
87        for (int i = 0; i < n; i++) {
88            balloons[i + 1] = nums[i];
89        }
90
91        int[][] memo = new int[n + 2][n + 2];
92        for (int[] row : memo) {
93            Arrays.fill(row, -1);
94        }
95
96        return solve(balloons, 0, n + 1, memo);
97    }
98
99    private int solve(int[] balloons, int left, int right, int[][] memo) {
100        // Base case
101        if (left + 1 >= right) {
102            return 0;
103        }
104
105        // Check memo
106        if (memo[left][right] != -1) {
107            return memo[left][right];
108        }
109
110        int result = 0;
111
112        // Try bursting each balloon last
113        for (int i = left + 1; i < right; i++) {
114            // Current balloon burst last in this interval
115            int gain = balloons[left] * balloons[i] * balloons[right];
116
117            // Add coins from left and right subproblems
118            gain += solve(balloons, left, i, memo) + solve(balloons, i, right, memo);
119
120            result = Math.max(result, gain);
121        }
122
123        memo[left][right] = result;
124        return result;
125    }
126
127    // Solution 4: With Reconstruction
128    public static class Result {
129        public int maxCoins;
130        public List<Integer> burstOrder;
131
132        public Result(int maxCoins, List<Integer> burstOrder) {
133            this.maxCoins = maxCoins;
134            this.burstOrder = burstOrder;
135        }
136    }
137
138    public Result maxCoinsWithPath(int[] nums) {
139        int n = nums.length;
140        int[] balloons = new int[n + 2];
141        balloons[0] = 1;
142        balloons[n + 1] = 1;
143        for (int i = 0; i < n; i++) {
144            balloons[i + 1] = nums[i];
145        }
146
147        int[][] dp = new int[n + 2][n + 2];
148        int[][] choice = new int[n + 2][n + 2];
149
150        // Build DP table
151        for (int length = 1; length <= n; length++) {
152            for (int left = 0; left < n + 2 - length - 1; left++) {
153                int right = left + length + 1;
154
155                for (int k = left + 1; k < right; k++) {
156                    int coins = balloons[left] * balloons[k] * balloons[right];
157                    coins += dp[left][k] + dp[k][right];
158
159                    if (coins > dp[left][right]) {
160                        dp[left][right] = coins;
161                        choice[left][right] = k;
162                    }
163                }
164            }
165        }
166
167        // Reconstruct the path
168        List<Integer> burstOrder = new ArrayList<>();
169        reconstruct(balloons, choice, 0, n + 1, burstOrder);
170
171        return new Result(dp[0][n + 1], burstOrder);
172    }
173
174    private void reconstruct(int[] balloons, int[][] choice, int left, int right, List<Integer> order) {
175        if (left + 1 >= right) {
176            return;
177        }
178
179        int k = choice[left][right];
180        reconstruct(balloons, choice, left, k, order);
181        reconstruct(balloons, choice, k, right, order);
182        order.add(balloons[k]);  // Burst k last
183    }
184}
185