LeetCode 312 - Burst Balloons

作者 QIFAN 日期 2017-01-03
LeetCode 312 - Burst Balloons

原题链接:312. Burst Balloons


题干

给定 n 个气球,位置从 0 到 n - 1 。有一个数组 nums 代表每个气球上的数字。

每戳破一个气球 i ,可以得到 nums[left] * nums[i] * nums[right] 个硬币。戳破后,left 和 right 就成了相邻的。

求戳破所有气球可以得到的最多硬币数量。

前提:

  1. nums[-1] = nums[n] = 1 ,它们不能被戳破
  2. 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

思路

到手不知道怎么做,但有一点确定,先去戳小的,让大的尽可能被相邻。那样是不是从小开始戳起就可以了呢?当戳的是起始或者末尾,需要因为它们都有一个相邻的数字是 1 ,那就需要比较一下。

看见一篇很好的思路历程 Share some analysis and explanations 。大致跟着这位 po 主的思路来走一遍。

  1. 简单粗暴
    一开始完全不知道该怎么用动态规划做,于是从最 naive 的想法开始:有 n 个气球,也就是说有 n 步,在第 i 步,有 n - i 个气球要戳破。也就是说,如果要列出所有情况比较,我们需要 $O(n!)$ ,这无疑是很慢的。
    所以我们需要找出重复工作,并试着优化。
    我们发现,对于任何气球,maxCoins 不依赖与已经戳破的气球。这提示我们可以采用 memorization (自上而下)或者动态规划(自下而上),从数量少的气球数计算到 n 个气球。对于 k 个球,有 $C_n^K$ 种情况,需要每次对每种情况进行比较,还是很大。这比 $O(n!)$ 稍好一些,但比 $O(2^n)$ 多。

  2. 优化思路
    通过上面的分析,感觉这些都可以看成是一个个相似的子问题,是不是可以用 divide and conquer (类似于递归的概念)?
    顺着这个想法自然的会想到可以这样分割问题:戳破一个气球,在将数组分成左右两个部分。但是,在这个问题里,被戳破气球左右的气球会在下一步变成相邻气球,并对 maxCoins 造成影响,所以这个想法不通。
    那如果倒过来想呢?如果从最后被戳破的气球开始想起呢?这样就通了!为什么?因为只有最后一个戳破的气球我们可以确定它的左右气球!并且以被戳破的气球为边界,可以去选择上一个被戳破的气球,而他们互不影响!这样就可以用递归来解决每个子问题了。
    以上面的 [3,1,5,8] 为例,
    若最后戳 5 ,数组状态为[5] ,coins = 1 5 1 = 5;
    5 的左边,最后戳 3 ,数组状态为 [3,5] , coins = 1 3 5 = 15;
    5 的右边,最后戳 8 ,数组状态为 [3,5,8] , coins = 5 8 1 = 40;
    3 的右边没有
    3 的左边,最后戳 1 ,数组状态为 [3, 1, 5, 8] ,Coins = 3 1 5 = 15;
    每次选择都已经知道左右邻居。

  3. 最终方案
    知道了方案,代码也不太好写。关键在于怎么去存储已知的信息避免重复运算。相邻的气球其实就像左边界与右边界,是不是有点像二分查找?边界若是定下来,那这一段气球能够产生的最大硬币数也是确定的。

时间复杂度 $O(n^3)$ ,这个为啥子呢?

代码:

public int maxCoins(int[] iNums) {
int[] nums = new int[iNums.length + 2];
int n = 1;
// 先去除所有数字为 0 的气球
for (int x : iNums) {
if (x > 0) nums[n++] = x;
}
nums[0] = nums[n++] = 1;
int[][] memo = new int[n][n];
return burst(memo, nums, 0, n - 1);
}
public int burst(int[][] memo, int[] nums, int left, int right) {
// base case
if (left + 1 == right) {
return 0;
}
if (memo[left][right] > 0) {
return memo[left][right];
}
int ans = 0;
// 总硬币数 = 戳破该气球的硬币+ 戳破左边部分的硬币 + 戳破右边部分的硬币
for (int i = left + 1; i < right; ++i) {
ans = Math.max(ans,
nums[left] * nums[i] * nums[right] + burst(memo, nums, left, i) + burst(memo, nums, i, right));
}
memo[left][right] = ans;
return ans;
}

看了这一段分析,简直不能更清晰。如果我有这样的思考历程就好啦!
下面的评论也很搞笑:”…. If my interviewer test this problem on me? Do they even believe that I could solve this without knowing beforehand in 45 mins? I don’t know they believe or not. I don’t.” 要我我也不信哈哈哈哈。