// Burst Balloons — HARD

// Category: dynamic-programming

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.

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

Output: 167