LESSON 508 OF 642 · DYNAMIC PROGRAMMING

Burst Balloons in Rust

Practice O(n³)

You get an array nums. It holds the numbers on a row of balloons, from left to right.

You burst the balloons one at a time, in any order you choose. Return the most coins you can collect.

Bursting a balloon pays its number times the numbers of its two neighbours. Its neighbours are the nearest balloons still in the row. When no balloon is left on one side, that side counts as 1.

Example 1:

Input: nums = [2,4,3]
Output: 33
Explanation: Burst the 4 first: 2 × 4 × 3 = 24 coins.
The row is now [2,3].
Burst the 2 next: 1 × 2 × 3 = 6 coins.
Burst the 3 last: 1 × 3 × 1 = 3 coins.
In total, 24 + 6 + 3 = 33.

Example 2:

Input: nums = [1,8,1]
Output: 24
Explanation: Burst the first 1: 1 × 1 × 8 = 8 coins.
Burst the other 1: 8 × 1 × 1 = 8 coins.
Burst the 8 last: 1 × 8 × 1 = 8 coins.
In total, 8 + 8 + 8 = 24.
Bursting the 8 first gives only 8 + 1 + 1 = 10.

Example 3:

Input: nums = [3,0,4]
Output: 16
Explanation: Burst the 0 first: 3 × 0 × 4 = 0 coins.
Burst the 3 next: 1 × 3 × 4 = 12 coins.
Burst the 4 last: 1 × 4 × 1 = 4 coins.
In total, 0 + 12 + 4 = 16.

Constraints:

nums holds 1 to 300 numbers.
Each number is a whole number from 0 to 100.

Note:

Your solution should run in O(n³) time. Here n is the length of nums.

Trying every order is far too slow. Ten balloons already have 3,628,800 orders.
Look at one range of the row instead, and ask which balloon in it bursts last. Until it bursts, it stands between its left part and its right part. So the two parts never touch, and each one is a smaller problem of the same kind.

Add a 1 at each end of the row, and call the new list values. Its two ends are never burst.
Let best[left][right] be the most coins from bursting every balloon strictly between left and right, while those two stay.
If balloon last bursts last in that range, its neighbours are left and right by then. It pays values[left] × values[last] × values[right]. The parts on its two sides add best[left][last] and best[last][right].
Try every last and keep the largest total. Fill the short ranges before the long ones. The answer is best[0][n - 1], where n is the length of values.

There are about n² / 2 ranges. Each one tries up to n balloons as the last one. That is O(n³) time.
The table best takes O(n²) space.

STEP 1 OF 10

Guided

Ctrl + Enter to check