(力扣每日一题)戳气球_力扣戳气球

戳气球

有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。

说明:
你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

解题思路
1、我们倒过来看这些操作，将全过程看作是每次添加一个气球。
2、定义方法solve，令 solve(i,j) 表示将开区间 (i,j) 内的位置全部填满气球能够得到的最多硬币数。
3、由于是开区间，因此区间两端的气球的编号就是 i和 j，对应着 val[i] 和 val[j]。
a、当 i≥j−1 时，开区间中没有气球，solve(i,j) 的值为 0；
b、当 i < j-1 时，我们枚举开区间 ( i , j )内的全部位置 mid，令 mid 为当前区间第一个添加的气球，该操作能得到的硬币数为 val[i]×val[mid]×val[j]。
我们递归地计算这三项之和的最大值，即为solve(i,j) 的值。

图示（来源力扣）：