【Leetcode刷题篇】leetcode312 戳气球
发布日期:2021-06-29 15:35:41
浏览次数:3
分类:技术文章
本文共 875 字,大约阅读时间需要 2 分钟。
有 n 个气球,编号为0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i ,就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后,气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
说明:
你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的所以并不能被戳破。 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
示例:
输入: [3,1,5,8] 输出: 167 解释: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 315 + 358 + 138 + 181 = 167
解题思路:动态规划
package com.lcz.leetcode;public class Leetcode312 { class Solution { public int maxCoins(int[] nums) { int n = nums.length; // 动态规划 int[][] dp = new int[n+2][n+2]; // 新数组 int[] coins = new int[n+2]; for(int i=1;i<=n;i++) { coins[i] = nums[i-1]; } coins[0] = coins[n+1] = 1; // 三重 遍历 for(int i=n-1;i>=0;i--) { for(int j=i+2;j<=n+1;j++) { for(int k=i+1;k
转载地址:https://codingchaozhang.blog.csdn.net/article/details/111866085 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月20日 16时57分53秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Windows创建本地版本库(1)
2019-04-29
基于java的酒店管理系统的设计与实现
2019-04-29
基于WEB的仓库管理系统的设计与实现
2019-04-29
基于java的web聊天系统
2019-04-29
基于java的俄罗斯方块的设计与实现
2019-04-29
基于java的魂斗罗的设计
2019-04-29
基于java的网页内容管理
2019-04-29
基于java的学生管理系统
2019-04-29
基于java网盘搜索的设计与实现
2019-04-29
基于SSM的仿小米商城源码
2019-04-29
基于SSM的医院人事管理系统的设计与实现
2019-04-29
基于SSM的网上购物系统的设计与开发
2019-04-29
基于SSM框架的BS微博系统的设计与实现
2019-04-29
超市订单管理系统
2019-04-29
基于ssm的民宿网站
2019-04-29
基于JavaWeb的物流管理系统的设计与实现
2019-04-29
基于Java的飞机大战游戏的设计与实现论文
2019-04-29
基于java实现的超级马里奥游戏
2019-04-29
keepalived 实现高可用,负载均衡
2019-04-29