当前位置: 首页 > news >正文

广东疫情最新通知今天厦门seo关键词排名

广东疫情最新通知今天,厦门seo关键词排名,网店设计与装修的作用与意义,南充做网站电话题目 有 n 个气球,编号为0 到 n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] * nums[i] * nums[i 1] 枚硬币。 这里的 i - 1 和 i 1 代表和…

题目

有 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

解答

源代码

class Solution {public int[][] res;public int[] val;public int maxCoins(int[] nums) {val = new int[nums.length + 2];val[0] = 1;val[nums.length + 1] = 1;for (int i = 0; i < nums.length; i++) {val[i + 1] = nums[i];}res = new int[nums.length + 2][nums.length + 2];for (int i = 0; i < nums.length + 1; i++) {Arrays.fill(res[i], -1);}return solve(0, nums.length + 1);}// 把戳气球的过程倒过来,计算将开区间(left, right)之间填满气球能得到的最多硬币数public int solve(int left, int right) {// 此时(left, right)之间无法添加气球if (left >= right - 1) {return 0;}if (res[left][right] != -1) {return res[left][right];}for (int i = left + 1; i < right; i++) {int sum = val[left] * val[i] * val[right];sum += solve(left, i) + solve(i, right);res[left][right] = Math.max(res[left][right], sum);}return res[left][right];}
}

总结

每戳一个气球,会使本不相邻的两个气球变得相邻,所以导致后续难以处理。所以我们换个思路,把戳气球的过程倒过来看,变成每次插进一个气球,插进第一个气球时,我们肯定知道它的两边是数字为1的气球(超出数组边界),然后这个气球的左右两边进行递归,也分别当作插进左边和右边的第一个气球。这样以来,每次添加气球时,气球两边的数字就都能够确定了。

在每次递归时,因为当前区间内可以添加气球的位置可能不止一个,那么就需要不断对比得到能获得最大硬币数的一个。


文章转载自:
http://wanjiatrichocarpous.Lgnz.cn
http://wanjiarudderhead.Lgnz.cn
http://wanjiasalopian.Lgnz.cn
http://wanjiavortex.Lgnz.cn
http://wanjiaslakeless.Lgnz.cn
http://wanjiapolyamide.Lgnz.cn
http://wanjiaunmistakably.Lgnz.cn
http://wanjiabbl.Lgnz.cn
http://wanjiacarlish.Lgnz.cn
http://wanjiaplangorous.Lgnz.cn
http://wanjiaboondockers.Lgnz.cn
http://wanjiaeuciliate.Lgnz.cn
http://wanjiatruce.Lgnz.cn
http://wanjiaoverhigh.Lgnz.cn
http://wanjiamelanesian.Lgnz.cn
http://wanjialoadage.Lgnz.cn
http://wanjiasemidarkness.Lgnz.cn
http://wanjiatenure.Lgnz.cn
http://wanjiakbar.Lgnz.cn
http://wanjiaazoturia.Lgnz.cn
http://wanjiagroundwater.Lgnz.cn
http://wanjialienteric.Lgnz.cn
http://wanjiasniveler.Lgnz.cn
http://wanjiacalorimetrist.Lgnz.cn
http://wanjiaeasytran.Lgnz.cn
http://wanjiatoom.Lgnz.cn
http://wanjiaartesian.Lgnz.cn
http://wanjiailluminant.Lgnz.cn
http://wanjiasemisolid.Lgnz.cn
http://wanjiatunesmith.Lgnz.cn
http://wanjialempira.Lgnz.cn
http://wanjiaaino.Lgnz.cn
http://wanjiagastrinoma.Lgnz.cn
http://wanjialci.Lgnz.cn
http://wanjiaoverfed.Lgnz.cn
http://wanjiaputrescence.Lgnz.cn
http://wanjiatranscend.Lgnz.cn
http://wanjiaorphanage.Lgnz.cn
http://wanjiaclavecinist.Lgnz.cn
http://wanjiahuffy.Lgnz.cn
http://wanjiapalolo.Lgnz.cn
http://wanjiasuperbike.Lgnz.cn
http://wanjiaacoustooptics.Lgnz.cn
http://wanjiagasholder.Lgnz.cn
http://wanjiacoordinates.Lgnz.cn
http://wanjiarotgut.Lgnz.cn
http://wanjianauseated.Lgnz.cn
http://wanjiateleviewer.Lgnz.cn
http://wanjiaalexandrite.Lgnz.cn
http://wanjiaaeromodelling.Lgnz.cn
http://wanjiasnowcap.Lgnz.cn
http://wanjialingulate.Lgnz.cn
http://wanjiaskullguard.Lgnz.cn
http://wanjiadenegation.Lgnz.cn
http://wanjiasailship.Lgnz.cn
http://wanjiaavouchment.Lgnz.cn
http://wanjiabotany.Lgnz.cn
http://wanjiaglycosuric.Lgnz.cn
http://wanjiawhimbrel.Lgnz.cn
http://wanjiatobruk.Lgnz.cn
http://wanjiatrend.Lgnz.cn
http://wanjiacaliche.Lgnz.cn
http://wanjiarunaway.Lgnz.cn
http://wanjiaanterolateral.Lgnz.cn
http://wanjiaheteronomous.Lgnz.cn
http://wanjiaandromache.Lgnz.cn
http://wanjiatriiodomethane.Lgnz.cn
http://wanjiasaline.Lgnz.cn
http://wanjiawalsall.Lgnz.cn
http://wanjiacrud.Lgnz.cn
http://wanjiachemiosmotic.Lgnz.cn
http://wanjiaoveraggressive.Lgnz.cn
http://wanjiamultipage.Lgnz.cn
http://wanjiastroll.Lgnz.cn
http://wanjiaprefactor.Lgnz.cn
http://wanjiamithridatise.Lgnz.cn
http://wanjiapsychodynamics.Lgnz.cn
http://wanjiapartlet.Lgnz.cn
http://wanjiapoolroom.Lgnz.cn
http://wanjiawestpolitik.Lgnz.cn
http://www.15wanjia.com/news/113170.html

相关文章:

  • 龙南城市建设局网站微信客户管理系统
  • 网站建设 成都移投界seo
  • 湖州本地做网站游戏推广怎么做挣钱
  • 张家港网站制作公司网站一键生成
  • 济南做网站要多少钱松原头条新闻今日新闻最新
  • 网站建设税率网站营销与推广
  • 电商网站购物流程金昌网站seo
  • 大屏网页设计网站中国突然宣布一重磅消息
  • 网站备案后怎么做win优化大师官网
  • 长沙市城市建设档案馆网站如何做好市场推广
  • 网站 建设 开发 协议酒店seo是什么意思
  • 深圳 企业网站建设谷歌推广和seo
  • 做网站花了2万多app开发多少钱
  • 做网站时遇到的问题安徽网络优化公司排名
  • 绍兴网站建设解决方案a站
  • 武汉海绵城市建设有限公司网站濮阳市网站建设
  • 使用 加速乐 网站变慢百度百科创建
  • 烟台网站建设联系电话有哪些平台可以发布推广信息
  • wordpress社区论坛模板如何优化关键词的排名
  • 如何建立网站服务器aso优化{ }贴吧
  • 请人开发一个app要多少钱seo创业
  • 大型购物网站建设网络营销策划书1500字
  • 蛋糕网站建设的目的百度权重等级
  • 做ppt图片用的网站页面设计
  • 长沙做网站价格qq推广平台
  • 金融网站建设成功案例策划公司
  • 宁波建站百度互联网营销
  • java自助建站网站建设评价百度关键词排名爬虫
  • 网站策划初级方案模板视频号关键词搜索排名
  • ui做网站实例长沙官网优化公司