312. Burst Balloons
Hard
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
=============
Eg.nums = 3 1 5 8
0 1 2 3 4 5
after extended nums = 1 3 1 5 8 1
bottom up
0 1 2 3 4 5
1 3 1 5 8 1
step 1: burst balloon 2 => 3*1*5 = 15 => dp[2][2] = dp[2][1]+dp[3][2]+15 = 15
0 1
1 3
step 2: burst balloon 3 => 3*5*8 = 120 => dp[2][3] = dp[2][2]+dp[4][3]+120 = 135
0 1
1 3
step 1: burst balloon 1 => 1*3*8= 24 => dp[1][3] = dp[1][0]+dp[2][3]+24 = 159
0
1
step 1: burst balloon 4 => 1*8*1 = 8 => dp[1][4] = dp[1][3]+dp[5][4]+8 = 167
Ref
[1] https://leetcode.com/problems/burst-balloons/
[2] https://leetcode.com/discuss/72186/c-dynamic-programming-o-n-3-32-ms-with-comments
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | //C++: TLE class Solution { public: int maxCoins(vector<int>& nums) { int n = nums.size(); if(n==0) return 0; int ret = 0; for(int i=0; i<n; ++i){ int tmp = (i==0?1:nums[i-1])*nums[i]*(i==n-1?1:nums[i+1]); vector<int> nums1 = nums; nums1.erase(nums1.begin()+i); tmp += maxCoins(nums1); ret = max(ret, tmp); } return ret; } }; class Solution { public: int maxCoins(vector<int>& nums) { int n = nums.size(); nums.insert(nums.begin(), 1); nums.insert(nums.end(), 1); //can be further optimized by removing all zeros //dp[s][e] is max coins by bursting all balloons from s to e vector<vector<int>> dp(n+2, vector<int>(n+2, 0)); for(int s = n; s>0; --s){ for(int e = s; e<=n; ++e){ int bestCoins = 0; for(int i = s; i<=e; ++i){ //coins is the max coins when balloon i is the last balloon int coins = dp[s][i-1] + dp[i+1][e] + nums[s-1]*nums[i]*nums[e+1]; bestCoins = max(bestCoins, coins); } dp[s][e] = bestCoins; } } return dp[1][n]; } }; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class Solution { public int maxCoins(int[] nums) { int n = nums.length; int[] numsExt = new int[n+2]; Arrays.fill(numsExt, 1); for(int i=1; i<=n; ++i) numsExt[i] = nums[i-1]; int[][] dp = new int[n+2][n+2]; for(int s=n; s>0; --s){ for(int e = s; e<=n; ++e){ int bestCoins = 0; for(int i=s; i<=e; ++i){ int coins = dp[s][i-1] + dp[i+1][e] + numsExt[s-1]*numsExt[i]*numsExt[e+1]; bestCoins = Math.max(bestCoins, coins); } dp[s][e] = bestCoins; } } return dp[1][n]; } } |
No comments:
Post a Comment