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

代码随想录算法训练营Day46|动态规划:121.买卖股票的最佳时机I、122.买卖股票的最佳时机II、123.买卖股票的最佳时机III

买卖股票的最佳时机I

121. 买卖股票的最佳时机 - 力扣(LeetCode)

之前用贪心算法做过相同的题,这次考虑使用动态规划来完成。

dp[i]表示前i天的最大利润

我们已知每一天的价格price[i],则dp[i]为每一天的价格price[i]减去当初购买的价格buyprice与dp1[i-1]的较大值。 dp[i] = max(dp[i-1],price[i]-buyprice)

dp[0]表示收益为0

从前往后递推,注意要更新buyprice的价格为当前遍历过的数据中最小的值。

最后返回dp[price.size()-1]。

其实和贪心差不多,或者说贪心是这里动态规划的变体?

class Solution {
public:int maxProfit(vector<int>& prices) {// 如果价格数组为空,则没有利润,返回0if(prices.size()==0)return 0;// 初始化买入价格为第一天的价格int buyprice = prices[0];// 创建一个动态数组dp,用于存储到第i天为止的最大利润// 初始化dp[0]为0,因为第一天买入卖出没有利润vector<int>dp(prices.size(),0);dp[0]  = 0;// 遍历价格数组,从第二天开始for(int i = 1;i < prices.size();i++){// 更新买入价格为当前价格和之前最低价格中的较小值buyprice = min(buyprice,prices[i]);// 计算如果在今天卖出股票能获得的最大利润// 即取当前价格减去最低买入价格和前一天的最大利润中的较大值dp[i] = max(dp[i-1],prices[i]-buyprice);}// 返回最后一天的最大利润,即整个期间的最大利润return dp[prices.size()-1];}
};

算法的时间复杂度为O(n),遍历一次数组,空间复杂度同样为O(n),需要维护一个dp数组。

买卖股票的最佳时机II

122. 买卖股票的最佳时机 II - 力扣(LeetCode)

由于不能同时参与多笔交易,则每天结束,只会存在拥有一支股票和无股票两种情况,由次,创建一个二维的dp数组(n*2的大小),其中dp[i][0]表示当天结束时,手头没有股票的最大利润,dp[i][1]表示当天结束时手头有股票的利润。

考虑推导,手头没有股票有两种情况,一是前一天就没有股票且今天没买,二是前一天有股票,但今天卖了,则dp[i][0] = max(dp[i-1][0],dp[i-1][1]+price[i]),手头有股票同样有两种情况,一是前一天没有股票但今天买了,二是昨天的股票没卖。

dp[i][1] = max(dp[i-1][0] - price[i],dp[i-1][1])

考虑到这样的情况,需对dp[0][0]和dp[1][0]初始化,dp[0][0] = 0,dp[0][1]=-price[0]

从前往后遍历(本质上还是从天来推导)

最后一天由于dp[i][0]一定大于dp[i][1],返回dp[i][0]即可。

class Solution {
public:int maxProfit(vector<int>& prices) {// 创建一个二维数组dp,行数为prices的大小,列数为2// dp[i][0]代表第i天结束时,不持有股票的最大利润// dp[i][1]代表第i天结束时,持有股票的最大利润vector<vector<int>> dp(prices.size(), vector<int>(2, 0));// 初始化dp数组的第一行// 第一天不持有股票的最大利润为0dp[0][0] = 0; // 第一天持有股票的最大利润为负的第一天价格(即买入股票)dp[0][1] = -prices[0];// 遍历价格数组,从第二天开始更新dp数组for(int i = 1; i < prices.size(); i++){// 更新第i天不持有股票的最大利润// 可以是前一天就不持有股票,或者前一天持有股票但今天卖出dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);// 更新第i天持有股票的最大利润// 可以是前一天就持有股票,或者前一天不持有股票但今天买入dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1]);}// 返回最后一天不持有股票的最大利润return dp[prices.size()-1][0];}
};

算法的时间复杂度为O(n),空间复杂度为O(n)。

买卖股票的最佳时机III

123. 买卖股票的最佳时机 III - 力扣(LeetCode)

每天结束后,我们手中持有的股票有以下五种情况。

  1. 无操作
  2. 第一次买操作
  3. 完成一笔操作
  4. 第二次买操作
  5. 完全两笔交易

由此,我们根据买卖股票的最佳时机II相似的方式,来完成本题。

  • dp[i][0]:没有进行任何交易时的利润。

  • dp[i][1]:进行了第一次买入后的利润。

  • dp[i][2]:完成了第一次卖出后的利润。

  • dp[i][3]:进行了第二次买入后的利润。

  • dp[i][4]:完成了第二次卖出后的利润。

dp[i][0]始终为0,这里我们将dp[i][0] = do[i-1][0];

dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i])

dp[i][2] = max(dp[i-1][2],dp[i-1][1] + prices[i])

dp[i][3] = max(dp[i-1][3],dp[i-1][2] - prices[i])

dp[i][4] = max(dp[i-1][4],dp[i-1][3] + prices[i])

从前向后遍历

返回dp[prices.size()-1][4]

class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.size() == 0) return 0; // 如果没有价格数据,则利润为0vector<vector<int>> dp(prices.size(), vector<int>(5, 0)); // 初始化dp数组// 初始化第一天的状态dp[0][1] = -prices[0]; // 第一天买入股票后的利润dp[0][3] = -prices[0]; // 假设k>=2,第一天买入第二次股票后的利润for (int i = 1; i < prices.size(); i++) { // 遍历价格数组// 更新第i天不进行任何交易的最大利润,这个值始终为0,因为不交易不会有利润变化dp[i][0] = dp[i - 1][0];// 更新第i天进行第一次买入后的最大利润dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);// 更新第i天完成第一次卖出后的最大利润dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);// 更新第i天进行第二次买入后的最大利润dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);// 更新第i天完成第二次卖出后的最大利润dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);}// 返回最后一天完成所有交易后的最大利润return dp[prices.size() - 1][4];}
};

算法的时间复杂度为O(n),空间复杂度为O(n)。

相关文章:

代码随想录算法训练营Day46|动态规划:121.买卖股票的最佳时机I、122.买卖股票的最佳时机II、123.买卖股票的最佳时机III

买卖股票的最佳时机I 121. 买卖股票的最佳时机 - 力扣&#xff08;LeetCode&#xff09; 之前用贪心算法做过相同的题&#xff0c;这次考虑使用动态规划来完成。 dp[i]表示前i天的最大利润 我们已知每一天的价格price[i]&#xff0c;则dp[i]为每一天的价格price[i]减去当初…...

hive on spark 记录

环境&#xff1a; hadoop 2.7.2 spark-without-hadoop 2.4.6 hive 2.3.4 hive-site.xml <property><name>hive.execution.engine</name><value>spark</value> </property> <property><name>spark.yarn.jars</name>&l…...

【计算机网络体系结构】计算机网络体系结构实验-DHCP实验

服务器ip地址 2. 服务器地址池 3. 客户端ip 4. ping Ipconfig...

攻防世界-pdf

方法一&#xff1a;打开是pdf格式的文件&#xff0c;里面有一张图&#xff0c;题目提示图下面什么都没有&#xff1f;emmm用chrom打开pdf——ctrlf搜索flag&#xff0c;里面是有东西的&#xff0c;ctrla复制就可以了。 方法二&#xff1a;题目提示图下面什么都没有&#xff0c;…...

关于后端幂等性问题分析与总结

后端幂等性&#xff08;Idempotency&#xff09;是指对系统执行一次操作或多次执行相同的操作&#xff0c;其结果始终如一。在分布式系统和API设计中&#xff0c;这是一个关键概念&#xff0c;因为它能保证用户无论请求被路由到哪个节点&#xff0c;多次执行相同的请求都不会导…...

2024广东省职业技能大赛云计算赛项实战——容器云平台搭建

容器云平台搭建 前言 容器镜像使用的是斗学培训平台提供的镜像包&#xff0c;这东西网上都没有&#xff0c;一堆人要&#xff0c;我是靠自己想的方法获取到了&#xff0c;也不敢给。你们可以通过在这个网站申请环境进行操作https://ncc.douxuedu.com/ 虚拟机使用的是自行创建…...

手持弹幕LED滚动字幕屏夜店表白手灯接机微信抖音小程序开源版开发

手持弹幕LED滚动字幕屏夜店表白手灯接机微信抖音小程序开源版开发 专业版 插件版 手持弹幕小程序通常提供多种功能&#xff0c;以便用户在不同的场合如夜店、表白、接机等使用。以下是一些常见的功能列表&#xff1a; 文本输入&#xff1a; 输入要显示的文字内容&#xff0c;…...

红队内网攻防渗透:内网渗透之内网对抗:代理通讯篇无外网或不可达SockS全协议规则配置C2正反向上线解决方案

红队内网攻防渗透 1. 内网代理通讯1.1 网络不可达实战环境模拟1.1.1 CS代理技术-SockS配置-网络不可达-通讯解决1.1.1.1 反向shell上线入口点主机1.1.1.2 入口点CS搭建sokcs4代理1.1.1.3 本地使用Proxifier访问代理1.1.1 CS代理技术-正反向监听-网络不可达-C2上线1.1.1.4 正向s…...

PHP学习总结-入门篇

PHP简介 PHP (Hypertext Preprocessor)&#xff0c;即“超文本预处理器”。PHP 是一种创建动态交互性站点的强有力的服务器端脚本语言。PHP语法吸收了C语言、Java和Perl的特点&#xff0c;便于学习。PHP 是开源免费的&#xff0c;主要适用于Web开发领域&#xff0c;使用广泛。…...

IDEA Plugins中搜索不到插件解决办法

IDEA中搜不到插件有三种解决方案&#xff1a; 设置HTTP选项&#xff0c;可以通过File->Settings->Plugins->⚙->HTTP Proxy Settings进行设置 具体可参考这篇博文&#xff1a;IDEA Plugins中搜索不到插件解决办法本地安装&#xff0c;ile->Settings->Plugin…...

SpringBootWeb 篇-入门了解 Vue 前端工程的创建与基本使用

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 基于脚手架创建前端工程 1.1 基于 Vue 开发前端项目的环境要求 1.2 前端工程创建的方式 1.2.1 基于命令的方式来创建前端工程 1.2.2 使用图形化来创建前端工程 1.…...

折线统计图 初级

此为折线统计图的初级题目。 本次的题目较难&#xff0c;菜鸡请退出。 4. 下图显示了甲、乙两台电脑的价格以及它们已使用的年数&#xff0c;从图中可以知道( )。 15. 妈妈去菜市场买菜&#xff0c;走到半路遇到一位熟人聊了一会儿&#xff0c;突然发现忘了带钱。于是马上回…...

最新下载:XmanagerXShell【软件附加安装教程】

​相信大家都认同支持IPv6&#xff1a;最近越来越多的公司和国家都采用了IPv6&#xff0c;Xmanager的最新版本v5也加入支持这个功能&#xff0c;无论你是同时使用IPv4和IPv6网络或者完全的IPv6网络&#xff0c;Xmanager 5都可完全满足你的要求&#xff0c;使用MIT Kerberos认证…...

Coursera耶鲁大学金融课程:Financial Markets 笔记Week 02

Financial Markets 本文是学习 https://www.coursera.org/learn/financial-markets-global这门课的学习笔记 这门课的老师是耶鲁大学的Robert Shiller https://en.wikipedia.org/wiki/Robert_J._Shiller Robert James Shiller (born March 29, 1946)[4] is an American econom…...

读书笔记:《生死疲劳》

《生死疲劳》. 莫言 生死疲劳》是莫言最重要的代表作之一。他用动物的视角、俏皮的语言和鬼才的叙事手法&#xff0c;使这本讲述沉重故事的书中处处充满惊喜&#xff1b;用幽默、戏谑的方式化解现实的痛苦&#xff0c;让人在痛苦时依旧能笑出声来&#xff0c;给人以力量。…...

C++面向对象三大特性--多态

C面向对象三大特性–多态 文章目录 C面向对象三大特性--多态1.虚函数&#xff08;Virtual Function&#xff09;2.纯虚函数&#xff08;Pure Virtual Function&#xff09;和抽象类&#xff08;Abstract Class&#xff09;3.重写&#xff08;Override&#xff09;4.动态绑定&am…...

啥移动硬盘格式能更好兼容Windows和Mac系统 NTFS格式苹果电脑不能修改 paragon ntfs for mac激活码

对于同时使用Windows和Mac操作系统的用户而言&#xff0c;选择一个既能确保数据互通又能满足大容量存储需求的移动硬盘格式尤为重要。下面我们来看看啥移动硬盘格式能更好兼容Windows和Mac系统&#xff0c;NTFS格式苹果电脑不能修改的相关内容。 一、啥移动硬盘格式能更好兼容…...

【面试】i++与++i的区别

目录 1. 情况11.1 i1.2 i 2. 情况23. 情况34. 情况4 1. 情况1 1.1 i 1.代码块 public void test(){int i 10;i;System.out.println(i);}2.字节码 0 bipush 102 istore_13 iinc 1 by 16 getstatic #2 <java/lang/System.out : Ljava/io/PrintStream;>9 iload_1 10 inv…...

使用 devtool 本地调试 nodejs

安装 # 全局安装 $ npm install devtool -g # 或临时安装 $ npx devtool [file] [opts]用法 Usage:devtool [入口文件] [opts]Options:--watch, -w enable file watching (for development) # 动态检测文件变更&#xff0c;不用每次手动重启--quit, -q …...

element-plus 表单组件 之element-form

elment-plus的表单组件的标签有el-form,el-form-item。 单个el-form标签内包裹若干个el-form-item,el-form-item包裹具体的表单组件&#xff0c;如输入框组件&#xff0c;多选组件&#xff0c;日期组件等。 el-form组件的主要作用是&#xff1a;提供统一的布局给其他表单组件&…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...