当前位置: 首页 > 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;提供统一的布局给其他表单组件&…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...