312. Burst Balloons

  • 41.9%

https://leetcode.com/problems/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 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

1
2
3
4
5
6
7
8
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个。

重点是逆向思考,先第n个,再第n-1个,直到第一个。

一个vector<vector> dp

dp[left][right]表示索引left至索引right里面,不戳破left和right,戳破[left+1, right-1]中任意顺序能获得的最大值。

假定最后戳破某一位i,则得到奖励nums[left]nums[i]nums[right],并且获得dp[left][i]和dp[i][right]。而dp[i][left]又是类似于前一个问题,而且跟i关系不大。

下面两个方法分别是递归和迭代

方法一:

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int maxCoins(vector<int>& nums) {
if(nums.empty()) return 0;
// insert插入时,第一位位置要使用迭代器
nums.insert(nums.begin(), 1);
nums.push_back(1);
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(n, -1));
return dfs(nums, 0, n-1, dp);
}

int dfs(vector<int>& nums, int left, int right, vector<vector<int>>& dp){
if(left+1==right){
dp[left][right] = 0;
return 0;
}
// 不要忘了这句话,不然超时
if(dp[left][right]>=0)
return dp[left][right];
// 使用变量前先声明
int ans = 0;
for(int i=left+1; i<right; i++)
ans = max(ans, nums[left]*nums[i]*nums[right]+dfs(nums, left, i, dp)+dfs(nums, i, right, dp));
dp[left][right] = ans;
return ans;
}
};

方法二:

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int maxCoins(vector<int>& nums) {
if(nums.empty()) return 0;
nums.insert(nums.begin(), 1);
nums.push_back(1);
// 不要忘了声明
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(n, -1));
for(int len=2; len<=n; len++){
// 比较大小时,用<= 而不用 !=
for(int left=0; left+len<=n; left++){
int right = left + len - 1;
int ans = 0;
for(int i=left+1; i!=right; i++)
ans = max(ans, nums[left]*nums[i]*nums[right]+dp[left][i]+dp[i][right]);
dp[left][right] = ans;
}
}
return dp[0][n-1];
}
};

方法一和方法二参考以下文章

https://discuss.leetcode.com/topic/41086/c-dp-detailed-explanation

C++ dp detailed explanation

the visualization help me to understand hope it can help you too.

1···················1

add two 1 at beginning and end of nums, each · represent each number in nums.

len is the subinterval length, it grows from 1 to full length of orignal nums string.

the following illustrations demonstrate how the subinterval shift from left to right. (len = 7 in the illustration)

for each len, when shifted to rightmost, increase len and do the shift again. this way we can evaluate all possible subintervals.

for each subinterval, in the innermost for loop, find which balloon to burst LAST that will give us the most coins for that subinterval. <- IMPORTANT TO UNDERSTAND THIS

dp[left][right] is the maximum coins we can get from left to right. note when left > right, it is 0

1
2
3
4
5
6
7
8
9
10
11
1···················1    (len = 7)
| |
left right

1···················1
| |
left right

1···················1
| |
left right

for the example [3, 1, 5, 8], the dp matrix is updated like this

1
2
3
4
5
6
0    0    0    0    0    0
0 3 0 0 0 0
0 0 15 0 0 0
0 0 0 40 0 0
0 0 0 0 40 0
0 0 0 0 0 0

then

1
2
3
4
5
6
0    0    0    0    0    0
0 3 30 0 0 0
0 0 15 135 0 0
0 0 0 40 48 0
0 0 0 0 40 0
0 0 0 0 0 0

at last

1
2
3
4
5
6
0    0    0    0    0    0
0 3 30 159 167 0
0 0 15 135 159 0
0 0 0 40 48 0
0 0 0 0 40 0
0 0 0 0 0 0

the code is like most others.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
nums.insert(nums.begin(), 1);
nums.push_back(1);
vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));
for (int len = 1; len <= n; ++len)
for (int left = 1; left <= n - len + 1; ++left) {
int right = left + len - 1;
for (int k = left; k <= right; ++k)
dp[left][right] = max(dp[left][right], nums[left-1]*nums[k]*nums[right+1] + dp[left][k-1] + dp[k+1][right]);
}
return dp[1][n];
}
};

https://discuss.leetcode.com/topic/30746/share-some-analysis-and-explanations

Share some analysis and explanations

Be Naive First

When I first get this problem, it is far from dynamic programming to me. I started with the most naive idea the backtracking.

We have n balloons to burst, which mean we have n steps in the game. In the i th step we have n-i balloons to burst, i = 0~ n-1. Therefore we are looking at an algorithm of O(n!). Well, it is slow, probably works for n < 12 only.

Of course this is not the point to implement it. We need to identify the redundant works we did in it and try to optimize.

Well, we can find that for any balloons left the maxCoins does not depends on the balloons already bursted. This indicate that we can use memorization (top down) or dynamic programming (bottom up) for all the cases from small numbers of balloon until n balloons. How many cases are there? For k balloons there are C(n, k) cases and for each case it need to scan the k balloons to compare. The sum is quite big still. It is better than O(n!) but worse than O(2^n).

Better idea

We then think can we apply the divide and conquer technique? After all there seems to be many self similar sub problems from the previous analysis.

Well, the nature way to divide the problem is burst one balloon and separate the balloons into 2 sub sections one on the left and one one the right. However, in this problem the left and right become adjacent and have effects on the maxCoins in the future.

Then another interesting idea come up. Which is quite often seen in dp problem analysis. That is reverse thinking. Like I said the coins you get for a balloon does not depend on the balloons already burst. Therefore
instead of divide the problem by the first balloon to burst, we divide the problem by the last balloon to burst.

Why is that? Because only the first and last balloons we are sure of their adjacent balloons before hand!

For the first we have nums[i-1]nums[i]nums[i+1] for the last we have nums[-1]nums[i]nums[n].

OK. Think about n balloons if i is the last one to burst, what now?

We can see that the balloons is again separated into 2 sections. But this time since the balloon i is the last balloon of all to burst, the left and right section now has well defined boundary and do not affect each other! Therefore we can do either recursive method with memoization or dp.

Final

Here comes the final solutions. Note that we put 2 balloons with 1 as boundaries and also burst all the zero balloons in the first round since they won’t give any coins.
The algorithm runs in O(n^3) which can be easily seen from the 3 loops in dp solution.

Java D&C with Memoization

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

Java DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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[][] dp = new int[n][n];
for (int k = 2; k < n; ++k)
for (int left = 0; left < n - k; ++left) {
int right = left + k;
for (int i = left + 1; i < right; ++i)
dp[left][right] = Math.max(dp[left][right],
nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);
}

return dp[0][n - 1];
}
// 17 ms

C++ DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maxCoinsDP(vector<int> &iNums) {
int nums[iNums.size() + 2];
int n = 1;
for (int x : iNums) if (x > 0) nums[n++] = x;
nums[0] = nums[n++] = 1;


int dp[n][n] = {};
for (int k = 2; k < n; ++k) {
for (int left = 0; left < n - k; ++left)
int right = left + k;
for (int i = left + 1; i < right; ++i)
dp[left][right] = max(dp[left][right],
nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);
}

return dp[0][n - 1];
}
// 16 ms

Python DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maxCoins(self, iNums):
nums = [1] + [i for i in iNums if i > 0] + [1]
n = len(nums)
dp = [[0]*n for _ in xrange(n)]

for k in xrange(2, n):
for left in xrange(0, n - k):
right = left + k
for i in xrange(left + 1,right):
dp[left][right] = max(dp[left][right],
nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right])
return dp[0][n - 1]

# 528ms

https://discuss.leetcode.com/topic/30738/c-dynamic-programming-o-n-3-32-ms-with-comments

C++ dynamic programming, O(N^3), 32 ms, with comments

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int maxCoins(vector<int>& nums) {
int N = nums.size();
nums.insert(nums.begin(), 1);
nums.insert(nums.end(), 1);

// rangeValues[i][j] is the maximum # of coins that can be obtained
// by popping balloons only in the range [i,j]
vector<vector<int>> rangeValues(nums.size(), vector<int>(nums.size(), 0));

// build up from shorter ranges to longer ranges
for (int len = 1; len <= N; ++len) {
for (int start = 1; start <= N - len + 1; ++start) {
int end = start + len - 1;
// calculate the max # of coins that can be obtained by
// popping balloons only in the range [start,end].
// consider all possible choices of final balloon to pop
int bestCoins = 0;
for (int final = start; final <= end; ++final) {
int coins = rangeValues[start][final-1] + rangeValues[final+1][end]; // coins from popping subranges
coins += nums[start-1] * nums[final] * nums[end+1]; // coins from final pop
if (coins > bestCoins) bestCoins = coins;
}
rangeValues[start][end] = bestCoins;
}
}
return rangeValues[1][N];
}


https://discuss.leetcode.com/topic/30934/my-c-code-dp-o-n-3-20ms

My C++ code (DP, O(N^3)) 20ms

The algorithm is well explained in 1 and I pretty much followed the same line.

  1. First version I got is recursion +backtracing (TLE)
  2. Second version I got is DP:

instead of bursting ballons one by one, we do it in a reverse order, “de-burst” ballons one by one. In that order, the left and right neighbor of the “de-burst” ballon is known. However, the complexity is still high (~ order of C(n,n/2))

The real challenge is the outer boundaries (i.e. left, right neighbors vary with the burst order). The algorithm in 1 elegantly fixed that problem: fix left/right neighbors and doing DP from length=3 to nSize;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int maxCoins(vector<int>& nums) {
int nSize = nums.size()+2, left, right, len, mid, temp, dpMax[nSize][nSize] ={};
nums.insert(nums.begin(),1); // two dummy "1" added to simplify DP
nums.push_back(1);

for(len=3; len<=nSize; ++len) // lenght including left and right boudaries,
for(left=0; left<=nSize-len; ++left) //left boudary/neighbor
for(right = left+len-1, mid=left+1, temp = nums[left]*nums[right]; mid<right;++mid) //right boundary, mid is the last one to burst in the range (left, right)
dpMax[left][right] = max(dpMax[left][right], dpMax[left][mid] + dpMax[mid][right] + nums[mid]*temp);

nums.erase(nums.begin()); // recover nums
nums.pop_back();
return dpMax[0][nSize-1];
}
};

https://discuss.leetcode.com/topic/31178/python-dp-n-3-solutions

Python DP N^3 Solutions

Analysis:
We need to find a way to divide the problems. If we start from the first balloon, we can’t determine the left/right for the number in each sub-problem, If we start from the last balloon, we can.
We can see the transformation equation is very similar to the one for matrix multiplication.

dp[i][j] = max(dp[i][j], nums[i] nums[k] nums[j] + dp[i][k] + dp[k][j]) # i < k < j
This is a typical interval DP problem. Because the order of the number extracted matters, we need to do a O(n^3) DP. If we only need to expand the interval to the left or right, we only need to do a O(n^2) DP.

Top-down:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums = [1] + nums + [1]
n = len(nums)
dp = [[0] * n for _ in xrange(n)]

def calculate(i, j):
if dp[i][j] or j == i + 1: # in memory or gap < 2
return dp[i][j]
coins = 0
for k in xrange(i+1, j): # find the last balloon
coins = max(coins, nums[i] * nums[k] * nums[j] + calculate(i, k) + calculate(k, j))
dp[i][j] = coins
return coins

return calculate(0, n-1)

Bottom-up:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums = [1] + nums + [1] # build the complete array
n = len(nums)
dp = [[0] * n for _ in xrange(n)]

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

java

https://discuss.leetcode.com/topic/30746/share-some-analysis-and-explanations

Be Naive First

When I first get this problem, it is far from dynamic programming to me. I started with the most naive idea the backtracking.

We have n balloons to burst, which mean we have n steps in the game. In the i th step we have n-i balloons to burst, i = 0~ n-1. Therefore we are looking at an algorithm of O(n!). Well, it is slow, probably works for n < 12 only.

Of course this is not the point to implement it. We need to identify the redundant works we did in it and try to optimize.

Well, we can find that for any balloons left the maxCoins does not depends on the balloons already bursted. This indicate that we can use memorization (top down) or dynamic programming (bottom up) for all the cases from small numbers of balloon until n balloons. How many cases are there? For k balloons there are C(n, k) cases and for each case it need to scan the k balloons to compare. The sum is quite big still. It is better than O(n!) but worse than O(2^n).

Better idea

We then think can we apply the divide and conquer technique? After all there seems to be many self similar sub problems from the previous analysis.

Well, the nature way to divide the problem is burst one balloon and separate the balloons into 2 sub sections one on the left and one one the right. However, in this problem the left and right become adjacent and have effects on the maxCoins in the future.

Then another interesting idea come up. Which is quite often seen in dp problem analysis. That is reverse thinking. Like I said the coins you get for a balloon does not depend on the balloons already burst. Therefore
instead of divide the problem by the first balloon to burst, we divide the problem by the last balloon to burst.

Why is that? Because only the first and last balloons we are sure of their adjacent balloons before hand!

For the first we have nums[i-1]*nums[i]* nums[i+1] for the last we have nums[-1]*nums[i]*nums[n] .

OK. Think about n balloons if i is the last one to burst, what now?

We can see that the balloons is again separated into 2 sections. But this time since the balloon i is the last balloon of all to burst, the left and right section now has well defined boundary and do not affect each other! Therefore we can do either recursive method with memoization or dp.

Final

Here comes the final solutions. Note that we put 2 balloons with 1 as boundaries and also burst all the zero balloons in the first round since they won’t give any coins.

The algorithm runs in O ( n\^3 ) which can be easily seen from the 3 loops in dp solution.

Java D&C with Memoization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
public int maxCoins(int[] nums) {
if(nums.length == 0) return 0;
int n = 1;
int[] numss = new int[nums.length+2];
for(int i:nums) numss[n++] = i;
numss[0] = numss[n++] = 1;

int[][] dp = new int[n][n];
return dfs(numss, dp, 0, n-1);
}

private int dfs(int[] numss, int[][] dp, int left, int right){
if(left+1==right) return 0;
if(dp[left][right]>0) return dp[left][right];
int ans = 0;
for(int i=left+1; i<right; i++){
ans = Math.max(ans, numss[left]*numss[i]*numss[right]+dfs(numss, dp, left, i) + dfs(numss, dp, i, right));
}
dp[left][right] = ans;
return ans;
}
}

Java DP

19ms, September 9, 2016
https://discuss.leetcode.com/topic/30746/share-some-analysis-and-explanations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
public int maxCoins(int[] nums) {
int[] numbers = new int [nums.length + 2];
int n = 1;
for(int x:nums) if(x>0) numbers[n++] = x;
numbers[0] = numbers[n++] = 1;

int[][] dp = new int[n][n];
for(int k=2; k<n; ++k){
for(int left = 0; left<n-k; ++left){
int right = left+k;
for(int i = left+1; i<right; ++i){
dp[left][right] = Math.max(dp[left][right],
numbers[left]*numbers[i]*numbers[right] + dp[left][i] + dp[i][right]);
}
}
}

return dp[0][n-1];
}
}

cpp

19ms, September 9, 2016
https://discuss.leetcode.com/topic/30746/share-some-analysis-and-explanations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int maxCoins(vector<int>& nums) {
int numbers[nums.size() + 2];
int n = 1;
for(int x:nums) if(x >0) numbers[n++] = x;
numbers[0] = numbers[n++] = 1;

int dp[n][n] = {};
for(int k = 2; k<n; ++k){
for(int left = 0; left<n-k;++left){
int right = left + k;
for(int i = left+1; i<right; ++i){
dp[left][right] = max(dp[left][right],
numbers[left]*numbers[i]*numbers[right] + dp[left][i] + dp[i][right]);
}
}
}

return dp[0][n-1];
}
};

python

416ms, September 9, 2016
https://discuss.leetcode.com/topic/31178/python-dp-n-3-solutions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums = [1] + nums + [1]
n = len(nums)
dp = [[0] *n for _ in xrange(n)]

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

972ms, September 9, 2016
https://discuss.leetcode.com/topic/31178/python-dp-n-3-solutions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums = [1] + nums + [1]
n = len(nums)
dp = [[0]*n for _ in xrange(n)]

def calculate(i, j):
if dp[i][j] or j == i+1:
return dp[i][j]
coins = 0
for k in xrange(i+1, j):
coins = max(coins, nums[i] * nums[k] * nums[j] + calculate(i, k) + calculate(k, j))
dp[i][j] = coins
return coins

return calculate(0, n-1)
谢谢你,可爱的朋友。