分析一下这道题，就是要截破所有的气球，获得硬币的最大数量，然后左右两边的气球相邻了。那就截呗，我的第一反应就是暴力，回溯法；但是肯定会超时，为什么呢？因为题目给的气球数量有点多，最多 500 个；500 的阶乘，会超时爆栈；但是我们依然写一下代码，找下突破口，小伙伴们千万不要看不起暴力，暴力是优化的突破口；如果小伙伴对回溯法不太熟悉，我建议你记住下面的模版，也可以看我之前写的文章，回溯法基本可以使用以下的模版写。回溯法省心省力，0 智商负担，懂的朋友都懂，QAQ。

回溯法的缺点也很明显，复杂度很高，对应本题截气球；小伙伴们可以脑补一下执行过程的状态树，这里我偷个懒就不画了；通过仔细观察这个状态树，我们会发现这个状态树的【选择】上，会有一些重复的选择分支；很明显存在了重复子问题；自然我就想到了能不能用动态规划来解决；

判读能不能用动态规划解决，还有一个问题，就是必须存在最优子结构；什么意思呢？其实就是根据局部最优，推导出答案；假设我们截破第 k 个气球是最优策略的最后一步，和上一步有没有联系呢？根据题目意思，截破第 k 个，前一个和后一个就变成相邻的了，看似是会有联系，其实是没有的。因为截破第 k 个和 k-1 个是没有联系的，脑补一下回溯法的状态树就更加明确了；

那本题的【选择】是什么呢？就是截哪一个气球。那【状态】呢？就是题目给的气球数量。

- 这里有个细节，就是题目说明有两个虚拟气球，nums[-1] = nums[n] = 1；如果当前截破的气球是最后一个或者第一个，前面/后面没有气球了，不能乘以 0，而是乘以 1。

- 定义状态的最关键两个点，往子问题（问题规模变小）想，最后一步最优策略是什么；我们假设最后截破的气球是 k，截破 k 获得最大数量的银币就是 nums[i] _ nums[k] _ nums[j] 再加上前面截破的最大数量和后面的最大数量，即：nums[i] _ nums[k] _ nums[j] + 前面最大数量 + 后面最大数量，就是答案。

- 而如果我们不考虑两个虚拟气球而直接定义状态，截到最后两个气球的时候又该怎么定义状态来避免和前面的产生联系呢？这两个虚拟气球就恰到好处了，太细节了；这也是本题的一个难点之一。

- 那我们可以这样来定义状态，dp[i][j] = x 表示，戳破气球 i 和气球 j 之间（开区间，不包括 i 和 j）的所有气球，可以获得的最大硬币数为 x。为什么开区间？因为不能和已经计算过的产生联系，我们这样定义之后，利用两个虚拟气球，截到最后两个气球的时候就完美的避开了所有状态的联系，太细节了。

- 而对于 dp[i][j]，i 和 j 之间会有很多气球，到底该截哪个先呢？我们直接设为 k，枚举选择最优的 k 就可以了。

- 因为我们最终要求的答案是 dp[0][n + 1]，就是截破虚拟气球之间的所有气球获得的最大值；