Description
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 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
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 315 + 358 + 138 + 181 = 167
Idea
Use dynamic programming. For each interval, compute the maximum score by bursting balloons in that interval, assuming the rest of the world is not broken.
Enumerate which balloon to burst last, compute the optimal solution.
Solution
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
if (!n) return 0;
vector<vector<int> > dp(n, vector<int>(n, 0));
for (int len = 1; len <= n; ++len) {
for (int l = 0; l + len <= n; ++l) {
int r = l + len - 1;
for (int last = l; last <= r; ++last) {
int last_point = nums[last];
if (l) last_point *= nums[l - 1];
if (r < n - 1) last_point *= nums[r + 1];
int left_point = (last > l) ? dp[l][last - 1] : 0;
int right_point = (last < r) ? dp[last + 1][r] : 0;
int tot_point = last_point + left_point + right_point;
dp[l][r] = max(dp[l][r], tot_point);
}
}
}
return dp[0][n - 1];
}
};
70 / 70 test cases passed.
Runtime: 13 ms
