Classic DP: Burst Balloons
Note
Now all the plugins has supported English. I'm still improving the website...
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 312. Burst Balloons | 🔴 |
Today, we're going to discuss the problem "Burst Balloon," which is similar to the "Egg Dropping from a High Building" problem we analyzed in Classic Dynamic Programming: Egg Dropping Problem. It's quite well-known but also quite challenging.
This is LeetCode problem #312, "Burst Balloons," described as follows:
312. Burst Balloons | LeetCode |
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, then 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 1:
Input: nums = [3,1,5,8] Output: 167 Explanation: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
Example 2:
Input: nums = [1,5] Output: 10
Constraints:
n == nums.length1 <= n <= 3000 <= nums[i] <= 100
Firstly, it must be mentioned that the state transition equation for this problem is quite ingenious. So, if you have no idea after reading the problem, that's actually normal. While the optimal solution may not be easy to come up with, a basic analysis of the approach is something we should strive for. Therefore, this article will first analyze the conventional approach and then introduce the dynamic programming solution.
I. Backtracking Approach
Let's first outline the general approach to solving this kind of problem: