# [Leetcode 312] Burst Balloons

[Leetcode 312] 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:

1. You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
2. $0 \leq n \leq 500$, $0 \leq nums[i] \leq 100$

Example:

Given [3, 1, 5, 8]

Return 167

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

### 总结

“Share some analysis and explanations” 的作者说，这是一种“逆向思维”，这种思维在动态规划中用的还是蛮多的，所以要好好深入地理解这道题目，为以后动态规划的问题打下扎实的基础。