【C语言】Leetcode-312 戳气球

2024-06-09 23:20
文章标签 leetcode 语言 气球 312

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

文章目录

  • 题目
  • 思路
  • 代码如下


题目

链接: Leetcode-312 戳气球

在这里插入图片描述


思路

我们观察戳气球的操作,发现这会导致两个气球从不相邻变成相邻,使得后续操作难以处理。于是我们倒过来看这些操作,将全过程看作是每次添加一个气球。

首先
我们需要创建一个 v a l val val 数组,用来存储所有的元素,其中 v a l [ 0 ] val[0] val[0] v a l [ n u m s S i z e + 1 ] val[numsSize+1] val[numsSize+1] 的位置用来存放两头的超出数组边界的1,剩下的从1开始就是 n u m s nums nums 数组里的元素

然后
我们定义 s o l v e solve solve 方法,令 s l o v e ( i , j ) slove(i,j) slove(i,j) 表示开区间 ( i , j ) (i,j) (i,j) 内的位置全部填满气球能够得到的最多硬币数。由于时开区间,因此区间两端的气球编号就是 v a l [ i [ val[i[ val[i[ v a l [ j ] val[j] val[j]

接着
我们要对这个 s l o v e slove slove 方法进行分类讨论

i > = j − 1 i >= j-1 i>=j1 时,开区间中没有气球, s l o v e ( i , j ) slove(i,j) slove(i,j) 的值为0

i < j − 1 i < j-1 i<j1 时,我们美剧开区间 ( i , j ) (i,j) (i,j) 内的全部位置 m i d mid mid ,令 m i d mid mid 为当前区间第一个添加的气球,该操作能得到的硬币数为 v a l [ i ] ∗ v a l [ m i d ] ∗ v a l [ j ] val[i] * val[mid] * val[j] val[i]val[mid]val[j]

同时我们利用递归,去计算分割出的两区间对 s o l v e ( i , j ) solve(i,j) solve(i,j) 的贡献,这三项之和的最大值,即为 s o l v e ( i , j ) solve(i,j) solve(i,j) 的值

还有
因为我们是利用递归将每种结果都计算出来,所以他的工程量是很大的,为了降低时间复杂度,我们可以建立一个二维数组,来根据 l e f t left left r i g h t right right 的值存放这个开区间内的最大贡献量

代码如下

int rec[302][302];
int val[302];int solve(int left, int right) {if (left >= right - 1)return 0;if (rec[left][right] != -1)return rec[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);rec[left][right] = fmax(rec[left][right], sum);}return rec[left][right];
}int maxCoins(int* nums, int numsSize) {memset(rec, -1, sizeof(rec));val[0] = val[numsSize + 1] = 1;for (int i = 1; i <= numsSize; i++) {val[i] = nums[i - 1];}return solve(0, numsSize + 1);
}

这篇关于【C语言】Leetcode-312 戳气球的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Go语言中make和new的区别及说明

《Go语言中make和new的区别及说明》:本文主要介绍Go语言中make和new的区别及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 概述2 new 函数2.1 功能2.2 语法2.3 初始化案例3 make 函数3.1 功能3.2 语法3.3 初始化

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

Go语言中泄漏缓冲区的问题解决

《Go语言中泄漏缓冲区的问题解决》缓冲区是一种常见的数据结构,常被用于在不同的并发单元之间传递数据,然而,若缓冲区使用不当,就可能引发泄漏缓冲区问题,本文就来介绍一下问题的解决,感兴趣的可以了解一下... 目录引言泄漏缓冲区的基本概念代码示例:泄漏缓冲区的产生项目场景:Web 服务器中的请求缓冲场景描述代码

Go语言如何判断两张图片的相似度

《Go语言如何判断两张图片的相似度》这篇文章主要为大家详细介绍了Go语言如何中实现判断两张图片的相似度的两种方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 在介绍技术细节前,我们先来看看图片对比在哪些场景下可以用得到:图片去重:自动删除重复图片,为存储空间"瘦身"。想象你是一个

Go语言中Recover机制的使用

《Go语言中Recover机制的使用》Go语言的recover机制通过defer函数捕获panic,实现异常恢复与程序稳定性,具有一定的参考价值,感兴趣的可以了解一下... 目录引言Recover 的基本概念基本代码示例简单的 Recover 示例嵌套函数中的 Recover项目场景中的应用Web 服务器中

Go语言中使用JWT进行身份验证的几种方式

《Go语言中使用JWT进行身份验证的几种方式》本文主要介绍了Go语言中使用JWT进行身份验证的几种方式,包括dgrijalva/jwt-go、golang-jwt/jwt、lestrrat-go/jw... 目录简介1. github.com/dgrijalva/jwt-go安装:使用示例:解释:2. gi

Go 语言中的 Struct Tag 的用法详解

《Go语言中的StructTag的用法详解》在Go语言中,结构体字段标签(StructTag)是一种用于给字段添加元信息(metadata)的机制,常用于序列化(如JSON、XML)、ORM映... 目录一、结构体标签的基本语法二、json:"token"的具体含义三、常见的标签格式变体四、使用示例五、使用

Go语言使用slices包轻松实现排序功能

《Go语言使用slices包轻松实现排序功能》在Go语言开发中,对数据进行排序是常见的需求,Go1.18版本引入的slices包提供了简洁高效的排序解决方案,支持内置类型和用户自定义类型的排序操作,本... 目录一、内置类型排序:字符串与整数的应用1. 字符串切片排序2. 整数切片排序二、检查切片排序状态: