How do you approach Burst Balloons (Interval DP)?

Going forwards (which balloon to burst first) is hard because the neighbours change.

What is the time complexity of Burst Balloons (Interval DP)?

Time complexity: O(n^3). Space complexity: O(n^2).

What are common mistakes on Burst Balloons (Interval DP)?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Burst Balloons (Interval DP)

HardAlgorithms

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 `i`-th 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.

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

Burst Balloons (Interval DP): approach, complexity and pitfalls

A hard dynamic programming problem, graded against 5 test cases (2 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 3-step hint ladder

Going forwards (which balloon to burst first) is hard because the neighbours change.
Reverse the order: dp[i][j] = max coins from open interval (i, j) where i and j are balloons that *survive*. The last balloon burst inside (i, j) is bordered exactly by i and j.
Pad nums with 1 on both ends so all sub-problems have valid boundaries.

The optimal approach

Show the approach: Interval DP (Burst-Last)

Pad nums with 1 on both ends. Let `dp[i][j]` = max coins obtainable from bursting all balloons strictly between i and j, where `balloons[i]` and `balloons[j]` have not been burst.

Choose the *last* balloon `k` to burst inside `(i, j)`. By the time it's last, the only balloons left in that range are `k` itself with neighbours `i` and `j`. So

```

dp[i][j] = max over k in (i, j) of dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]

```

Iterate by increasing range length. Final answer is `dp[0][n+1]` of the padded array.

Time: O(n^3)
Space: O(n^2)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.