312. 戳气球 Hard

2024-06-09 23:20
文章标签 hard 气球 312

本文主要是介绍312. 戳气球 Hard,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

有 n 个气球,编号为0 到 n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界,那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

示例 1:

输入:nums = [3,1,5,8]
输出: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

示例 2:

输入:nums = [1,5]
输出:10

提示:

 ·n == nums.length

 ·1 <= n <= 300

 ·0 <= nums[i] <= 100

题目大意:在戳破一个气球可获得该气球与周围气球乘积数的情况下计算最多可获得的乘积数。

分析:

(1)在戳破一个气球后会造成不相邻的气球变得相邻,较难处理,因此考虑反向操作。将题目过程改为从两个数字为1的气球中不断插入气球,每次插入可获得插入球与相邻球的乘积数,计算最多可获得的乘积数;

(2)通过(1)中方法将问题转换为插入气球的问题,由于是从两个数字为1的气球开始插入,因此在nums数组的首尾插入数字1,再设dp[l][r]为在区间(l,r)中的气球全部插满最多可获得的硬币数。若区间(l,r)中第一个气球插入的位置为mid(l<mid<r),则dp[l][r]=dp[l][mid]+dp[mid][r]+nums[l]*nums[mid]*nums[r]。由此计算方式可得状态转移方程:

class Solution {
public:int maxCoins(vector<int>& nums) {nums.insert(nums.begin(),1);nums.emplace_back(1);int N=nums.size();vector<vector<int>> dp(N,vector<int>(N,0));for(int len=2,l,r,mid;len<N;++len){for(l=0,r=l+len;r<N;++l,++r){for(mid=l+1;mid<r;++mid){dp[l][r]=max(dp[l][r],dp[l][mid]+dp[mid][r]+nums[l]*nums[mid]*nums[r]);}}}return dp[0][N-1];}
};

这篇关于312. 戳气球 Hard的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1046585

相关文章

HDU 1097 A hard puzzle(规律)

题目: http://acm.hdu.edu.cn/showproblem.php?pid=1097 题意: 求a的b次方的最后一位。 题解: 直接从例子入手, 第一组数据 7 66,结果如下(只要最后一位所以模10) 7 9 3 1 7 9··· 循环节为4,即结果在4个数值内循环出现。 第二组数据 6 800,结果如下 6 6 6 6··· 循环节为1 ···

P problem、NP problem、NP-complete problem、NP-hard problem是什么

时间复杂度并不是表示一个程序解决问题需要花多少时间,而是当程序所处理的问题规模扩大后,程序需要的时间长度对应增长得有多快。 一、多项式时间(Polynomial time) 多项式复杂度 容易看出,前面的几类复杂度被分为两种级别,其中后者的复杂度无论如何都远远大于前者。 像等,我们把它叫做多项式级复杂度,因为它的规模n出现在底数的位置; 非多项式级的复杂度 另一种像是等,它

LintCode 吹气球

有n个气球,编号为0到n-1,每个气球都有一个分数,存在nums数组中。每次吹气球i可以得到的分数为 nums[left] * nums[i] * nums[right],left和right分别表示i气球相邻的两个气球。当i气球被吹爆后,其左右两气球即为相邻。要求吹爆所有气球,得到最多的分数。 样例 给出 [4, 1, 5, 10] 返回 270 nums = [4, 1, 5, 10]

力扣452-用最少数量的箭引爆气球(Java详细题解)

题目链接:452. 用最少数量的箭引爆气球 - 力扣(LeetCode) 前情提要: 因为本人最近都来刷贪心类的题目所以该题就默认用贪心方法来做。 贪心方法:局部最优推出全局最优。 如果一个题你觉得可以用局部最优推出全局最优,并且没有反例来反驳的话就可以用贪心来试试。 题目思路: 其实本题模拟一遍后思路不难想,就是尽可能的找重叠的区域,一箭可以把重叠的全射了。 全局最优:用最小的弓箭

【0-1背包hard】力扣3181. 执行操作可获得的最大总奖励 II

给你一个整数数组 rewardValues,长度为 n,代表奖励的值。 最初,你的总奖励 x 为 0,所有下标都是 未标记 的。你可以执行以下操作 任意次 : 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。 如果 rewardValues[i] 大于 你当前的总奖励 x,则将 rewardValues[i] 加到 x 上(即 x = x + rewardValues[i]),并

算法训练第26天|452. 用最少数量的箭引爆气球|435. 无重叠区间|763.划分字母区间

LeetCode 452. 用最少数量的箭引爆气球 题目链接:452. 用最少数量的箭引爆气球 题目讲解:代码随想录 func findMinArrowShots(points [][]int) int {var res int = 1// 先按照第一位排序sort.Slice(points, func(i, j int)bool{return points[i][0] < points

06-1. Saving James Bond - Hard Version (30) BFS

06-1. Saving James Bond - Hard Version (30) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 CHEN, Yue This time let us consider the situation in the movie "Live

什么是NP问题,什么是NP hard问题,什么是NP完全问题

先来看一个小故事:(转自:http://zhm2k.blog.163.com/blog/static/5981506820095233143571/) 假如老板要你解决一个问题,你绞尽脑汁还是想不出来,叫天天不应,叫地地不灵,这时你走进老板办公室,可以采取3种策略: 1) 一副倒霉像,神情猥琐,可怜巴巴的说:老板,我没做出来,我想我是太蠢了…… boss:蠢材!滚! (失败……) 2)

[Algorithm][综合训练][kotori和气球][体操队形][二叉树中的最大路径和]详细讲解

目录 1.kotori和气球1.题目链接2.算法原理详解 && 代码实现 2.体操队形1.题目链接2.算法原理详解 && 代码实现 3.二叉树中的最大路径和1.题目链接2.算法原理详解 && 代码实现 1.kotori和气球 1.题目链接 kotori和气球 2.算法原理详解 && 代码实现 解法:数学 – 排列组合问题 --> n ∗ ( n − 1 ) m

Codeforces Round 961 (Div. 2) B2. Bouquet (Hard Version)

文章目录 写在前面思路code B2. Bouquet (Hard Version) 写在前面 今天下午写这道题时,有思路却没写出来,后面看了一下别人写的代码豁然开朗,这道题其实挺简单的,没写出来只能说 我太菜了QAQ 思路 考点:排序+贪心 首先我们可以在序列中任意组合 那么这个序列的初始排序并不重要,我们可以先将序列进行升序排序 排完序后,对于这题而言,无非就两种情