[312][困难][分治][递归][动态规划] 戳气球

题目描述

312. 戳气球

有 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

解题思路

戳气球

分治递归

为了方便处理，我们对 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) ，可以写出方程：

  $$\textit{solve}(i,j)= \begin{cases}{} \displaystyle \max_{\textit{mid} = i + 1}^{j - 1}val[i] \times \textit{val}[\textit{mid}] \times \textit{val}[j] + \textit{solve}(i, \textit{mid}) + \textit{solve}(\textit{mid}, j) ,&i < j - 1 \\ 0, & i \geq j - 1 \end{cases}$$

  ​ 为了防止重复计算，我们存储 solve 的结果，使用记忆化搜索的方法优化时间复杂度。

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        val = [1] + nums + [1]

        @lru_cache(None)
        def coins(left, right):
            if left >= right - 1:  # left在左侧紧邻right就触发终止条件
                return 0

            best = 0
            for i in range(left + 1, right):
                total = val[left] * val[i] * val[right]
                total += coins(left, i) + coins(i, right)
                best = max(best, total)
            return best

        return coins(0, n + 1)