当前位置: 首页 > news >正文

买股票的最佳时机 - 2

买卖股票的最佳时机 III

题目描述:

提示:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 105
分析过程:

写动态规划,我们需要考虑一下问题:

  1. 定义状态
  2. 状态转移方程
  3. 初始条件
  4.  遍历顺序

4种状态:

实现先思考一共有几种状态,题目当中说我们一共最多可以买卖两次股票,所以买卖股票一共有四种情况,加上不持有股票,就是以下4种状态:

  1. 第一个持有股票
  2. 第一次卖出股票
  3. 第二次持有股票
  4. 第二次卖出股票

 转移方程:

第一次买入:
        在第 i 天,可以选择在第 i 天买入,或者保持之前的买入状态。
buy1[i] = max(buy1[i-1], -prices[i])
(初始资金为 0,第一次买入后的余额是 -prices[i])
第一次卖出:
        在第 i 天,可以选择在第 i 天卖出,或者保持之前的卖出状态。
sell1[i] = max(sell1[i-1], buy1[i-1] + prices[i])
第二次买入:
        在第 i 天,可以选择在第 i 天买入(用第一次卖出的利润),或者保持之前的买入状态。
buy2[i] = max(buy2[i-1], sell1[i-1] - prices[i])
第二次卖出:
        在第 i 天,可以选择在第 i 天卖出,或者保持之前的卖出状态。
sell2[i] = max(sell2[i-1], buy2[i-1] + prices[i])

 遍历顺序:

通过上面的转移方程,我们可以看出,我们只需要一次遍历,就可以得出我们的dp 

初始化: 

buy1[0] = -prices[0](第一天买入)
sell1[0] = 0(第一天无法卖出)
buy2[0] = -prices[0](允许同一天买入两次?其实此时第一次卖出利润为 0,所以 buy2[0] = 0 - prices[0])
sell2[0] = 0(第一天无法卖出两次)  

 代码:
class Solution {
public:int maxProfit(vector<int>& prices) {int sizes = prices.size();if (!sizes)return 0;vector<vector<int>> dp(sizes, vector<int>(5, 0));dp[0][1] = -prices[0];dp[0][3] = -prices[0];for (int i = 1; i < sizes; i++) {dp[i][1] = max(dp[i - 1][1], -prices[i]);dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2]);dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3]);dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4]);}return dp[sizes - 1][4];}
};

买卖股票的最佳时机 IV

题目描述:

  • 1 <= k <= 100
  • 1 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

从题目当中我们可以看出,这道题多了一个限制,就是我们只能最多买k张股票

分析过程:

最多买2张股票和最多买k张股票的区别是哪里呢,买两张股票是4个状态,那买k张股票不是2k个状态吗,事实上就是这样,我们只需要在里面套上一层for循环就可以了,具体实现的逻辑和上面的一样

代码:
class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();// 边界情况:如果没有股票或者价格为空,直接返回 0if (n == 0) return 0;// 如果k大于等于n/2,意味着可以进行无限次交易,用贪心算法来处理if (k >= n / 2) {int profit = 0;for (int i = 1; i < n; ++i) {if (prices[i] > prices[i - 1]) {profit += prices[i] - prices[i - 1];}}return profit;}// dp[i][j] 表示在第i天进行至多j次交易的最大利润vector<vector<int>> dp(n, vector<int>(k + 1, 0));// 进行每次交易for (int j = 1; j <= k; ++j) {int maxDiff = -prices[0];  // maxDiff 表示买入股票后的最大利润for (int i = 1; i < n; ++i) {dp[i][j] = max(dp[i - 1][j], prices[i] + maxDiff);  // 不交易或者卖出股票maxDiff = max(maxDiff, dp[i][j - 1] - prices[i]);  // 更新最大买入利润}}return dp[n - 1][k];  // 返回最终最大利润}
};

相关文章:

买股票的最佳时机 - 2

买卖股票的最佳时机 III 题目描述&#xff1a; 提示&#xff1a; 1 < prices.length < 1050 < prices[i] < 105 分析过程&#xff1a; 写动态规划&#xff0c;我们需要考虑一下问题&#xff1a; 定义状态状态转移方程初始条件 遍历顺序 4种状态&#xff1a; …...

pytorch入门级项目--基于卷积神经网络的数字识别

文章目录 前言1.数据集的介绍2.数据集的准备3.数据集的加载4.自定义网络模型4.1卷积操作4.2池化操作4.3模型搭建 5.模型训练5.1选择损失函数和优化器5.2训练 6.模型的保存7.模型的验证结语 前言 本篇博客主要针对pytorch入门级的教程&#xff0c;实现了一个基于卷积神经网络&a…...

【Java】求绝对值

目录 引言基础方法Math.abs()适用类型与语法代码示例 特殊数值处理复数绝对值&#xff08;模&#xff09;大整数与高精度小数 底层实现与性能优化位运算技巧&#xff08;仅限int类型&#xff09;最小值溢出与 Math.absExact()解决方案1&#xff1a;手动判断解决方案2&#xff0…...

简单爬虫:东方财富网股票数据爬取(20231230)

目标网站&#xff1a;https://quote.eastmoney.com/center/gridlist.html#hs_a_board 需求&#xff1a;将东方财富网行情中心不同板块的股票数据爬取下来 目标是将各个选项卡的股票数据全部爬取并以excel文件保存在本地。 查看网页源代码发现并没有目标数据&#xff0c;因此需…...

Vue学习教程-14内置指令

文章目录 前言一、v-text指令二、v-html指令三、v-cloak指令四、v-once指令五、v-pre指令六、其他指令 前言 Vue.js 提供了许多内置指令&#xff08;Directives&#xff09;&#xff0c;这些指令用于在模板中添加特殊功能。内置指令以 v- 前缀开始。 v-text : 更新元素的 tex…...

Java——抽象类

在Java中&#xff0c;抽象类&#xff08;Abstract Class&#xff09; 是一种特殊的类&#xff0c;用于定义部分实现的类结构&#xff0c;同时允许子类提供具体的实现。抽象类通常用于定义通用的行为或属性&#xff0c;而将具体的实现细节留给子类。 1. 抽象类的定义 语法&…...

js数据类型检测

JavaScript的数据类型检测 typeof操作符 适用场景 基本数据类型快速判断&#xff1a;适用于快速判断变量是否为number、string、boolean、undefined、function等基本数据类型。比如在函数参数检查中&#xff0c;若要求传入数字参数&#xff0c;可用typeof来初步判断。函数类型…...

Maven+SSM+SpringBoot+Mybatis-Plus

SSM技术栈&#xff1a;spring6、springmvc、mybatis、springboot3、mybatis-plus、druid&#xff1b; 前端: node、npm、vue 快速掌握&#xff1a;全新SSMSpring BootMyBatis-Plus实战精讲...

【爬虫】request库

文章目录 发送请求响应对象响应数据的方式中文乱码问题响应对象的其他属性或方法 发送带参数的请求headers和查询参数 Requests——发送http请求&#xff0c;获取响应数据 首先&#xff0c;请确保&#xff1a; 已安装 RequestsRequests 是最新的 让我们从一些简单的示例开始…...

Docker内存芭蕾:优雅调整容器内存的极限艺术

title: “&#x1f4be; Docker内存芭蕾&#xff1a;优雅调整容器内存的极限艺术” author: “Cjs” date: “2025-2-23” emoji: “&#x1fa70;&#x1f4a5;&#x1f4ca;” 当你的容器变成内存吸血鬼时… &#x1f680; 完美内存编排示范 &#x1f4dc; 智能内存管家脚本…...

云手机如何进行经纬度修改

云手机如何进行经纬度修改 云手机修改经纬度的方法因不同服务商和操作方式有所差异&#xff0c;以下是综合多个来源的常用方法及注意事项&#xff1a; 通过ADB命令注入GPS数据&#xff08;适用于技术用户&#xff09; 1.连接云手机 使用ADB工具连接云手机服务器&#xff0c;…...

力扣-贪心-53 最大子数组和

思路 先把每一个值都加到当前集合中&#xff0c;记录当前的和&#xff0c;直到当前记录和小于0了&#xff0c;再重置改记录&#xff0c;再次尝试累加 代码 class Solution { public:int maxSubArray(vector<int>& nums) {int res INT32_MIN;int curSum 0;for(in…...

【c语言】函数_作业详解

前言&#xff1a; 对应鹏哥专升本c语言&#xff0c;51集 内容&#xff1a; 找出10个数值中的最大值&#xff0c; #include <stdio.h> //求10个整数中的最大值 int main() {//准备10个整数 //int arr[10] {1,2,3,4,13,6,7,8,9,-2};//用于循环10次int i 0;//也可以自…...

超详细:数据库的基本架构

MySQL基础架构 下面这个图是我给出的一个MySQL基础架构图&#xff0c;可以清楚的了解到SQL语句在MySQL的各个模块进行执行过程。 然后MySQL可以分为两个部分&#xff0c;一个是server层&#xff0c;另一个是存储引擎。 server层 Server层涵盖了MySQL的大多数核心服务功能&am…...

PCL 边界体积层次结构(Boundary Volume Hierarchy, BVH)

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 边界体积层次结构(Boundary Volume Hierarchy, BVH) 是一种高效的空间数据结构,广泛应用于计算机图形学、计算机视觉、机器人学、物理仿真等领域。它的核心思想是通过将空间递归地划分为层次化的包围体(通常是轴…...

【微服务】深入解析spring aop原理

目录 一、前言 二、AOP 概述 2.1 什么是AOP 2.2 AOP中的一些概念 2.2.1 aop通知类型 2.3 AOP实现原理 2.3.1 aop中的代理实现 2.4 静态代理与动态代理 2.4.1 静态代理实现 三、 jdk动态代理与cglib代理 3.1 jdk动态代理 3.1.1 jdk动态代理模拟实现 3.2 CGLIB 代理…...

Python爬虫系统搭建教程,从0开始搭建爬虫系统(附安装包)

文章目录 前言一、Python环境搭建1.Python安装2.选择Python开发环境3. 安装必要库 二、基础爬虫构建1. 发送请求获取网页2. 解析网页提取数据 三、使用 Scrapy 框架搭建系统1. 创建 Scrapy 项目2. 生成爬虫3. 编写爬虫代码4. 运行爬虫 四、应对反爬虫机制1. 常见反爬虫手段2. 解…...

linux -对文件描述符的操作dup、fcntl有五种

dup #include<unistd.h> int dup(int oldfd);作用&#xff1a;复制一个新的文件描述符fd 3, int fd1 dup(fd);f指向的是a.txt,fd1指向的也是a.txt从空闲的文件描述符表中找一个最小的作为新的拷贝的文件描述符返回&#xff1a;成功返回新的文件描述符&#xff0c;失败…...

人工智能(AI)的不同维度分类

人工智能(AI)的分类 对机器学习进行分类的方式多种多样&#xff0c;可以根据算法的特性、学习方式、任务类型等不同维度进行分类这些分类都不是互斥的&#xff1a; 1、按数据模态不同:图像&#xff0c;文本&#xff0c;语音&#xff0c;多态等 2、按目标函数不同:判别式模型…...

MySQL的Union和OR查询

这里写目录标题 **1. 创建表和索引****2. 编写 UNION 查询****3. 使用 EXPLAIN 分析查询****4. 分析 EXPLAIN 结果****可能的结果分析**&#xff1a; **5. 验证索引合并****总结****1. UNION 操作的分析****为什么使用临时表&#xff1f;** 2. OR 条件的分析为什么使用索引合并…...

金融业的AI革命——量化交易与智能风控(五)

‌第五章 AI驱动的智能投顾与普惠金融服务体系‌ ‌一、智能投顾技术架构的范式革新‌ ‌1. 技术演进三阶段‌ ‌阶段‌‌核心技术‌‌典型应用‌‌局限性‌规则引擎(2015-2020)决策树、专家系统银行理财风险评估自动化(覆盖率98%)无法应对黑天鹅事件机器学习(2020-2023)…...

机动车授权签字人考试题库及答案

一、单选题 11、 资质认定,是指(  )以上质量技术监督部门依据有关法律法规和标准、技术规范的规定,对检验检测机构的基本条件和技术能力是否符合法定要求实施的评价许可。资质认定包括检验检测机构计量认证。 A、县级 B、市级 C、地区 D、省级 答案&#xff1…...

Kafka系列之:记录一次源头数据库刷数据,造成数据丢失的原因

Kafka系列之:记录一次源头数据库刷数据,造成数据丢失的原因 一、背景二、查看topic日志信息三、结论四、解决方法一、背景 源头数据库在很短的时间内刷了大量的数据,部分数据在hdfs丢失了 理论上debezium数据采集不会丢失,就需要排查数据链路某个节点是否有数据丢失。 数据…...

鸿蒙学习-

鸿蒙数据传值 //* 传值 //* State /**State创建一个响应式的数据&#xff0c;但不是所有的更改都会引起刷新&#xff0c;只有被框架观察到的修改才会被刷新UI* 1. 基本数据类型如 number string boolean等值的变化修改* 2. Object类型&#xff0c;只会观察到第一层的数据变化或…...

【多模态处理篇五】【DeepSeek文档解析:PDF/Word智能处理引擎】

你知道吗?全球每天产生的PDF文档超过10亿份,但90%的上班族还在用复制粘贴的笨办法处理文档!DeepSeek文档解析引擎就像给你的电脑装上了"文档翻译官",能把PDF/Word里的文字、表格、公式甚至排版样式都变成AI能理解的"语言"。举个真实场景:法务小姐姐用…...

WPS中如何批量上下居中对齐word表格中的所有文字

大家好&#xff0c;我是小鱼。 在日常制作Word表格时&#xff0c;经常需要对表格中的内容进行排版。经常会把文字设置成左对齐、居中对齐或者是右对齐&#xff0c;这些对齐方式都比较好设置&#xff0c;有时我们制作的表格需要把文字批量上下居中对齐&#xff0c;那么怎么操作…...

【LLM】增强大模型推理能力的四种范式

note 增强大模型推理能力的四种范式&#xff1a;推理时间扩展、纯强化学习(RL)、SFTRL、蒸馏(distillation) 。其实这几种方法本质就是SFTRL&#xff1a; 低成本做事就直接推理时间扩展稍微肯付出成本就蒸馏SFT&#xff0c;顺便搞点高质量COT SFT数据高级点就先用GRPO等RL学习…...

2025年华为手机解锁BL的方法

注&#xff1a;本文是我用老机型测试的&#xff0c;新机型可能不适用 背景 华为官方已经在2018年关闭了申请BL解锁码的通道&#xff0c;所以华为手机已经无法通过官方获取解锁码。最近翻出了一部家里的老手机华为畅玩5X&#xff0c;想着能不能刷个系统玩玩&#xff0c;但是卡…...

鸿蒙状态管理概述 v2

状态管理v2 概述状态管理之v2ObservedV2 和 Trace状态管理V1版本对嵌套类对象属性变化直接观测的局限性ObservedV2 和 Trace 使用场景 Local状态管理V1版本State装饰器的局限性 Param状态管理V1版本接受外部传入的装饰器的局限性 OnceEventComputedComputed 使用场景 TypePersi…...

阿里云上的网站配置HTTPS

1. 获取SSL证书 创建证书 下载证书 下载 上传 .key .pem 文件 到 阿里云服务器 /etc/nginx/ssl nginx.conf 配置 server { listen 443 ssl; server_name yuming; ssl_certificate /etc/nginx/ssl/*.pem; ssl_certificate_key /etc/nginx/ssl/*.key;...

【部署优化篇十四】【十万字全景拆解:GitHub Actions自动化流水线设计圣经(DeepSeek工业级实践大公开)】

一、从手工作坊到智能工厂:CI/CD的革命之路 想象一下,你所在的公司每天要手工组装1000台手机,每个环节都靠老师傅肉眼检查——这就是没有CI/CD的软件开发现状。GitHub Actions的出现,就像给软件交付装上了特斯拉的超级工厂流水线。 DeepSeek的CI/CD演进史就是一部血泪史:…...

Golang | 每日一练 (3)

&#x1f4a2;欢迎来到张胤尘的技术站 &#x1f4a5;技术如江河&#xff0c;汇聚众志成。代码似星辰&#xff0c;照亮行征程。开源精神长&#xff0c;传承永不忘。携手共前行&#xff0c;未来更辉煌&#x1f4a5; 文章目录 Golang | 每日一练 (3)题目参考答案map 实现原理hmapb…...

Java+SpringBoot+Vue+数据可视化的综合健身管理平台(程序+论文+讲解+安装+调试+售后)

感兴趣的可以先收藏起来&#xff0c;还有大家在毕设选题&#xff0c;项目以及论文编写等相关问题都可以给我留言咨询&#xff0c;我会一一回复&#xff0c;希望帮助更多的人。 系统介绍 在当今社会&#xff0c;随着人们生活水平的不断提高和健康意识的日益增强&#xff0c;健…...

深入解析Textual库:打造现代化的终端用户界面(TUI)

深入解析Textual库&#xff1a;打造现代化的终端用户界面&#xff08;TUI&#xff09; 在终端应用程序的世界里&#xff0c;过去的交互方式通常是简单的命令行输入和文本输出。然而&#xff0c;随着开发者对更高可用性和更友好界面的追求&#xff0c;现代终端用户界面&#xf…...

基于ffmpeg+openGL ES实现的视频编辑工具-opengl相关逻辑(五)

在我们的项目中,OpenGL ES 扮演着至关重要的角色,其主要功能是获取图像数据,经过一系列修饰后将处理结果展示到屏幕上,以此实现各种丰富多样的视觉效果。为了让大家更好地理解后续知识,本文将详细介绍 OpenGL 相关代码。需要注意的是,当前方案将对 OpenGL 的所有操作都集…...

加班限制了进步

今天周六&#xff0c;大家都在加班吗&#xff1f; 做个统计。 最近面试了很多硬件工程师&#xff0c;还没有找到如意的。 这些面试者都很会解决问题&#xff0c;但是不会闭环问题。 EMC不过&#xff0c;加个磁环就过了。为什么加磁环就过了&#xff0c;底层原理不清楚。 改…...

容器化部署tomcat

容器化部署tomcat 需求在docker容器中部署tomcat,并通过外部机器访问tomcat部署的项目 容器化部署要先装好docker容器(docker安装配置) 实现步骤&#xff1a; 拉取tomcat docker pull tomcat用于列出本地Docker主机上存储的所有镜像 docker images在root目录里面创建tomc…...

【HeadFirst系列之HeadFirst设计模式】第7天之命令模式:封装请求,轻松实现解耦!

命令模式&#xff1a;封装请求&#xff0c;轻松实现解耦&#xff01; 大家好&#xff01;今天我们来聊聊设计模式中的命令模式&#xff08;Command Pattern&#xff09;。如果你曾经需要将请求封装成对象&#xff0c;或者希望实现请求的撤销、重做等功能&#xff0c;那么命令模…...

尚硅谷爬虫note009

一、jsonpath 1.安装 pip install jsonpath 2.使用 只能解析本地文件 .json文件 {"store": {"book": [{"category": "reference","author": "Nigel Rees","title": "Sayings of the Century&qu…...

C语言(11)------------->while循环

一、if与while的区别 在C语言中&#xff0c;有三大结构&#xff0c;分别是顺序、选择和循环。在前面的博客文章中&#xff0c;我们解释了if语句的用法&#xff0c;可以参考&#xff1a;C语言&#xff08;7&#xff09;------------&#xff1e;if语句-CSDN博客 从文章中&…...

Unity 全局屏幕点击特效

思路&#xff1a; 1、生成一个点击特效实例&#xff0c;每点击屏幕&#xff0c;就调整特效实例的位置并控制特效的显隐状态即可。 2、需要注意要保证在编辑器开发时或手机上运行时都要显示点击效果。 方案一 &#xff08;推荐&#xff09; using UnityEngine; using UnityEn…...

【数据结构初阶第十二节】设计循环队列

云边有个稻草人-CSDN博客 必须有为成功付出代价的决心&#xff0c;然后想办法付出这个代价。 还有最后一道关于队列的习题&#xff0c;这题有点难&#xff0c;准备好迎接挑战吧&#xff01; 目录 1.【题目】 2.实现循环队列推荐用数组&#xff0c;Why? 3.Q1&#xff1a;如…...

【小白学HTML5】盒模型(一文讲清margin、padding)_第三讲

根据第一讲的内容&#xff0c;我们知道margin是外边距、padding是内边距&#xff0c;那么内外边距该怎么设置呢&#xff1f; 1、margin&#xff1a;外边距 第一种情况&#xff1a;比如设置外边距为上10px、右20px、下30px、左40px 外边距可以分别设置为&#xff1a;margin-t…...

PLC数据采集网关(三格电子)

产品概述 PLC转Modbus网关型号SG-PLC-Private&#xff08;PLC私有协议网关&#xff09;&#xff0c;是三格电子推出的工业级网关&#xff08;以下简称网关&#xff09;&#xff0c;主要用于在不需要对PLC编程的情况下将PLC数据映射到Modbus TCP(映射的方式符合PLC工程师使用习惯…...

基于图扑 HT 可视化实现智慧地下采矿可视化

在前端开发领域&#xff0c;不断涌现的新技术为各行业带来了创新变革的可能。今天&#xff0c;让我们聚焦于图扑软件自研的 HT for Web 产品&#xff0c;看看它如何在前端 2D、3D 渲染方面发力&#xff0c;为智慧地下采矿可视化打造令人惊叹的解决方案&#xff0c;为开发者开启…...

【网络】高级IO(2)

或者在某些情况下&#xff0c;它可能是&#xff1a; typedef unsigned int nfds_t; 前言 由于select函数有下面几个特别明显的缺点&#xff0c;就推演出了改进版本——poll函数 比如select监视的fd是有上限的&#xff0c;我的云服务器内核版本下最大上限是1024个fd&#xf…...

论文解读 | AAAI'25 Cobra:多模态扩展的大型语言模型,以实现高效推理

点击蓝字 关注我们 AI TIME欢迎每一位AI爱好者的加入&#xff01; 点击 阅读原文 观看作者讲解回放&#xff01; 个人信息 作者&#xff1a;赵晗&#xff0c;浙江大学-西湖大学联合培养博士生 内容简介 近年来&#xff0c;在各个领域应用多模态大语言模型&#xff08;MLLMs&…...

区块链共识机制详解

区块链共识机制详解 &#x1f91d; 1. 什么是共识机制&#xff1f; 共识机制是区块链网络中&#xff0c;所有节点就某个状态&#xff08;如交易的有效性&#xff09;达成一致的规则和过程。它解决了在去中心化网络中如何确保数据一致性的问题。 2. 主流共识机制 2.1 工作量证…...

Unity游戏制作中的C#基础(1)界面操作基础

1.脚本有关注意事项 &#xff08;1&#xff09;.进入项目之后&#xff0c;一般创建一个文件夹Scripts用来存放c#脚本&#xff1b; &#xff08;2&#xff09;.在Scripts中创建脚本&#xff0c;双击脚本&#xff0c;进入VS编辑器&#xff0c;有如下结构&#xff1a; start&#…...

python学习笔记,python处理 Excel、Word、PPT 以及邮件自动化办公

文章目录 前言一、环境搭建1. 下载 Python2. 安装 Python 二、处理 Excel 文件&#xff08;openpyxl库&#xff09;三、 处理 Word 文件&#xff08;python-docx库&#xff09;四、 处理 PPT 文件&#xff08;python-pptx库&#xff09;五、 自动发送邮件&#xff08;smtplib和…...