【LeetCode】312.戳气球
题目
有 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.length1 <= n <= 3000 <= 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的气球(超出数组边界),然后这个气球的左右两边进行递归,也分别当作插进左边和右边的第一个气球。这样以来,每次添加气球时,气球两边的数字就都能够确定了。
在每次递归时,因为当前区间内可以添加气球的位置可能不止一个,那么就需要不断对比得到能获得最大硬币数的一个。
相关文章:
【LeetCode】312.戳气球
题目 有 n 个气球,编号为0 到 n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] * nums[i] * nums[i 1] 枚硬币。 这里的 i - 1 和 i 1 代表和…...
商业数据分析概论
🐳 我正在和鲸社区参加“商业数据分析训练营活动” https://www.heywhale.com/home/competition/6487de6649463ee38dbaf58b ,以下是我的学习笔记: 学习主题:波士顿房价数据快速查看 日期:2023.9.4 关键概念/知识点&…...
Golang GUI框架
Golang GUI框架fyne fyne简介第一个fyne应用fyne应用程序和运行循环fyne更新GUI内容fyne窗口处理fyne解决中文乱码问题fyne应用打包fyne画布和画布对象fyne容器和布局fyne绘制和动画fyne盒子布局fyne网格grid布局fyne网格包裹布局fyne边框布局fyne表单布局fyne中心布局fyne ma…...
LeetCode刷题笔记【24】:贪心算法专题-2(买卖股票的最佳时机II、跳跃游戏、跳跃游戏II)
文章目录 前置知识122.买卖股票的最佳时机II题目描述贪心-直观写法贪心-优化代码更简洁 55. 跳跃游戏题目描述贪心-借助ability数组贪心-只用int far记录最远距离 45.跳跃游戏II题目描述回溯算法贪心算法 总结 前置知识 参考前文 参考文章: LeetCode刷题笔记【23】…...
游戏出现卡顿有哪些因素
一、服务器CPU内存占用过大会导致卡顿,升级CPU内存或者优化自身程序占用都可以解决。 二、带宽跑满导致卡,可以升级带宽解决。 二、平常不卡,有大型的活动的时候会卡,这方面主要是服务器性能方面不够导致的,性能常说…...
学习Bootstrap 5的第八天
目录 加载器 彩色加载器 实例 闪烁加载器 实例 加载器大小 实例 加载器按钮 实例 分页 分页的基本结构 实例 活动状态 实例 禁用状态 实例 分页大小 实例 分页对齐 实例 面包屑(Breadcrumbs) 实例 加载器 彩色加载器 在 Bootstr…...
vue中自定义指令
什么是指令 在Vue.js中,指令是一种特殊的 token,用于在模板中以声明式方式将响应式数据绑定到 DOM 元素上,从而实现与 DOM 元素的交互和操作。指令以 “v-” 前缀开始,后跟指令的名称,例如 v-model、v-bind 和 v-on。…...
Python:安装Flask web框架hello world
安装easy_install pip install distribute 安装pip easy_install pip 安装 virtualenv pip install virtualenv 激活Flask pip install Flask 创建web页面demo.py from flask import Flask app Flask(__name__)app.route(/) def hello_world():return Hello World! 2023if _…...
小程序点击复制功能制作
在wxml文件中添加一个按钮或需要点击的元素,并绑定点击事件监听器2 <button bindtap"copyText">点击复制</button> 2 在对应的js文件中定义点击事件处理函数,并在函数中调用小程序的API进行复制操作, copyText(e){co…...
20230909java面经整理
1.java常用集合 ArrayList动态数组,动态调整大小,实现List接口 LinkedList双向链表,实现list和queue接口,适用于频繁插入和删除操作 HashSet无序,使用哈希表实现 TreeSet有序,使用红黑树实现 HashMap无序&…...
常用的css命名规则
一、命名规则说明: 1)、所有的命名最好都小写 2)、属性的值一定要用双引号(“”)括起来 3)、给图片加上alt标签 4)、尽量使用英文命名原则 5)、尽量不缩写,除非一看就明白的单词 二、相对网页外…...
【Linux编程Shell自动化脚本】03 shell四剑客(find、sed、grep、awk)
文章目录 一、find1. 常用expression2. 时间参数3. 其他选项参数3.1 查找深度3.2 执行命令 二、sed1. 常用命令选项2. 常用动作脚本命令2.1 s 替换2.2 已匹配字符串标记&2.3 在当前行前后插入文本 a\ 和 i\2.4 p 打印指定行2.5 匹配行的方式2.5.1 以数字形式指定行区间2.5.…...
java的springboot框架中使用logback日志框架使用RabbitHandler注解为什么获取不到消费的traceId信息?
当使用 Logback 日志框架和 RabbitMQ 的 RabbitHandler 注解时,如果无法获取消费的 traceId 信息,可能是因为在处理 RabbitMQ 消息时,没有正确地将 traceId 传递到日志中。 为了将 traceId 传递到日志中,你可以利用 MDCÿ…...
初探Vue.js及Vue-Cli
一、使用vue框架的简单示例 我们本次的vue系列就使用webstorm来演示: 对于vue.js的安装我们直接使用script的cdn链接来实现 具体可以参考如下网址: https://www.bootcdn.cn/ 进入vue部分,可以筛选版本,我这里使用的是2.7.10版本的ÿ…...
大数据课程K21——Spark的SparkSQL基础语法
文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 掌握Spark的SparkSQL通过方法来使用; ⚪ 掌握Spark的SparkSQL通过sql语句来调用; 一、SparkSQL基础语法——通过方法来使用 1. 查询 df.select("id","name").show()…...
【实践篇】Redis最强Java客户端(三)之Redisson 7种分布式锁使用指南
文章目录 0. 前言1. Redisson 7种分布式锁使用指南1.1 简单锁:1.2 公平锁:1.3 可重入锁:1.4 红锁:1.5 读写锁:1.6 信号量:1.7 闭锁: 2. Spring boot 集成Redisson 验证分布式锁3. 参考资料4. 源…...
卫星通话过后,卫星导航产业被彻底激活
华为新手机发布后,其主打的卫星通话功能备受热议。在卫星产业链发展的背后,下一个大产业在哪里让人颇为好奇。 目前,卫星导航颇被看好,或将引领下一个技术狂潮。它的特点是产业大、发展快、参与者多。继电动汽车、新能源和芯片产…...
【算法训练-链表 七】【排序】:链表排序、链表的奇偶重排、重排链表
废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【链表的排序】,使用【链表】这个基本的数据结构来实现,这个高频题的站点是:CodeTop,筛选条件为&am…...
LGB的两种写法
方法一 import lightgbm as lgb import pandas as pd from sklearn.model_selection import train_test_split, KFold from sklearn.metrics import accuracy_score# 读取训练集和测试集数据 train_data pd.read_csv(train.csv) test_data pd.read_csv(test.csv)# 分割特征和…...
【Unity的HDRP下ShaderGraph实现权重缩放全息投影_(内附源码)】
实现权重缩放全息投影 效果如下 效果如下 顶点位置偏移 链接: 提取码:1234...
告别VisionPro工具箱翻找!手把手教你用脚本搞定‘冷门’输入输出类型
VisionPro高效开发:用脚本管理非常规输入输出类型 在VisionPro项目开发中,我们经常遇到一些特殊的数据类型需求——比如需要处理二维数组、目录信息或者自定义结构体。这些"非常规"类型往往无法通过图形界面快速添加,而手动在工具…...
NVIDIA GPU监控效能深度解析:nvitop如何破解多用户环境资源管理难题
NVIDIA GPU监控效能深度解析:nvitop如何破解多用户环境资源管理难题 【免费下载链接】nvitop An interactive NVIDIA-GPU process viewer and beyond, the one-stop solution for GPU process management. 项目地址: https://gitcode.com/gh_mirrors/nv/nvitop …...
1.NCM格式解密技术全解析:从原理到实战的音乐自由之路
1.NCM格式解密技术全解析:从原理到实战的音乐自由之路 【免费下载链接】ncmdump ncmdump - 网易云音乐NCM转换 项目地址: https://gitcode.com/gh_mirrors/ncmdu/ncmdump 问题引入:当音乐遭遇数字围栏 "花了千元订阅的无损音乐,…...
FLUX.1-dev镜像免配置部署:5分钟启动影院级Text-to-Image服务
FLUX.1-dev镜像免配置部署:5分钟启动影院级Text-to-Image服务 想体验一下“所见即所得”的顶级AI绘画吗?今天,我们一起来部署一个开箱即用的FLUX.1-dev旗舰版镜像。它集成了当前开源界最强的文本生成图像模型之一,并且针对24GB显…...
s2-pro镜像管理:容器健康检查脚本编写与自动化服务恢复方案
s2-pro镜像管理:容器健康检查脚本编写与自动化服务恢复方案 1. 引言 s2-pro作为专业级语音合成模型镜像,在实际业务场景中承担着重要角色。当服务出现异常时,如何快速发现问题并自动恢复成为运维工作的关键。本文将详细介绍如何为s2-pro编写…...
龙芯2K0300智能车开发避坑指南:从引脚复用冲突到龙邱库完美适配的全流程记录
龙芯2K0300智能车开发实战:引脚复用冲突与龙邱库适配深度解析 第一次将龙芯2K0300处理器应用于智能车开发时,我对着原理图反复确认了三次引脚分配——直到电机突然不受控地高速旋转,才意识到自己掉进了GPIO复用功能的陷阱。这不是普通的嵌入式…...
终极指南:如何安全自定义英雄联盟客户端视觉体验
终极指南:如何安全自定义英雄联盟客户端视觉体验 【免费下载链接】LeaguePrank 项目地址: https://gitcode.com/gh_mirrors/le/LeaguePrank LeaguePrank是一款基于LCU API开发的英雄联盟视觉定制工具,专门帮助玩家在不修改游戏文件、不触碰内存的…...
一键召唤AI画师!次元画室让角色设计变得如此简单
一键召唤AI画师!次元画室让角色设计变得如此简单 你是否曾经有过这样的经历?脑海中浮现出一个绝妙的角色形象,却苦于无法将它完美呈现;或者为了设计游戏角色,不得不花费重金聘请专业画师;又或者作为小说作…...
开箱即用!LongCat动物百变秀本地部署指南,小白也能快速上手
开箱即用!LongCat动物百变秀本地部署指南,小白也能快速上手 1. 什么是LongCat动物百变秀? LongCat动物百变秀是一款基于美团开源模型开发的AI图片编辑工具,专门用于动物图片的创意编辑。它最大的特点是能够通过简单的自然语言描…...
Wan2.2-I2V-A14B与数据库联动:自动化生成电商商品动态详情页视频
Wan2.2-I2V-A14B与数据库联动:自动化生成电商商品动态详情页视频 1. 电商视频制作的痛点与机遇 电商平台每天都有大量新品上架,传统的商品详情页视频制作方式面临巨大挑战。一个中型电商平台每月可能新增上千款商品,如果每款商品都需要人工…...
