最后更新于
最后更新于
有 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
示例:
为了方便处理，我们对 nums 数组稍作处理，将其两边各加上题目中假设存在的 nums[−1] 和 nums[n] ，并保存在 val 数组中，即 val[i]=nums[i−1] 。之所以这样处理是为了处理 nums[−1] ，防止下标越界。
下文中的区间均指数组 val 上的区间。
我们观察戳气球的操作，发现这会导致两个气球从不相邻变成相邻，使得后续操作难以处理。于是我们倒过来看这些操作，将全过程看作是每次添加一个气球。 在区间中插入一个气球, 等价于在这个区间中最后一个戳爆这个气球, 但这种转变让我们有了递归的思路: 插入一个气球后, 我们以这个气球为边界, 将原来的区间划分成了左右两个子区间, 最终的数量等于两个区间的数量再加上这个气球对应的数量. 然后左右子区间递归计算.
我们定义方法 solve，令 solve(i,j) 表示将开区间 (i,j) 内的位置全部填满气球能够得到的最多硬币数。由于是开区间，因此区间两端的气球的编号就是 i 和 j，对应着 val[i] 和 val[j]。
当 i >= j - 1时，开区间中没有气球，solve(i,j) 的值为 0. 即左右断相邻, 区间长度为2. 因为我们考虑的是开区间, 区间端点对应的气球是不能被戳爆的, 因此要有这个限制, 否则区间内无气球插入的空间. 而且val[0]和val[n+1]也是假设出的, 值为1但不能被戳的气球
当 i < j - 1时，我们枚举开区间 (i,j)(i,j) 内的全部位置 \textit{mid}mid，令 \textit{mid}mid 为当前区间第一个添加的气球，该操作能得到的硬币数为 val[i]×val[mid]×val[j]。同时我们递归地计算分割出的两区间对 solve(i,j) 的贡献，这三项之和的最大值，即为 solve(i,j) 的值。这样问题就转化为求 solve(i,mid) 和 solve(mid,j) ，可以写出方程：
为了防止重复计算，我们存储 solve 的结果，使用记忆化搜索的方法优化时间复杂度。