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:

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

Example:

1
2
3
4
Input: [3,1,5,8]
Output: 167
Explanation: 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。问该以什么顺序戳气球得到的奖励最大

最笨的思路

枚举法:将所有的情况列举一遍。当有n个气球的时候,第一步我们有n种选择,第二步我们又有n-1个选择……显然全枚举的算法复杂度为$O(N!)$,效率不敢恭维,因此这里就不实现——因为不可能过。

参阅

进一步想法

我们需要去考虑上面枚举法做了什么重复的计算。我们可以想到,给定一组气球,它所能获得的最大的奖励应该和前面已经被戳的气球无关——被戳过的气球只是在求和的时候累积上了而已。

对于给定k<n, 其可能的组合数有 $C_n^k$ 种,我们可以把k(从1开始)的所有情况都记录在内存上,k+1就可以基于k进行计算,那么我们总共需要进行的计算就是
$$C_n^1+C_n^2+…+C_n^n$$
这种算法优于$O(N!)$, 但仍然坏于$O(2^N)$; 我们需要更优的算法

分治的想法

我们考虑用分治去思考这一道题。先是正常地考虑分治,我戳爆某个气球,可不可以把剩下的气球分成两堆呢?这是否可行的前提是两堆会不会互相干扰:答案是肯定的,在戳爆某个气球以后,左堆的最右气球会需要右堆的最左气球来进行计算。

这时候我们需要反向的思维:我们正向地想戳气球的过程,当然会导致两堆相互影响。那如果我们考虑的是在这一堆里最后戳爆的那个气球呢?假如A,B,C,D,E中我最后戳C, 那左堆(A,B)在戳的过程中显然会以C为右边界,而右堆(D,E)以C为左边界——这就实现了分治,两个子问题是相互不干扰的。

想一下为什么分治会更好,它少算了哪些步骤

定义一个函数 burst(left, right),它的值表示以left right分别为左右边界的时候 [left,right]所能得到的最大的奖励值。这里需要说明的是这里定义的左右边界都需要晚于中间的任意气球被戳,那样在剩下的气球(i)里任意选取一个作为倒数第三(边界是倒数一、二,顺序不重要,只要知道它会比中间的数晚戳就行)去戳,那它又能成为左右两个新区间的新边界,则这样戳所能得到的最大值是

1
nums[left]*nums[i]*nums[right] + burst(left,i) + burst(i,right)

这样我们只要遍历每个 i in (left,right) 去求出上述等式并得到最大值,那就得到了 burst(left, right) 的最大值

还有一些细节:

  • 假设 nums[-1]=nums[n]=1,这样两个假边界就显然是整组气球里“最晚被戳的气球”了
  • 当两个边界相邻,说明中间无球可戳,所以应该有burst(i,i+1)=0

按照上面说的就可以实现如下具体的算法了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int maxCoins(int[] iNums) {
int[] nums = new int[iNums.length + 2];
int n = 1;
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) {
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;
}
// 12 ms
Donate
  • Copyright: Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2015-2024 Jeff
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信