LC312. 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.
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
要求能够得到的最大的数量，看起来就很像DP的题目。可是DP的话如何从前一个状态推得后一个状态呢？很明显结束条件是只剩下最后一个气球…参考了低卡百事大神的解法，这是自己出题自己做的节奏…
Divide and conquer solution
打破每个气球得到的金币是与左右气球相关的，所以最后一个气球来将问题分开。
public class Solution {
// Divide and Conquer
public int maxCoins(int[] nums) {
// add -1 and n to num
int[] num = new int[nums.length + 2];
for(int i = 0; i < nums.length; i++) num[i+1] = nums[i];
num[0] = num[nums.length + 1] = 1;
// memo[i][j] means the coins get when brust [i, j] balloons
int[][] memo = new int[num.length+1][num.length+1];
return brust(memo, num, 0 ,num.length-1);
} // maxCoins
private int brust(int[][] memo, int[] num, int begin, int end){
if(memo[begin][end] > 0) return memo[begin][end];
int res = 0;
// we have end - begin -1 conditoins, each time end with one of num between them
for(int i = begin + 1; i < end; i++){
res = Math.max(res, num[begin]*num[i]*num[end] + brust(memo, num, begin, i) + brust(memo, num, i, end));
}
memo[begin][end] = res;
return res;
} // brust
}
O(n^3), O(n^2)
DP solution:
跟分治法的解法相似，有递推式就可以用DP来解。DP{ij}表示打破从i到j(inclusive)的气球能获得的最大金币数。
dp{i, j} = max(dp{i, j}, nums[i - 1]✖️nums[k]✖️nums[j + 1] + dp{i, k - 1} + dp{k + 1, j})
下面低卡百事的答案应该是不包括左边界的。
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];
}
复杂度应该是一样。