Burst Balloons

Hard

Arrays Dynamic Programming Dynamic Programming

Problem

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.

Constraints

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

Examples

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

Output: 167

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

Input: nums = [1,5]

Output: 10

We can burst balloon 0 first (1×1×5 = 5) then balloon 1 (1×5×1 = 5), or burst balloon 1 first (1×5×1 = 5) then balloon 0 (1×1×1 = 1). The first order gives 10 coins total.

Loading...

Loading Python...