力扣_动态规划1—买卖股票的最佳时机
题目
给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
方法—动态规划
- 由于我们最多可以完成两笔交易,因此在任意一天结束之后,我们会处于以下五个状态中的一种:
- 未进行过任何操作;(利润为0,忽略)
- 只进行过一次买操作;
- 进行了一次买操作和一次卖操作,即完成了一笔交易;
- 在完成了一笔交易的前提下,进行了第二次买操作;
- 完成了全部两笔交易。
- 四种状态的最大利润分别记为 d p 1 , d p 2 , d p 3 , d p 4 dp_1, dp_2, dp_3, dp_4 dp1,dp2,dp3,dp4
- 状态转移:
- d p 1 = m a x ( d p 1 , − p r i c e s [ i ] ) dp_1 = max(dp_1, -prices[i]) dp1=max(dp1,−prices[i]) # 不做任何操作或者今天买
- d p 2 = m a x ( d p 2 , d p 1 + p r i c e s [ i ] ) dp_2 = max(dp_2, dp_1+prices[i]) dp2=max(dp2,dp1+prices[i]) # 不做任何操作或者今天卖
- d p 3 = m a x ( d p 3 , d p 2 − p r i c e s [ i ] ) dp_3 = max(dp_3, dp_2-prices[i]) dp3=max(dp3,dp2−prices[i]) # 不做任何操作或者今天买
- d p 4 = m a x ( d p 4 , d p 3 + p r i c e s [ i ] ) dp_4 = max(dp_4, dp_3+prices[i]) dp4=max(dp4,dp3+prices[i]) # 不做任何操作或者今天卖
- 初始状态
- d p 1 = − p r i c e s [ 0 ] dp_1 = -prices[0] dp1=−prices[0] # 第一天买入
- d p 2 = 0 dp_2 = 0 dp2=0 # 第一天买入并立即卖掉
- d p 3 = − p r i c e s [ 0 ] dp_3 = -prices[0] dp3=−prices[0] # 第一支卖了后立即买入第二支
- d p 4 = 0 dp_4 = 0 dp4=0 # 立即卖掉第二支
代码
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int dp1 = -prices[0]; // 持有第一支int dp2 = 0; // 卖或已经卖了第一支int dp3 = -prices[0]; // 持有第二支int dp4 = 0; // 卖或已经卖了第二支int ret = 0;for(int i = 1; i < n; i++){dp1 = max(dp1, -prices[i]);dp2 = max(dp2, prices[i]+dp1);dp3 = max(dp3, dp2-prices[i]);dp4 = max(dp4, prices[i]+dp3);}return dp4;}
};
相关文章:
力扣_动态规划1—买卖股票的最佳时机
题目 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 方法—动态…...
苍穹外卖问题记录(持续更新)
Day01_3.2.4前后端联调 1. 前端无法登录 (1)确保nginx服务器已经启动 (2)查看自己数据库的用户名和密码是否和老师的一样,不一样的话需要在application-dev.yml文件中把老师的用户名密码修改成自己的 老师的用户名…...
结合大象机器人六轴协作机械臂myCobot 280 ,解决特定的自动化任务和挑战!(下)
Limo Pro 小车建图导航 引言 前景提要:我们在上文介绍了使用LIMO cobot 实现一个能够执行复杂任务的复合机器人系统的应用场景的项目,从以下三个方面:概念设计、系统架构以及关键组件。 本文主要深入项目内核的主要部分,同样也主要…...
加速 Webpack 构建:提升效率的秘诀
🤍 前端开发工程师、技术日更博主、已过CET6 🍨 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 🕠 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 🍚 蓝桥云课签约作者、上架课程《Vue.js 和 E…...
Qt自定义标题栏的多屏适配
标题栏自定义 参考博客 : https://blog.csdn.net/goforwardtostep/article/details/53494800 多屏适配 MyTitleBar类抽象定义了自定义标题栏,使用起来相对方便。但是在多屏情况下,窗口初次显示只能在主屏幕上,如果拖到其他屏幕…...
【MySQL篇】 MySQL基础学习
文章目录 前言基础数据类型DDL数据库操作查询数据库创建数据库删除数据库使用数据库 DDL表操作创建表查询表修改表删除 DML-增删改添加数据更改数据删除数据 DQL-查询基础查询条件查询聚合函数分组查询排序查询分页查询编写顺序 DML-用户及权限用户管理权限控制 函数字符串函数…...
Qt多弹窗实现包括QDialog、QWidget、QMainWindow
1.相关说明 独立Widget窗口、嵌入式Widget、嵌入式MainWindow窗口、独立MainWindow窗口等弹窗的实现 相关界面包含关系 2.相关界面 3.相关代码 mainwindow.cpp #include "mainwindow.h" #include "ui_mainwindow.h" #include "tformdoc.h" #incl…...
Django高级之-forms组件
Django高级之-forms组件 1 校验字段功能 针对一个实例:注册用户讲解。 模型:models.py class UserInfo(models.Model):namemodels.CharField(max_length32)pwdmodels.CharField(max_length32)emailmodels.EmailField()模版文件 <!DOCTYPE html&g…...
GPT实战系列-LangChain实现简单链
GPT实战系列-LangChain实现简单链 LangChain GPT实战系列-LangChain如何构建基通义千问的多工具链 GPT实战系列-构建多参数的自定义LangChain工具 GPT实战系列-通过Basetool构建自定义LangChain工具方法 GPT实战系列-一种构建LangChain自定义Tool工具的简单方法 GPT实战系…...
关于tomcat服务器配置及性能优化的20道高级面试题
1. 请描述Tomcat服务器的基本架构和组件。 Tomcat服务器的基本架构主要包括Server、Service、Connector和Container等组件。具体来看: Server:是Tomcat中最顶层的容器,代表着整个服务器。它负责运行Tomcat服务器,例如打开和关闭…...
LeetCode 1315.祖父节点值为偶数的节点和
给你一棵二叉树,请你返回满足以下条件的所有节点的值之和: 该节点的祖父节点的值为偶数。(一个节点的祖父节点是指该节点的父节点的父节点。) 如果不存在祖父节点值为偶数的节点,那么返回 0 。 示例: 输入…...
C语言分支和循环总结
文章目录 概要结构介绍不同结构的语句简单运用小结 概要 C语言中分为三种结构:顺序结构,选择结构,循环结构 结构介绍 顺序结构就是从上到下,从左到右等等;选择结构可以想象是Y字路口就是到了一个地方会有不同的道路…...
【Echarts】曲线图上方显示数字以及自定义值,标题和副标题居中,鼠标上显示信息以及自定义信息
欢迎来到《小5讲堂》 大家好,我是全栈小5。 这是《前端》系列文章,每篇文章将以博主理解的角度展开讲解, 特别是针对知识点的概念进行叙说,大部分文章将会对这些概念进行实际例子验证,以此达到加深对知识点的理解和掌握…...
双环PID控制详细讲解
参考博客: (1)PID双环控制(速度环和位置环) (2)PID控制(四)(单环与双环PID) (3)内外双环pid算法 0 单环PID 目标位置→系…...
深入解析Java内存模型
一、背景 并发编程本质问题是:CPU、内存以及IO三者之间的速度差异。CPU速度快于内存、内存访问速度又远远快于IO,根据木桶理论,程序性能取决于最慢的操作,即IO操作。这样会出现CPU和内存交互时,CPU性能无法被充分利用…...
python使用国内镜像源
使用格式 格式为:pip install 库名 -i 镜像地址(注意空格的存在) pip install pandas -i https://pypi.tuna.tsinghua.edu.cn/simple 推荐的镜像源: 清华大学(推荐):https://pypi.tuna.tsing…...
【动态规划】代码随想录算法训练营第四十六天 |139.单词拆分,关于多重背包,你该了解这些! ,背包问题总结篇!(待补充)
139.单词拆分 1、题目链接:. - 力扣(LeetCode) 2、文章讲解:代码随想录 3、题目: 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词…...
WordPress建站入门教程:如何选择和设置固定链接结构?
我们成功搭建好WordPress网站后,发布的文章对应的URL地址默认是使用“日期和名称型”,即是网站域名跟着的是年月日,最后是文章标题,如http://www.yigujin.com/2024/03/06/免费响应式WordPress博客主题JianYue/ 为了让我们的文章U…...
一款好用的AI工具——边界AICHAT(三)
目录 3.23、文档生成PPT演示3.24、AI文档翻译3.25、AI翻译3.26、论文模式3.27、文章批改3.28、文章纠正3.29、写作助手3.30、文言文翻译3.31、日报周报月报生成器3.32、OCR-DOC办公文档识别3.33、AI真人语音合成3.34、录音音频总结3.35、域方模型市场3.36、模型创建3.37、社区交…...
编程示例: 矩阵的多项式计算以javascript语言为例
编程示例: 矩阵的多项式计算以javascript语言为例 国防工业出版社的《矩阵理论》一书中第一章第8个习题 试计算2*A^8-3*A^5A^4A^2-4I A[[1,0,2],[0,-1,1],[0,1,0]] 代码如下 <html> <head> <title> 矩阵乘法 </title> <script srcset.js ><…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...
