Burst Balloons
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 ith 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, 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
Input: [3,1,5,8]
Output: 167
Input: [1,5]
Output: 10
Hints
Consider the problem as a dynamic programming (DP) problem where you need to find the optimal order of bursting balloons to maximize coins. Think about how to break down the problem into smaller subproblems.
Instead of thinking about bursting balloons one by one, think about the last balloon to burst. The last balloon to burst will have `1`s on its left and right (since all other balloons are already burst). Use this insight to define a DP state.
Define `dp[i][j]` as the maximum coins obtained by bursting all balloons between index `i` and `j` (inclusive). The recurrence relation should consider each balloon `k` in `[i, j]` as the last balloon to burst, and compute the coins accordingly. The final answer will be `dp[0][n-1]`.
Burst Balloons
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.