Problem:
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 rightthen becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.
Note:
(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 167
|
1 2 |
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 |
Idea
DP
Solution1:
C++ / Recursion with memoization
|
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 |
// Author: Huahua // Runtime: 16 ms class Solution { public: int maxCoins(vector<int>& nums) { int n = nums.size(); nums.insert(nums.begin(), 1); nums.push_back(1); // c[i][j] = maxCoins(nums[i:j+1]) c_ = vector<vector<int>>(n+2, vector<int>(n+2, 0)); return maxCoins(nums, 1, n); } private: int maxCoins(const vector<int>& nums, const int i, const int j) { if(i>j) return 0; if(c_[i][j]>0) return c_[i][j]; if(i==j) return nums[i-1]*nums[i]*nums[i+1]; int ans=0; for(int k=i;k<=j;++k) ans=max(ans, maxCoins(nums,i,k-1) + nums[i-1]*nums[k]*nums[j+1] + maxCoins(nums, k+1, j)); c_[i][j] = ans; return c_[i][j]; } vector<vector<int>> c_; }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua class Solution { private int[][] memo; private int[] vals; public int maxCoins(int[] nums) { final int n = nums.length; vals = new int[n + 2]; for (int i = 0; i < n; ++i) vals[i + 1] = nums[i]; vals[0] = vals[n + 1] = 1; memo = new int[n + 2][n + 2]; return maxCoins(1, n); } private int maxCoins(int i, int j) { if (i > j) return 0; if (i == j) return vals[i - 1] * vals[i] * vals[i + 1]; if (memo[i][j] > 0) return memo[i][j]; int ans = 0; for (int k = i; k <= j; ++k) ans = Math.max(ans, maxCoins(i, k - 1) + vals[i - 1] * vals[k] * vals[j + 1] + maxCoins(k + 1, j)); memo[i][j] = ans; return memo[i][j]; } } |
Solution2:
C++ / DP
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // Runtime: 9 ms class Solution { public: int maxCoins(vector<int>& nums) { int n = nums.size(); nums.insert(nums.begin(), 1); nums.push_back(1); // c[i][j] = maxCoins(nums[i:j+1]) vector<vector<int>> c(n+2, vector<int>(n+2, 0)); for(int l=1;l<=n;++l) for(int i=1;i<=n-l+1;++i) { int j=i+l-1; for(int k=i;k<=j;++k) { c[i][j] = max(c[i][j], c[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + c[k+1][j]); } } return c[1][n]; } }; |
Java / DP
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public int maxCoins(int[] nums) { final int n = nums.length; int[] vals = new int[n + 2]; for (int i = 0; i < n; ++i) vals[i + 1] = nums[i]; vals[0] = vals[n + 1] = 1; int[][] dp = new int[n + 2][n + 2]; for (int l = 1; l <= n; ++l) for (int i = 1; i + l <= n + 1; ++i) { int j = i + l - 1; int best = 0; for (int k = i; k <= j; ++k) best = Math.max(best, dp[i][k - 1] + vals[i - 1] * vals[k] * vals[j + 1] + dp[k + 1][j]); dp[i][j] = best; } return dp[1][n]; } } |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment