【LeetCode】312. Burst Balloons
2024-08-30 03:01:23
题目:
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
题解:
Solution 1 (TLE)
class Solution {
public:
void helper(vector<int> nums, int cur, int& res) {
if(nums.size() == ) {
if(cur > res) res = cur;
return;
}
for(int i=; i<nums.size()-; ++i) {
int tmp = nums[i];
cur += nums[i-]*nums[i]*nums[i+];
nums.erase(nums.begin()+i);
helper(nums, cur, res);
nums.insert(nums.begin()+i,tmp);
cur -= nums[i-]*nums[i]*nums[i+];
}
}
int maxCoins(vector<int> nums) {
nums.insert(nums.begin(),);
nums.push_back();
int res = INT_MIN;
helper(nums, , res);
return res;
}
};
Solution 2 ()
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
nums.insert(nums.begin(), );
nums.push_back();
vector<vector<int> > dp(nums.size(), vector<int>(nums.size() , ));
for (int len = ; len <= n; ++len) {
for (int left = ; left <= n - len + ; ++left) {
int right = left + len - ;
for (int k = left; k <= right; ++k) {
dp[left][right] = max(dp[left][right], nums[left - ] * nums[k] * nums[right + ] + dp[left][k - ] + dp[k + ][right]);
}
}
}
return dp[][n];
/* for (int len = 2; len <= n+1; ++len) {
for (int left = 0; left <= n - len + 1; ++left) {
int right = left + len;
for (int k = left+1; k < right; ++k) {
dp[left][right] = max(dp[left][right], nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right]);
}
}
}
return dp[0][n+1]; */
}
};
Solution 3 ()
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
nums.insert(nums.begin(), );
nums.push_back();
vector<vector<int> > dp(nums.size(), vector<int>(nums.size() , ));
return burst(nums, dp, , n);
}
int burst(vector<int> &nums, vector<vector<int> > &dp, int left, int right) {
if (left > right) return ;
if (dp[left][right] > ) return dp[left][right];
int res = ;
for (int k = left; k <= right; ++k) {
res = max(res, nums[left - ] * nums[k] * nums[right + ] + burst(nums, dp, left, k - ) + burst(nums, dp, k + , right));
}
dp[left][right] = res;
return res;
}
};
Solution 4 ()
class Solution {
public:
int maxCoins(vector<int>& nums) {
nums.insert(nums.begin(),);
nums.push_back();
const auto N=nums.size();
vector<int> m(N*N);
for(size_t l=;l<N;l++)
{
for(size_t i=;i+l<N;i++)
{
const size_t j=i+l;
int v=;
for(size_t k=i+;k<j;k++)
{
v=max(v,nums[i]*nums[k]*nums[j]+m[i*N+k]+m[k*N+j]);
}
m[i*N+j]=v;
}
}
return m[N-];
}
};
最新文章
- VMware备份研究
- LoadRunner替换字符串(可以同时替换多个)
- paip.提升效率--数据绑定到table原理和流程Angular js jquery实现
- 【BZOJ 3196】二逼平衡树 线段树套splay 模板题
- QuickStart OpenvirteX
- leetcode Database2 (四)
- [连载]JavaScript讲义(05)--- 数据处理
- Android ListView点击失效
- 预定义的类型“Microsoft.CSharp.RuntimeBinder.Binder”未定义或未导入
- ubuntu openstack spice
- 高质量c c++编程
- css清除浮动float的三种方法总结
- 如何给Ionic写一个cordova插件
- hdu_1017(水水水,坑格式)
- java项目 在 linux ubuntu 上的部署相关
- 利用开机账户登录“轻松访问”创建Windows后门
- linux-shell系列4-init
- vue深入响应式原理
- Linux命令之sed
- hdu1305Immediate Decodability(字典树)