Veal98#CS-Wiki#312-戳气球1

# 312. 戳气球 --- 👉 [312. Burst Balloons — Hard](https://leetcode-cn.com/problems/burst-balloons/) ## 📜 题目描述 Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get `nums[left] * nums[i] * nums[right]` coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent. Find the maximum coins you can collect by bursting the balloons wisely. **Note**: You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them. 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100 **Example**: ``` Input: [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 ``` ## 💡 解题思路 > 🔈 该题用动态规划比分治法更好，详细请见动态规划模块 **分治法**：以 [3, 1, 5, 8] 为例 首先思考能不能直接将 [3, 1, 5, 8] 直接分为类似于 [3]、[1, 5, 8] 这样两个子问题。这意味着，