第六章 - 高频考题(困难)
0312. 戳气球

题目地址(312. 戳气球)

题目描述

1
有 n 个气球,编号为0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。
2
3
现在要求你戳破所有的气球。每当你戳破一个气球 i 时,你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后,气球 left 和气球 right 就变成了相邻的气球。
4
5
求所能获得硬币的最大数量。
6
7
说明:
8
9
你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的所以并不能被戳破。
10
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
11
示例:
12
13
输入: [3,1,5,8]
14
输出: 167
15
解释: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
16
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
Copied!

前置知识

  • 回溯法
  • 动态规划

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

回溯法(超时)

回溯法

这道题就是要戳破所有的气球,求获得硬币的最大数量。我的第一反应就是暴力回溯。
但是这种暴力算法肯定会超时,为什么呢?因为题目给的气球数量有点多,最多 500 个;500 的阶乘,会超时爆栈;但是我们依然写一下代码,找下突破口,小伙伴们千万不要看不起暴力,暴力是优化的突破口;
如果小伙伴对回溯法不太熟悉,我建议你记住下面的模版,也可以看我之前写的文章,回溯法基本可以使用以下的模版写。

代码

1
var maxCoins = function (nums) {
2
let res = Number.MIN_VALUE;
3
backtrack(nums, 0);
4
return res;
5
// 回溯法,状态树很大
6
function backtrack(nums, score) {
7
if (nums.length == 0) {
8
res = Math.max(res, score);
9
return;
10
}
11
for (let i = 0, n = nums.length; i < n; i++) {
12
let point =
13
(i - 1 < 0 ? 1 : nums[i - 1]) *
14
nums[i] *
15
(i + 1 >= n ? 1 : nums[i + 1]);
16
let tempNums = [].concat(nums);
17
// 做选择 在 nums 中删除元素 nums[i]
18
nums.splice(i, 1);
19
// 递归回溯
20
backtrack(nums, score + point);
21
// 撤销选择
22
nums = [...tempNums];
23
}
24
}
25
};
Copied!

动态规划

思路

回溯法的缺点也很明显,复杂度很高,小伙伴们可以脑补一下执行过程的状态树,这里我偷个懒就不画了;
通过仔细观察这个状态树,我们会发现这个状态树的【选择】上,会有一些重复的选择分支;很明显存在了重复子问题;自然我就想到了能不能用动态规划来解决;
判读能不能用动态规划解决,还有一个问题,就是必须存在最优子结构;什么意思呢?其实就是根据局部最优,推导出答案;假设我们戳破第 k 个气球是最优策略的最后一步,和上一步有没有联系呢?根据题目意思,戳破第 k 个,前一个和后一个就变成相邻的了。由于这种不稳定性,导致问题难以处理。一种解决方案是反向思考。即我们不是给你一个 nums,一个个移除数。而是从空数组开始一个个添加。
由于题目说明了 nums 左右各存在一个虚拟的气球,因此这里说的空数组实际指的是 [1,1] 这种情况,即只有两个虚拟数字。
经过这样的反向思考,问题就变得简单起来了。经过这样的思考之后就使用动态规划解决就 ok 了。
既然用动态规划,那就老套路了,把动态规划的三个问题想清楚定义好;然后找出题目的【状态】和【选择】,然后根据【状态】枚举,枚举的过程中根据【选择】计算递推就能得到答案了。
那本题的【选择】是什么呢?就是戳哪一个气球。那【状态】呢?就是题目给的气球数量。
  1. 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. 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. 1.
    初始值和边界
由于我们利用了两个虚拟气球,边界就是气球数 n + 2,当 i == j 时,很明显两个之间没有气球,为 0;
  1. 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:
1
var maxCoins = function (nums) {
2
let n = nums.length;
3
// 添加两侧的虚拟气球
4
let points = [1, ...nums, 1];
5
let dp = Array.from(Array(n + 2), () => Array(n + 2).fill(0));
6
// 最后一行开始遍历,从下往上
7
for (let i = n; i >= 0; i--) {
8
// 从左往右
9
for (let j = i + 1; j < n + 2; j++) {
10
for (let k = i + 1; k < j; k++) {
11
dp[i][j] = Math.max(
12
dp[i][j],
13
points[j] * points[k] * points[i] + dp[i][k] + dp[k][j]
14
);
15
}
16
}
17
}
18
return dp[0][n + 1];
19
};
Copied!
Python Code:
1
class Solution:
2
def maxCoins(self, nums: List[int]) -> int:
3
n = len(nums)
4
points = [1] + nums + [1]
5
dp = [[0] * (n + 2) for _ in range(n + 2)]
6
7
for i in range(n, -1, -1):
8
for j in range(i + 1, n + 2):
9
for k in range(i + 1, j):
10
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + points[i] * points[k] * points[j])
11
return dp[0][-1]
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n ^ 3)$
  • 空间复杂度:$O(n ^ 2)$
如果使用记忆化递归,时间复杂度和上面一样,空间复杂度是 $O(n)$,但是在力扣提交会超时,大家作为参考即可。
Python3 Code:
1
class Solution:
2
def maxCoins(self, nums: List[int]) -> int:
3
n = len(nums)
4
nums = [1] + nums + [1]
5
6
@lru_cache(None)
7
def dp(left, right):
8
if left + 1 == right:
9
return 0
10
if left + 2 == right:
11
return nums[left] * nums[left + 1] * nums[left + 2]
12
ans = 0
13
for i in range(left + 1, right):
14
ans = max(ans, nums[i] * nums[left] * nums[right] + dp(left, i) + dp(i, right))
15
return ans
16
17
return dp(0, len(nums) - 1)
Copied!

相关题目

总结

简单的 dp 题目会直接告诉你怎么定义状态,告诉你怎么选择计算,你只需要根据套路判断一下能不能用 dp 解题即可,而判断能不能,往往暴力就是突破口。
这道题如果从空数组反向思考,则避免了因为数组变化导致的状态变化而难以处理的问题,是一种常见的技巧。另外此题属于典型的分割 DP 问题。区间问题通常都是两层循环枚举所有的左右端点,再用一层循环枚举所有的割点,也就是三层循环,时间复杂度也是 $O(n^3)$。
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 30K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。