Burst Balloons

The key idea

Instead of choosing which balloon to burst FIRST, choose which one is burst LAST in each range. The last balloon k in an open interval (i, j) is never bursting its neighbours, so its left and right multipliers are the fixed boundaries nums[i] and nums[j]. That splits the range into two independent subranges, which is the overlapping-subproblem structure dynamic programming needs.

Problem

You are given n balloons, indexed 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.

Constraints

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

Examples

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

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

Complexity

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

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →