Comment on page
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:
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
A very nice analysis on LeetCode talking about several approaches from brute-force to divide and conquer as well as dynamic programming:
一、利用分治法Divide and Conquer结合记忆化memoization
二、或者利用区间型动态规划Dynamic Programming
subproblems are overlapped, so we can use divide and conquer + cache
Balloons0, 1, ..., n - 1
What is the max value if we burst all of them[0, n - 1]
? Let's first consider bursting[start, end]
(includingstart
andend
boundaries) Imagine indexi
as the last one in the interval to be bursted[start, ... i - 1, (i), i + 1 ... end]
Before the end, we already bursted[start, i - 1]
and[i + 1, end]
Before the end, boundariesstart - 1
,i
,end + 1
are always there This helps us calculate coins without worrying about details inside[start, i - 1]
and[i + 1, end]
So the range can be divided intostart - 1
,maxCoin(start, i - 1)
,i
,maxCoins(i + 1, end)
,end + 1
基本思想就是在区间
[start, end]
中循环i
,i
作为该区间内最后被爆的气球,这样区间被分成了左右两个区间,再依次递归地寻找 [start, i - 1]
和 [i + 1, end]
的区间。这样就变成了子问题,而子问题区间上是可能有重叠的,因此可以用memoization来优化递归。这题的难点在于,如何在动态变化的数组中,正确定义并计算subproblem.
因为数组一直在变化,如何计算每次打爆获得的coin呢?
是否可以将子问题定义为寻找(left, right)区间内能得到最多的coin数目?
难想到的是从最后被打爆的气球入手,这种情况下,区间的左右两个两个元素就是确定的,而改变(循环
i
)区间内最后被打爆的气球则会得到不同的结果,从而找到最大State:
dp[i][j]
表示 i 到 j 区间中,打爆所有气球的最大coin数目
Function:
- 对于所有k属于
{i,j}
, 表示第k号气球最后打爆。k
is the last balloon to burst.midValue = arr[i- 1] * arr[k] * arr[j + 1];
dp[i][j] = max(dp[i][k-1] + d[k+1][j] + midvalue)
Initialize:
- for each
i
dp[i][i] = 0
Answer:
dp[0][n-1]
Divide & Conquer + Recursive + Memoization - Easy to Understand Solution (16 ms, faster than 14.04%)
start
, end
boundary included (boundaries will be burst)[start, ... i - 1, (i), i + 1 ... end]
class Solution {
public int maxCoins(int[] nums) {
int[][] dp = new int[nums.length][nums.length];
return maxCoinsHelper(nums, 0, nums.length - 1, dp);
}
public int maxCoinsHelper(int[] nums, int start, int end, int[][] dp) {
if (start > end) return 0;
if (dp[start][end] != 0) return dp[start][end];
int max = 0;
for (int i = start; i <= end; i++) {
int val = maxCoinsHelper(nums, start, i - 1, dp) +
maxCoinsHelper(nums, i + 1, end, dp) +
getVal(nums, start - 1) * getVal(nums, i) * getVal(nums, end + 1);
max = Math.max(max, val);
}
dp[start][end] = max;
return max;
}
private int getVal(int[] nums, int i) {
if (i == -1 || i == nums.length) {
return 1;
}
return nums[i];
}
}
*(Favorite) - Same idea as above (Divide & Conquer with Memoization) but faster performance (6ms 87.86%)
Building a new array first for faster access, compared to above
getVal()
functionpublic class Solution {
public int maxCoins(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int n = nums.length;
int[] arr = new int[n + 2];
arr[0] = 1;
arr[n + 1] = 1;
for(int i = 0; i < n; i++){
arr[i + 1] = nums[i];
}
int[][] dp = new int[n + 2][n + 2];
return memoizedSearch(1, n, arr, dp);
}
private int memoizedSearch(int start, int end, int[] arr, int[][] dp){
if(dp[start][end] != 0) return dp[start][end];
int max = 0;
for(int i = start; i <= end; i++){
int cur = arr[start - 1] * arr[i] * arr[end + 1];
int left = memoizedSearch(start, i - 1, arr, dp);
int right = memoizedSearch(i + 1, end, arr, dp);
max = Math.max(max, cur + left + right);
}
dp[start][end] = max;
return max;
}
}
Other answers for reference
*Divide and Conquer, Memoization, Recursive - (Runtime: 5 ms, faster than 99.18%)
(not including boundaries in the recursion - boundary balloons not bursted)
class Solution {
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;
}
}
Dynamic Programming - 6 ms , faster than 88.28%
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];
}
Last modified 3yr ago