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

相关文章

Python设置Cookie永不超时的详细指南

《Python设置Cookie永不超时的详细指南》Cookie是一种存储在用户浏览器中的小型数据片段,用于记录用户的登录状态、偏好设置等信息,下面小编就来和大家详细讲讲Python如何设置Cookie... 目录一、Cookie的作用与重要性二、Cookie过期的原因三、实现Cookie永不超时的方法(一)

SpringBoot整合liteflow的详细过程

《SpringBoot整合liteflow的详细过程》:本文主要介绍SpringBoot整合liteflow的详细过程,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋...  liteflow 是什么? 能做什么?总之一句话:能帮你规范写代码逻辑 ,编排并解耦业务逻辑,代码

从入门到精通C++11 <chrono> 库特性

《从入门到精通C++11<chrono>库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段(Durat

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多,因为它实际属于c++20最为重要的

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

浏览器插件cursor实现自动注册、续杯的详细过程

《浏览器插件cursor实现自动注册、续杯的详细过程》Cursor简易注册助手脚本通过自动化邮箱填写和验证码获取流程,大大简化了Cursor的注册过程,它不仅提高了注册效率,还通过友好的用户界面和详细... 目录前言功能概述使用方法安装脚本使用流程邮箱输入页面验证码页面实战演示技术实现核心功能实现1. 随机

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

C++11委托构造函数和继承构造函数的实现

《C++11委托构造函数和继承构造函数的实现》C++引入了委托构造函数和继承构造函数这两个重要的特性,本文主要介绍了C++11委托构造函数和继承构造函数的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、委托构造函数1.1 委托构造函数的定义与作用1.2 委托构造函数的语法1.3 委托构造函

C++11作用域枚举(Scoped Enums)的实现示例

《C++11作用域枚举(ScopedEnums)的实现示例》枚举类型是一种非常实用的工具,C++11标准引入了作用域枚举,也称为强类型枚举,本文主要介绍了C++11作用域枚举(ScopedEnums... 目录一、引言二、传统枚举类型的局限性2.1 命名空间污染2.2 整型提升问题2.3 类型转换问题三、C