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 = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
dp问题,开始没想出来唉,看了下别人的。就是从left和right间的间距从2开始,一直递推到相差n-1这种情况。代码如下所示:
class Solution {
public:
static bool noCoins(int a)
{
return a == ;
}
int maxCoins(vector<int>& nums) {
nums.erase(remove_if(nums.begin(), nums.end(), noCoins), nums.end());//注意这里的处理方法。先调用remove在调用erase
if(nums.size() == )
return ;
nums.resize(nums.size() + );
copy(nums.begin(), nums.end() - , nums.begin() + );
nums[] = nums[nums.size() - ] = ;
int sz = nums.size();
int dp[sz][sz] = {};
for(int interval = ; interval < sz; ++interval){//interval指的是left与right之间的间隔
for(int left = ; left < sz - interval; ++left){
int right = left + interval;
for(int j = left + ; j < right; ++j){//穷尽left-right之间的每一种可能值
dp[left][right] = max(dp[left][right], dp[left][j] + nums[left]*nums[j]*nums[right] + dp[j][right]);
} //注意这里取left以及right的原因是left到j之间的数字以及被dp[left][j]所覆盖了
}
}
return dp[][sz-];//这是最终结果了
}
};