[Leetcode 312] Burst Balloons

作者 Shilei Tian 日期 2017-01-03
[Leetcode 312] Burst Balloons

题目要求

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

  1. You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
  2. $0 \leq n \leq 500$, $0 \leq nums[i] \leq 100$

Example:

Given [3, 1, 5, 8]

Return 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

解题思路

这道题拿过来我第一反应是暴力枚举,或者说是递归。但是看到 n 的范围后,想都不用想如果用递归肯定超时,或者直接跑爆内存。

第二反应吧,就是动态规划,可是动态规划必须在每一步都能拆成立两个独立子结构,但是这一题呢,如果假设第 i 个气球爆炸,确实能够拆成 i 左边和右边两个子结构,但是此时这两个子结构并不是独立的,因为第 i-1 个气球和第 i+1 个气球就变成相邻的了,这样爆炸这两个气球的时候将会相互依赖。

想了半天想不出来,只好看看 Top Solutions 里面各路大神都是如何解答这道题目了,排名第一的是一篇名为 “Share some analysis and explanations” 的文章,读下来以后发现作者的想法变化和我是比较类似的,刚开始也是考虑的递归,后来才考虑了动态规划。在考虑了动态规划以后,也是发现不能直接拆成两个独立子结构。下面就是重点了。我们上面说考虑第 i 个气球爆炸,此时产生的收益是确定的,即 $nums[i-1] \times nums[i] \times nums[i+1]$,然后产生的两子结构。如果假设第 i 个气球是最后爆炸,产生的收益也是固定的,为 $nums[-1] \times nums[i] \times nums[n]$,其中 $nums[-1]=nums[n]=1$,而此时生成的左右两个子结构就是相互独立的,因为它们都有了自己的边界:左边的子结构从它的最左边开始到 i,右边的子结构从 i 开始到它的最右边。注意,这里 i 在两个子结构中作为边界,指的是在考虑这两个子结构的时候,就不把它的爆炸考虑在内了。原问题的边界分别是 -1n,因为我们不需要真正爆炸这两个气球,它们是虚拟的。

我们设置一个二维数组 dp[n][n],其中的元素 dp[i][j] 表示的是我们可以爆炸的气球的范围是 ij 时产生的收益,那么我们最终只需要返回 dp[0][n-1] 就好。

具体的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int maxCoins(vector<int>& _nums) {
vector<int> nums;
nums.push_back(1);
for (auto num : _nums) {
if (num) {
nums.push_back(num);
}
}
nums.push_back(1);
vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));
for (int len = 2; len < nums.size(); ++len) {
for (int left = 0; left + len < nums.size(); ++left) {
int right = left + len;
for (int i = left + 1; i < right; ++i) {
dp[left][right] = max(dp[left][right], nums[i] * nums[left] * nums[right] + dp[left][i] + dp[i][right]);
}
}
}
return dp[0][nums.size() - 1];
}
};

总结

“Share some analysis and explanations” 的作者说,这是一种“逆向思维”,这种思维在动态规划中用的还是蛮多的,所以要好好深入地理解这道题目,为以后动态规划的问题打下扎实的基础。