0312. 戳气球

题目地址(312. 戳气球)

https://leetcode-cn.com/problems/burst-balloons/

题目描述

有 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

前置知识

  • 回溯法

  • 动态规划

公司

  • 阿里

  • 腾讯

  • 百度

  • 字节

回溯法(超时)

回溯法

这道题就是要戳破所有的气球,求获得硬币的最大数量。我的第一反应就是暴力回溯。

但是这种暴力算法肯定会超时,为什么呢?因为题目给的气球数量有点多,最多 500 个;500 的阶乘,会超时爆栈;但是我们依然写一下代码,找下突破口,小伙伴们千万不要看不起暴力,暴力是优化的突破口;

如果小伙伴对回溯法不太熟悉,我建议你记住下面的模版,也可以看我之前写的文章,回溯法基本可以使用以下的模版写。

代码

var maxCoins = function (nums) {
  let res = Number.MIN_VALUE;
  backtrack(nums, 0);
  return res;
  // 回溯法,状态树很大
  function backtrack(nums, score) {
    if (nums.length == 0) {
      res = Math.max(res, score);
      return;
    }
    for (let i = 0, n = nums.length; i < n; i++) {
      let point =
        (i - 1 < 0 ? 1 : nums[i - 1]) *
        nums[i] *
        (i + 1 >= n ? 1 : nums[i + 1]);
      let tempNums = [].concat(nums);
      // 做选择 在 nums 中删除元素 nums[i]
      nums.splice(i, 1);
      // 递归回溯
      backtrack(nums, score + point);
      // 撤销选择
      nums = [...tempNums];
    }
  }
};

动态规划

思路

回溯法的缺点也很明显,复杂度很高,小伙伴们可以脑补一下执行过程的状态树,这里我偷个懒就不画了;

通过仔细观察这个状态树,我们会发现这个状态树的【选择】上,会有一些重复的选择分支;很明显存在了重复子问题;自然我就想到了能不能用动态规划来解决;

判读能不能用动态规划解决,还有一个问题,就是必须存在最优子结构;什么意思呢?其实就是根据局部最优,推导出答案;假设我们戳破第 k 个气球是最优策略的最后一步,和上一步有没有联系呢?根据题目意思,戳破第 k 个,前一个和后一个就变成相邻的了。由于这种不稳定性,导致问题难以处理。一种解决方案是反向思考。即我们不是给你一个 nums,一个个移除数。而是从空数组开始一个个添加。

由于题目说明了 nums 左右各存在一个虚拟的气球,因此这里说的空数组实际指的是 [1,1] 这种情况,即只有两个虚拟数字。

经过这样的反向思考,问题就变得简单起来了。经过这样的思考之后就使用动态规划解决就 ok 了。

既然用动态规划,那就老套路了,把动态规划的三个问题想清楚定义好;然后找出题目的【状态】和【选择】,然后根据【状态】枚举,枚举的过程中根据【选择】计算递推就能得到答案了。

那本题的【选择】是什么呢?就是戳哪一个气球。那【状态】呢?就是题目给的气球数量。

  1. 定义状态

这里有个细节,就是题目说明有两个虚拟气球,nums[-1] = nums[n] = 1;如果当前戳破的气球是最后一个或者第一个,前面/后面没有气球了,不能乘以 0,而是乘以 1。

定义状态的最关键两个点,往子问题(问题规模变小)想,最后一步最优策略是什么;我们假设最后戳破的气球是 k,戳破 k 获得最大数量的银币就是 nums[i] * nums[k] * nums[j] 再加上前面戳破的最大数量和后面的最大数量,即:nums[i] * nums[k] * nums[j] + 前面最大数量 + 后面最大数量

那我们可以这样来定义状态,dp[i][j] = x 表示:戳破气球 i 和气球 j 之间(开区间,不包括 i 和 j)的所有气球,可以获得的最大硬币数为 x。为什么开区间?因为不能和已经计算过的产生联系,我们这样定义之后,利用两个虚拟气球 就可完成本题。

  1. 状态转移方程

而对于 dp[i][j],i 和 j 之间会有很多气球,到底该戳哪个先呢?我们直接设为 k,枚举选择最优的 k 就可以了。所以,最终的状态转移方程为:dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[k] * nums[i] * nums[j])。由于是开区间,因此 k 为 i + 1, i + 2... j - 1。

这就是典型的枚举分割点 ”区间 DP“,大家一定要掌握哦~

  1. 初始值和边界

由于我们利用了两个虚拟气球,边界就是气球数 n + 2,当 i == j 时,很明显两个之间没有气球,为 0;

  1. 如何枚举状态

因为我们最终要求的答案是 dp[0][n + 1],就是戳破虚拟气球之间的所有气球获得的最大值。当 i == j 时,i 和 j 之间是没有气球的,所以枚举的状态很明显是 dp table 的左上部分,也就是 j 大于 i,如下图所示,只给出一部分方便思考。

图有错误。图中 dp[k][i] 应该是 dp[i][k],dp[j][k] 应该是 dp[k][j]

从上图可以看出,我们需要从下到上,从左到右进行遍历。

关键点

  • 区间 DP

  • 反向思考。不是戳气球,而是添加气球。

  • 遍历方向的确定

代码

代码支持: JS, Python

JS Code:

var maxCoins = function (nums) {
  let n = nums.length;
  // 添加两侧的虚拟气球
  let points = [1, ...nums, 1];
  let dp = Array.from(Array(n + 2), () => Array(n + 2).fill(0));
  // 最后一行开始遍历,从下往上
  for (let i = n; i >= 0; i--) {
    // 从左往右
    for (let j = i + 1; j < n + 2; j++) {
      for (let k = i + 1; k < j; k++) {
        dp[i][j] = Math.max(
          dp[i][j],
          points[j] * points[k] * points[i] + dp[i][k] + dp[k][j]
        );
      }
    }
  }
  return dp[0][n + 1];
};

Python Code:

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        points = [1] + nums + [1]
        dp = [[0] * (n + 2) for _ in range(n + 2)]

        for i in range(n, -1, -1):
            for j in range(i + 1, n + 2):
                for k in range(i + 1, j):
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + points[i] * points[k] * points[j])
        return dp[0][-1]

复杂度分析

令 n 为数组长度。

  • 时间复杂度:$O(n ^ 3)$

  • 空间复杂度:$O(n ^ 2)$

如果使用记忆化递归,时间复杂度和上面一样,空间复杂度是 $O(n)$,但是在力扣提交会超时,大家作为参考即可。

Python3 Code:

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

        @lru_cache(None)
        def dp(left, right):
            if left + 1 == right:
                return 0
            if left + 2 == right:
                return nums[left] * nums[left + 1] * nums[left + 2]
            ans = 0
            for i in range(left + 1, right):
                ans = max(ans, nums[i] * nums[left] * nums[right] + dp(left, i) + dp(i, right))
            return ans

        return dp(0, len(nums) - 1)

相关题目

总结

简单的 dp 题目会直接告诉你怎么定义状态,告诉你怎么选择计算,你只需要根据套路判断一下能不能用 dp 解题即可,而判断能不能,往往暴力就是突破口。

这道题如果从空数组反向思考,则避免了因为数组变化导致的状态变化而难以处理的问题,是一种常见的技巧。另外此题属于典型的分割 DP 问题。区间问题通常都是两层循环枚举所有的左右端点,再用一层循环枚举所有的割点,也就是三层循环,时间复杂度也是 $O(n^3)$。

更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 30K star 啦。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。

最后更新于