【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...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
