Burst Balloons
Mastery
There are balloons with numbers nums[i]. Bursting balloon i gives nums[i - 1] * nums[i] * nums[i + 1] coins, where i - 1 and i + 1 are the neighbours that are still there (a missing neighbour counts as a balloon with number 1). Burst all balloons in the best order and return the maximum coins.
For [3, 1, 5, 8] the answer is 167.
The starter code tries every order. It is correct but too slow for more than a few balloons.
Examples
Example 1
Input:
max_coins([3, 1, 5, 8])
Output:
167
Example 2
Input:
max_coins([1, 5])
Output:
10
Constraints
0 <= len(nums) <= 1200 <= nums[i] <= 100
Theory
Go to TheoryKeywords
dsa-sheetdynamic-programmingintervals-and-states
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.