Givennballoons, indexed from0ton-1. Each balloon is painted with a number on it represented by arraynums. You are asked to burst all the balloons. If the you burst ballooniyou will getnums[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 themaximumcoins you can collect by bursting the balloons wisely.
You may imaginenums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
这题是划分类，所以比较适合从大到小用dfs记忆化搜索。首先我们要找区间[0, n - 1](整个区间的)。进到递归函数，如果我们已经算过这个区间的话直接返回，如果没有才继续算下去。然后我们来到base case，区间长度为1，只有一个气球。这个是第一个被打爆的气球。分情况来算分，因为一开始的那个和最后那个要特别处理。然后我们得处理其他区间长度大于1的情况。基本上，我们枚举区间的断点，算算断点左边的分数，再算算断点右边的分数。然后还得算算断点处的分数。这里也得注意第一个和最后一个的特殊情况。然后把3部分的分数加起来。然后，把所有断点loop一遍，找出可以得到的最高分数。把那个分数记录到dp矩阵里。（s 到 e这段区间里能打到的最大值）
再加一个follow up，如果是个环，怎么破。这个的做法跟L593 Stone Game II一样，变成2n，就是最前面和最后面不是乘以1了，而是乘以相应的球的值
public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
if (n == 1) {
return nums[0];
}
int[][] dp = new int[n][n];
dfs(0, n - 1, dp, nums);
return dp[0][n - 1];
}
private int dfs(int s, int e, int[][] dp, int[] nums) {
// if already calculated, return directly
if (dp[s][e] > 0) {
return dp[s][e];
}
// 1st one to burst, base case
if (s == e) {
if (s == 0) {// 1st ballon
dp[s][e] = 1 * nums[s] * nums[s + 1];
} else if (s == nums.length - 1) {// last ballon
dp[s][e] = nums[s - 1] * nums[s] * 1;
} else {// baloons in the middle
dp[s][e] = nums[s - 1] * nums[s] * nums[s + 1];
}
} else { // other cases
// loop all the possible last balloon to burst position in this
// range
int max = 0;
int startLeft = (s == 0) ? 1 : nums[s - 1];// 左边气球的值
int endRight = (e == nums.length - 1) ? 1 : nums[e + 1];// 右边气球的值
for (int i = s; i <= e; i++) {
// find the max and assign to dp[s][e]
int leftPoints = (s == i) ? 0 : dfs(s, i - 1, dp, nums);//左区间得到的最大值
int rightPoints = (i == e) ? 0 : dfs(i + 1, e, dp, nums);//右区间得到的最大值
int midPoints = startLeft * nums[i] * endRight;// 打爆i气球得到的值
int cur = leftPoints + rightPoints + midPoints;// 加起来跟max比较大小
max = Math.max(max, cur);
}
dp[s][e] = max;
}
return dp[s][e];
}
补一个递推的
public class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[][] dp = new int[n + 2][n + 2];
// 做一个偏移，前面加一个1后面加一个1
nums = Arrays.copyOf(nums, nums.length + 2);
for (int i = n - 1; i >= 0; i--) {
nums[i + 1] = nums[i];
}
nums[0] = 1;
nums[n + 1] = 1;
for (int len = 1; len <= n; len++) {
for (int i = 1; i <= n && i + len -1 <= n; i++) {
int j = i + len - 1;
for (int k = i; k <= j; k++) {
dp[i][j] = Math.max(dp[i][k - 1] + dp[k + 1][j] + nums[i -1] * nums[k] * nums[j + 1], dp[i][j]);
}
}
}
return dp[1][n];
}
}