You are given $n$ balloons, numbered from $0$ to $n - 1$. Each balloon has a number painted on it, represented by an integer array nums.

When you burst a balloon $i$, you earn coins equal to nums[i - 1] * nums[i] * nums[i + 1].
If either $i - 1$ or $i + 1$ is out of bounds, assume there is a virtual balloon with the number $1$ in its place.

Your task is to burst all the balloons to collect the maximum number of coins possible.

Return the maximum coins you can obtain by bursting the balloons in an optimal order.

Constraints:

• $n ==$ nums.length

• $1 \leq n \leq$ 300

• $0 \leq$ nums[i] $\leq 100$

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.