Burst Balloons — Go Coding Problem
Difficulty: hard | Category: dynamic-programming
Problem Description
You are given `n` balloons, indexed from `0` to `n-1`. Each balloon is painted with a number on it represented by `nums[i]`. You are asked to burst all the balloons. If you burst balloon `i`, you will get `nums[i-1] * nums[i] * nums[i+1]` coins. If `i-1` or `i+1` goes out of bounds, 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.
Examples
Example 1
Input: nums = [3,1,5,8]
Output: 167
Explanation: Burst 1→3×1×5=15, then 5→3×5×8=120, then 3→1×3×8=24, then 8→1×8×1=8. Total = 167.
Example 2
Input: nums = [1,5]
Output: 10