# 经典动态规划：戳气球

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

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 `i`

balloon, you will get ^{th}`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:167Explanation: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.length`

`1 <= n <= 300`

`0 <= 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: