Classic DP: Burst Balloons
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 312. Burst Balloons | 🔴 |
Prerequisites
Before reading this article, you should first study:
Today, we will discuss the problem "Burst Balloon", which is similar to the "Classic Dynamic Programming: Egg Drop Problem" analyzed in our previous article Egg Drop Problem. This problem is well-known but also quite challenging.
It is LeetCode's Problem 312 "Burst Balloons", and the problem statement is 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
First, it must be noted that the state transition equation for this problem is quite ingenious. If you find yourself with no clue after reading the problem, it's perfectly normal. Although the optimal solution is not easy to conceive, we should strive to achieve a basic analysis of the approach. Therefore, this article will first analyze the conventional approach and then introduce the dynamic programming solution.
1. Backtracking Approach
Let's first outline the approach to solve this type of problem: