Leetcode 312 打气球 Burst Balloons C++ 史上最详细题解系列

2023-12-25 06:58

本文主要是介绍Leetcode 312 打气球 Burst Balloons C++ 史上最详细题解系列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:


Given n balloons, indexed from 0 to n-1. Each balloon is painted witha number on it represented by array nums. You are asked to burst allthe balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

  1. You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
  2. 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100、

Example:

  1. Given [3, 1, 5, 8]
  2. Return 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

有 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 =  3*1*5      +  3*5*8    +   1*3*8     + 1*8*1   = 167

这题实在是。。。太巧妙了,做的时候有感而发。

首先要知道的是要采用dp的方法做。

难点1
dp各项表示什么?

这关乎到做题选手的建模能力,我们代码中选择的是dp[i][j]等于从第i个数到第j个数的这个区间内的乘积最大值(包括i,j)

难点2
如何找递归式?

这里就更巧妙了,总的思路是先确定长度较小的区间,然后在这个区间里选一个数k成为最后一个被打爆的气球,dp[left][i-1]就是左边部分被打爆的最大值,dp[i+1][right]就是右边部分被打爆的最大值,所以我们只需要算最后一次打爆气球的分数再加上2旁区间打爆所有气球的最大值即可。读上面这句话三遍或以上直至读懂,读代码:

// Non-recursion
class Solution {
public:int maxCoins(vector<int>& nums) {int n = nums.size();//记录数组大小为nnums.insert(nums.begin(), 1);//在数组前加1nums.push_back(1);//后加1vector<vector<int> > dp(nums.size(), vector<int>(nums.size() , 0));//构造dp表,注意这时候nums.size()是加过2了的for (int len = 1; len <= n; ++len) {//遍历长度,这个长度len指的是区间[left,right]的长度for (int left = 1; left <= n - len + 1; ++left) {//遍历这个区间的起始点leftint right = left + len - 1;//通过上面的长度遍历求区间的结束点rightfor (int k = left; k <= right; ++k) {//遍历这个区间中的每个点dp[left][right] = max(dp[left][right], nums[left - 1] * nums[k] * nums[right + 1] + dp[left][k - 1] + dp[k + 1][right]);//dp[left][right]表示从left->right中所有点的连乘的最大值,包括left,right。//这个递推式的解释是,我选择k作为最后一个被消除的元素,那么这个区间的连乘的最大值为//nums[left-1]*nums[k]*nums[right+1](这时候left,right都不在了,因为k才是这个区间的最后一个元素,所以这个区间2边相邻的元素是nums[left-1],nums[right+1].这个式子表示最后一次计算的结果,//dp[left][k-1]指的是从left->k-1乘完后的最大值(包括left,k-1),dp[k+1][right]同理}}}return dp[1][n];//返回整个最大区间的连乘最大值(第1个到第n个)}
};

补充:

1.dp[left][k-1] , dp[k+1][right]是你想求就求啊,你以为这是递归函数?

答:这是这道题最巧妙的地方了,仔细看我们的for循环的顺序,第一次我们取长度为1的区间(也就是每个区间只有一个数),第二次for遍历时候取的长度为2的区间,这时候长度为1的区间的结果已经求出来了!刚好可以被长度为2的区间用到!伟大的dp!

2.行行行,那有些时候dp[k+1][right]里的k+1 > right了怎么说?

答:确实会出现这种情况,比如遍历长度为1的区间时。但是这并不影响做题,因为那些都会是0,经过初始化后还没动。

 
来源:CSDN 
原文:https://blog.csdn.net/weixin_41958153/article/details/81903551 

这篇关于Leetcode 312 打气球 Burst Balloons C++ 史上最详细题解系列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringBoot改造MCP服务器的详细说明(StreamableHTTP 类型)

《SpringBoot改造MCP服务器的详细说明(StreamableHTTP类型)》本文介绍了SpringBoot如何实现MCPStreamableHTTP服务器,并且使用CherryStudio... 目录SpringBoot改造MCP服务器(StreamableHTTP)1 项目说明2 使用说明2.1

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析(结合应用场景)

《nginx-t、nginx-sstop和nginx-sreload命令的详细解析(结合应用场景)》本文解析Nginx的-t、-sstop、-sreload命令,分别用于配置语法检... 以下是关于 nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析,结合实际应

Spring boot整合dubbo+zookeeper的详细过程

《Springboot整合dubbo+zookeeper的详细过程》本文讲解SpringBoot整合Dubbo与Zookeeper实现API、Provider、Consumer模式,包含依赖配置、... 目录Spring boot整合dubbo+zookeeper1.创建父工程2.父工程引入依赖3.创建ap

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

创建Java keystore文件的完整指南及详细步骤

《创建Javakeystore文件的完整指南及详细步骤》本文详解Java中keystore的创建与配置,涵盖私钥管理、自签名与CA证书生成、SSL/TLS应用,强调安全存储及验证机制,确保通信加密和... 目录1. 秘密键(私钥)的理解与管理私钥的定义与重要性私钥的管理策略私钥的生成与存储2. 证书的创建与

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被