leetcode Burst Balloons - 细语呢喃
https://robinliu.gitbooks.io/algorithms/content/qu_jian_lei.html
https://leetcode.com/problems/burst-balloons/discuss/76232/C%2B%2B-dynamic-programming-O(N3)-32-ms-with-comments
https://discuss.leetcode.com/topic/30745/java-dp-solution-with-detailed-explanation-o-n-3
http://www.hrwhisper.me/leetcode-burst-balloons/
一开始想dp[i][j] 为第 i 天打破第j 个气球，然后枚举上一轮打破的为第k个气球 dp[i][j] =max( dp[i – 1][k] + left * nums[j] * right) （当然要记录都打了哪些O） 复杂度 O(n^3) 然而TLE (python)
http://yuancrackcode.com/2015/11/29/burst-balloons/
public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[][] dp = new int[nums.length][nums.length];
for (int len = 1; len <= nums.length; len++) {
for (int start = 0; start <= nums.length - len; start++) {
int end = start + len - 1;
for (int i = start; i <= end; i++) {
int coins = nums[i] * getValue(nums, start - 1) * getValue(nums, end + 1);
coins += i != start ? dp[start][i - 1] : 0; // If not first one, we can add subrange on its left.
coins += i != end ? dp[i + 1][end] : 0; // If not last one, we can add subrange on its right
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];
}
https://leetcode.com/discuss/89797/java-solution-with-explanations
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
(2) 0 ≤
(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
Example:
Given
[3, 1, 5, 8]
Return
167nums = [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个气球。每次你可以打破一个，打破第i个，那么你会获得nums[left] * nums[i] * nums[right]个积分。 （nums[-1] = nums[n] = 1）求你可以获得的最大积分数
https://robinliu.gitbooks.io/algorithms/content/qu_jian_lei.html
https://leetcode.com/problems/burst-balloons/discuss/76232/C%2B%2B-dynamic-programming-O(N3)-32-ms-with-comments
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];
}
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 than 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 dp problem analysis. That is reverse thinking. Like I said the coins you get for a ballon 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 havenums[-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 effect 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.
This DP solution is actually very similar to https://leetcode.com/problems/longest-palindromic-substring/. The idea is that if you want to compute answer for a given range in a bottom-up way (you don't care about this in recursive approach), you need to know its subset ranges first. Therefore you populate the matrix diagonally
This DP solution is actually very similar to https://leetcode.com/problems/longest-palindromic-substring/. The idea is that if you want to compute answer for a given range in a bottom-up way (you don't care about this in recursive approach), you need to know its subset ranges first. Therefore you populate the matrix diagonally
Java D&C with Memoization
https://leetcode.com/problems/burst-balloons/discuss/76245/Easiest-Java-Solution
https://leetcode.com/problems/burst-balloons/discuss/76245/Easiest-Java-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;
}
Java DP
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];
}
// 154 mshttps://discuss.leetcode.com/topic/30745/java-dp-solution-with-detailed-explanation-o-n-3
The basic idea is that we can find the maximal coins of a subrange by trying every possible final burst within that range. Final burst means that we should burst balloon i as the very last one and burst all the other balloons in whatever order. dp[i][j] means the maximal coins for range [i...j]. In this case, our final answer is dp[0][nums.length - 1].
When finding the maximal coins within a range [start...end], since balloon i is the last one to burst, we know that in previous steps we have already got maximal coins of range[start .. i - 1] and range[i + 1 .. start], and the last step is to burst ballon i and get the product of balloon to the left of i, balloon i, and ballon to the right of i. In this case, balloon to the left/right of i is balloon start - 1 and balloon end + 1. Why? Why not choosing other balloon in range [0...start - 1] and [end + 1...length] because the maximal coins may need other balloon as final burst?
In my opinion, it's because this subrange will only be used by a larger range when it's trying for every possible final burst. It will be like [larger start.....start - 1, [start .. end] end + 1/ larger end], when final burst is at index start - 1, the result of this sub range will be used, and at this moment, start - 1 will be there because it's the final burst and end + 1 will also be there because is out of range. Then we can guarantee start - 1 and end + 1 will be there as adjacent balloons of balloon i for coins. That's the answer for the question in previous paragraph.
public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[][] dp = new int[nums.length][nums.length];
for (int len = 1; len <= nums.length; len++) {
for (int start = 0; start <= nums.length - len; start++) {
int end = start + len - 1;
for (int i = start; i <= end; i++) {
int coins = nums[i] * getValue(nums, start - 1) * getValue(nums, end + 1);
coins += i != start ? dp[start][i - 1] : 0; // If not first one, we can add subrange on its left.
coins += i != end ? dp[i + 1][end] : 0; // If not last one, we can add subrange on its right
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];
}
看了discuss是dp[i][j]为打破的气球为i~j之间。
我们可以想象：最后的剩下一个气球为i的时候，可以获得的分数为：nums[-1]*nums[i]*nums[n].
那么介于i,j之间的x，有： dp[i][j] = max(dp[i][j], dp[i][x – 1] + nums[i – 1] * nums[x] * nums[j + 1] + dp[x + 1][j]);
public int maxCoins(int[] iNums) {
int n = iNums.length;
int[] nums = new int[n + 2];
for (int i = 0; i < n; i++) nums[i + 1] = iNums[i];
nums[0] = nums[n + 1] = 1;
int[][] dp = new int[n + 2][n + 2];
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n - k + 1; i++) {
int j = i + k - 1;
for (int x = i; x <= j; x++) {
dp[i][j] = Math.max(dp[i][j], dp[i][x - 1] + nums[i - 1] * nums[x] * nums[j + 1] + dp[x + 1][j]);
}
}
}
return dp[1][n];
}
http://www.cnblogs.com/grandyang/p/5006441.html
像这种求极值问题，我们一般都要考虑用动态规划Dynamic Programming来做，我们维护一个二维动态数组dp，其中dp[i][j]表示打爆区间[i,j]中的所有气球能得到的最多金币。题目中说明了边界情况，当气球周围没有气球的时候，旁边的数字按1算，这样我们可以在原数组两边各填充一个1，这样方便于计算。这道题的最难点就是找递归式，如下所示：
dp[i][j] = max(dp[i][j], nums[i - 1]*nums[k]*nums[j + 1] + dp[i][k - 1] + dp[k + 1][j]) ( i ≤ k ≤ j )
有了递推式，我们可以写代码，我们其实只是更新了dp数组的右上三角区域，我们最终要返回的值存在dp[1][n]中，其中n是两端添加1之前数组nums的个数。
这道题提出了一种打气球的游戏，每个气球都对应着一个数字，我们每次打爆一个气球，得到的金币数是被打爆的气球的数字和其两边的气球上的数字相乘，如果旁边没有气球了，则按1算，以此类推，求能得到的最多金币数。参见题目中给的例子，题意并不难理解。那么大家拿到题后，总是会习惯的先去想一下暴力破解法吧，这道题的暴力搜索将相当的复杂，因为每打爆一个气球，断开的地方又重新挨上，所有剩下的气球又要重新遍历，这使得分治法不能work，整个的时间复杂度会相当的高，不要指望可以通过OJ。而对于像这种求极值问题，我们一般都要考虑用动态规划Dynamic Programming来做，我们维护一个二维动态数组dp，其中dp[i][j]表示打爆区间[i,j]中的所有气球能得到的最多金币。题目中说明了边界情况，当气球周围没有气球的时候，旁边的数字按1算，这样我们可以在原数组两边各填充一个1，方便于计算。这道题的最难点就是找状态转移方程，还是从定义式来看，假如区间只有一个数，比如dp[i][i]，那么计算起来就很简单，直接乘以周围两个数字即可更新。如果区间里有两个数字，那么就要算两次了，先打破第一个再打破了第二个，或者先打破第二个再打破第一个，比较两种情况，其中较大值就是该区间的dp值。假如区间有三个数呢，比如dp[1][3]，怎么更新呢？如果先打破第一个，剩下两个怎么办呢，难道还要分别再遍历算一下吗？这样跟暴力搜索的方法有啥区别呢，还要dp数组有啥意思。所谓的状态转移，就是假设已知了其他状态，来推导现在的状态，现在是想知道dp[1][3]的值，那么如果我们先打破了气球1，剩下了气球2和3，若我们之前已经计算了dp[2][3]的话，就可以使用其来更新dp[1][3]了，就是打破气球1的得分加上dp[2][3]。那假如我们先打破气球2呢，只要我们之前计算了dp[1][1]和dp[3][3]，那么三者加起来就可以更新dp[1][3]。同理，先打破气球3，就用其得分加上dp[1][2]来更新dp[1][3]。说到这里，是不是感觉豁然开朗了 ^.^
那么对于有很多数的区间 [i, j]，我们如何来更新呢？现在是想知道dp[i][j]的值，这个区间可能比较大，但是如果我们知道了所有的小区间的dp值，然后聚沙成塔，逐步的就能推出大区间的dp值了。还是要遍历这个区间内的每个气球，就用k来遍历吧，k在区间 [i, j] 中，假如第k个气球先被打爆，然后此时区间 [i, j] 被分成了两部分，[i, k-1] 和 [k+1, j]，只要我们之前更新过了这两个子区间的dp值，可以直接用 dp[i][k-1] 和 dp[k+1][j]，那么先被打爆的第k个气球的得分该怎么算呢，你可能会下意识的说，就乘以周围两个气球被 nums[k-1] * nums[k] * nums[k+1]，但其实这样是错误的，为啥呢？dp[i][k-1]的意义是什么呢，是打爆区间 [i, k-1] 内所有的气球后的最大得分，此时第k-1个气球已经不能用了，同理，第k+1个气球也不能用了，求相当于区间 [i, j] 中除了第k个气球，其他的已经爆了，那么周围的气球只能是第i-1个，和第j+1个了，所以得分应为 nums[i-1] * nums[k] * nums[j+1]，分析到这里，我们的状态转移方程应该已经跃然纸上了吧，如下所示：
dp[i][j] = max(dp[i][j], nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j]) ( i ≤ k ≤ j )
有了状态转移方程了，我们可以写代码，下面就遇到本题的第二大难点了，区间的遍历顺序。一般来说，我们遍历所有子区间的顺序都是i从0到n，然后j从i到n，然后得到的 [i, j] 就是子区间。但是这道题用这种遍历顺序就不对，在前面的分析中已经说了，我们需要先更新完所有的小区间，然后才能去更新大区间，而用这种一般的遍历子区间的顺序，会在更新完所有小区间之前就更新了大区间，从而不一定能算出正确的dp值，比如拿题目中的那个例子 [3, 1, 5, 8] 来说，一般的遍历顺序是：
[3] -> [3, 1] -> [3, 1, 5] -> [3, 1, 5, 8] -> [1] -> [1, 5] -> [1, 5, 8] -> [5] -> [5, 8] -> [8]
显然不是我们需要的遍历顺序，正确的顺序应该是先遍历完所有长度为1的区间，再是长度为2的区间，再依次累加长度，直到最后才遍历整个区间：
[3] -> [1] -> [5] -> [8] -> [3, 1] -> [1, 5] -> [5, 8] -> [3, 1, 5] -> [1, 5, 8] -> [3, 1, 5, 8]
我们其实只是更新了dp数组的右上三角区域，我们最终要返回的值存在dp[1][n]中，其中n是两端添加1之前数组nums的个数
对于题目中的例子
[3, 1, 5, 8]，得到的dp数组如下：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
- public int maxCoins(int[] nums) {
- if (nums == null || nums.length == 0) return 0;
- int[] ballons = new int[nums.length + 2];
- int len = 1;
- for (int num : nums) {
- if (num > 0) {
- ballons[len++] = num;
- }
- }
- ballons[0] = ballons[len++] = 1;
- int[][] coins = new int[len][len];//len此时是原长度+2
- for (int k = 2; k < len; k++) {
- for (int left = 0; left + k < len; left ++) {//left一直起始于0
- int right = left + k;
- for (int i = left + 1; i < right; i ++) {//i必须大于0，因为ballons[0]是人为加进去的1
- coins[left][right] = Math.max(coins[left][right], ballons[left] * ballons[i] * ballons[right] + coins[left][i] + coins[i][right]);
- }
- }
- }
- return coins[0][len-1];
- }
public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[][] dp = new int[nums.length][nums.length];
for (int len = 1; len <= nums.length; len++) {
for (int start = 0; start <= nums.length - len; start++) {
int end = start + len - 1;
for (int i = start; i <= end; i++) {
int coins = nums[i] * getValue(nums, start - 1) * getValue(nums, end + 1);
coins += i != start ? dp[start][i - 1] : 0; // If not first one, we can add subrange on its left.
coins += i != end ? dp[i + 1][end] : 0; // If not last one, we can add subrange on its right
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];
}
https://leetcode.com/discuss/89797/java-solution-with-explanations
dp[i][j]表示区间[i...j]中能得到的最大值，那么这个最大值怎么得到呢， 那就轮询一遍这个区间。假设k是该区间中最后一个打破的气球，能获得的最大值，轮询k从i到j，然后取最大值.