HardDynamic Programming

Burst Balloons

Explanation & Solution

Description

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.

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 = 15 + 120 + 24 + 8 = 167

Constraints

1 <= nums.length <= 300
0 <= nums[i] <= 100

Approach

Dynamic Programming pattern

1. Add Virtual Boundary Balloons

Prepend and append a balloon with value 1 to the array: vals = [1, ...nums, 1]
This simplifies boundary handling since out-of-bounds neighbors are treated as 1

2. Define the DP Subproblem

dp[left][right] = maximum coins obtainable by bursting all balloons strictly between index left and right in the vals array
The balloons at left and right themselves are not burst; they act as boundaries

3. Reverse the Thinking: Choose the LAST Balloon to Burst

Instead of choosing which balloon to burst first (which changes neighbors unpredictably), choose which balloon k to burst last in the range (left, right)
When k is the last to burst, its neighbors are exactly vals[left] and vals[right]
The coins from bursting k last: vals[left] * vals[k] * vals[right]
Plus the coins from the left subproblem dp[left][k] and right subproblem dp[k][right]

4. Iterate Over Increasing Range Sizes

Start with small ranges (length 2) and build up to the full range
For each range (left, right), try every possible k as the last balloon to burst
Take the maximum over all choices of k

5. Return the Result

dp[0][n-1] gives the maximum coins for bursting all original balloons (between the two virtual boundary balloons)

Key Insight

The crucial insight is thinking about the last balloon to burst in a range rather than the first, because the last balloon's neighbors are known (the boundaries)
This transforms an intractable problem into clean interval DP

Time

O(n^3) where n is the number of balloons

Space

O(n^2) for the DP table

Visualization

Input:

[3, 1, 5, 8]

—

No animation available

Left (L)Right (R)ConvergedDone

0 steps

Solution Code

Regular Expression Matching