(资料图)
【题目】
【例子】
【解析】
根据https://leetcode.com/problems/burst-balloons/solutions/892552/for-those-who-are-not-able-to-understand-any-solution-with-diagram/所写
首先容易想到的暴力解法(Brute Force)，即尝试所有的可能，时间复杂度为O(n!)，显然太大了，需要想其他的方法。
这道题目不容易想到使用动态规划的方法，因为难以想到递推公式。假设solve(i,j)表示从气球i到气球j的最大收益值，那么我们选择其中第k个首先戳爆的话，solve(i, j) = solve(i, k-1) + solve(k+1, j)，但是solve(i, k-1)与solve(k+1, j)并不是独立的，因为戳爆第k个之后，k-1与k+1的气球就会相邻，因此无法使用此递推公式。
不得不说作者非常天才，既然第k个首先戳爆不行，那就选择第k个最后戳爆，此时solve(i, k-1)与solve(k+1,j)相互独立不影响，而最后戳爆第k个气球获得的收益为nums[i-1] * nums[k] * nums[j+1]，因为此时k左右两边的气球为i第i-1个气球与第j+1个气球。此时我们只需要比较最后戳爆第k个气球(k=i, i+1, ...j)的收益，选择最大的即可。
同时，为了加速运算，可以使用空间换时间，使用memory数组记录下solve(i,j)的结果。
最终代码如下：