312. Burst Balloons (Hard)
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:
- 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
Solutions
public class Solution {
// This problem is complicated, but it is a typical dynamic problem and worth trying.
public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
// max coins we can get when burst balloons in window x, y, or nums[x:y], where y is inclusive.
int[][] dp = new int[len][len];
// ws means window side
for (int ws = 1; ws <= len; ws++) {
// work out the max coins for given window size
for (int start = 0; start <= len - ws; start++) {
// ending index of search window
int end = start + ws - 1;
// At this point, we have dp for windows of which sizes are from 1 to ws - 1
for (int i = start; i <= end; i++) {
// Suppose only i left, others in the window all burst. We need to plus the max
// coins of both sides when they burst.
// 1. max coins when burst all balloons in range [start, i-1];
// 2. max coins when burst all balloons in range [i + 1, end];
int coins = nums[i] * getValue(nums, start - 1) * getValue(nums, end + 1);
if (ws != 1) {
// i is the first one, we can only add right side
if (i == start) {
coins += dp[i + 1][end];
}
// i is the last one, we can only add left side
else if (i == end) {
coins += dp[start][i - 1];
}
// i is the middle, we can add both sides
else if (ws >= 3) {
coins += dp[start][i - 1] + dp[i + 1][end];
}
}
// Update the max coins if current schema is superior than previous.
dp[start][end] = Math.max(dp[start][end], coins);
}
}
}
return dp[0][nums.length - 1];
}
private int getValue(int[] nums, int i) {
// Deal with num[-1] and num[num.length]
if (i < 0 || i >= nums.length) {
return 1;
}
return nums[i];
}
}
Incorrect Solutions
class Solution {
// Time exceeds the limit.
// serves as cache to keep the best scores of computed nums
Map<String, Integer> scoreMap = new HashMap<>();
public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
List<Integer> numList = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
numList.add(nums[i]);
}
return recurse(numList, numList.size());
}
private int recurse(List<Integer> nums, int len) {
if (nums == null || len == 0) {
return 0;
}
if (len == 1) {
return 1 * nums.get(0) * 1;
}
// if nums already processed, return previous computed score
if (scoreMap.containsKey(nums.toString())) {
return scoreMap.get(nums.toString());
}
// keep the score of the best scheme
int max = 0;
for (int i = 0; i < len; i++) {
// calculate if scores after burst balloon i
int score = 0;
if (i == 0) {
score = 1 * nums.get(0) * nums.get(1);
} else if (i == len - 1) {
score = nums.get(len - 2) * nums.get(len - 1) * 1;
} else {
score = nums.get(i - 1) * nums.get(i) * nums.get(i + 1);
}
// save it for recover purpose
int burstOne = nums.get(i);
// shift elements after i forward by 1 step, simultaneously move element i to the end
nums.remove(i);
score += recurse(nums, len - 1);
max = Math.max(max, score);
// undo above shift process
nums.add(i, burstOne);
}
// keep score of nums to cache
scoreMap.put(nums.toString(), max);
return max;
}
}