312戳气球——力扣算法系列2020.07.19 Python_力扣戳气球python

第25天
2020.07.19 周日
难度系数：困难
题目：有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

示例:

输入: [3,1,5,8]
输出: 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
1
2
3
4
5
6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/burst-balloons
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
——————————我是分割线——————————
解法：
思路一：记忆化搜索（暴力）
首先在nums两边加上nums[-1]和nums[n]，值为1。
正向戳气球->反向加气球。
定义方法solve，令solve(i,j)表示开区间(i,j)内的全部位置填满气球能得到的最多的硬币数。
i>=j-1，开区间中无气球（i、j只差1，中间没有东西），solve(i,j)=0。
i<j-1，枚举(i,j)内所有位置mid，令mid为当前区间第一个添加的气球，将得到val[i]*val[mid]*val[j]个硬币。递归算出被分割开的两个区间solve(i,mid)和solve(mid,j)对solve(i,j)的贡献，这三项的和的最大值即为solve(i,j)的值。

以[3,1,5,8]为例（下面的图来源于力扣！）：