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

leetCode 123.买卖股票的最佳时机 III 动态规划 + 状态压缩

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

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入:prices = [3,3,5,0,0,3,1,4]
输出:6
解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。

示例 1:

输入:prices = [3,3,5,0,0,3,1,4]
输出:6
解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。

示例 3:

输入:prices = [7,6,4,3,1] 
输出:0 
解释:在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4:

输入:prices = [1]
输出:0

>>思路和分析

这道题目相对leetCode 121.买卖股票的最佳时机 和 leetCode 122.买卖股票的最佳时机 II难了不少关键在于至多买卖几次,意味着可以买卖一次,可以买卖两次,也可以不买卖。

>>动规五部曲

1.确定dp数组以及下标的含义

一天 一共有 5 个 状态 ,dp[i][j] 中 i 表示 第 i 天,j 为[0 - 4] 五个状态,dp[i][j]表示第 i 天状态 j所剩最大现金

  • 0.没有操作(其实也可以不设置这个状态)
  • 1.第一次持有股票
  • 2.第一次不持有股票
  • 3.第二次持有股票
  • 4.第二次不持有股票

"持有" : 不代表就是当天"买入"!可能昨天就买入了,今天保持有的状态

2.确定递推公式

3.dp数组初始化

dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
dp[0][3] = -prices[0];
dp[0][4] = 0;

4.确定遍历顺序

递归公式其实已经可以看出,一定是从前向后遍历,因为dp[i],依靠dp[i - 1]的数值

5.举例推导dp数组

以输入[1,2,3,4,5]为例

class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();if (len == 0) return 0;vector<vector<int>> dp(len, vector<int>(5, 0));dp[0][1] = -prices[0];dp[0][3] = -prices[0];for (int i = 1; i < len; i++) {// dp[i][0] = dp[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]);}return dp[len - 1][4];}
};

其实可以不设置,‘0. 没有操作’ 这个状态,因为没有操作,手上的现金自然就是0, 正如在 leetCode 121.买卖股票的最佳时机和 leetCode 122.买卖股票的最佳时机 II也没有设置这一状态是一样的。 

  • 时间复杂度:O(n)
  • 空间复杂度:O(n × 4)

>>状态压缩

摘取自代码随想录代码随想录 (programmercarl.com)

  • dp[1] = max(dp[1], dp[0] - prices[i]); 如果dp[1]取dp[1],即保持买入股票的状态,那么 dp[2] = max(dp[2], dp[1] + prices[i]);中dp[1] + prices[i] 就是今天卖出。
  • 如果dp[1]取dp[0] - prices[i],今天买入股票,那么dp[2] = max(dp[2], dp[1] + prices[i]);中的dp[1] + prices[i]相当于是今天再卖出股票,一买一卖收益为0,对所得现金没有影响。相当于今天买入股票又卖出股票,等于没有操作,保持昨天卖出股票的状态了。
// 状态压缩
class Solution {
public:int maxProfit(vector<int>& prices) { if(prices.size() == 0) return 0;   int len = prices.size();vector<int> dp(5,0);dp[1] = -prices[0];dp[3] = -prices[0];for(int i=1;i<len;i++) {dp[1] = max(dp[1],dp[0] - prices[i]);dp[2] = max(dp[2],dp[1] + prices[i]);dp[3] = max(dp[3],dp[2] - prices[i]);dp[4] = max(dp[4],dp[3] + prices[i]);}return dp[4];}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

参考和推荐文章、视频

代码随想录 (programmercarl.com)

动态规划,股票至多买卖两次,怎么求? | LeetCode:123.买卖股票最佳时机III_哔哩哔哩_bilibili

来自代码随想录课堂截图:

相关文章:

leetCode 123.买卖股票的最佳时机 III 动态规划 + 状态压缩

123. 买卖股票的最佳时机 III - 力扣&#xff08;LeetCode&#xff09; 给定一个数组&#xff0c;它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意&#xff1a;你不能同时参与多笔交易&#xff0…...

JavaScript计算两个时间相差多少个小时的封装函数

js中计算两个时间相差小时数 在JavaScript中&#xff0c;你可以使用Date对象来处理日期和时间。下面是一个函数&#xff0c;它接受两个时间字符串作为参数&#xff0c;并返回两者之间的时间差&#xff08;以小时为单位&#xff09;&#xff1a; function calculateHours(time…...

Qt 画自定义饼图统计的例子

先给出结果图&#xff0c;这个例子是将各种事件分类然后统计的其比例&#xff0c;然后画饼图显示出来 这个是我仿照官方给的例子&#xff0c;让后自己理解后&#xff0c;修改的&#xff0c;要生成饼图&#xff0c;需要QT的 charts 支持&#xff0c;安装QT 没有选择这个的&#…...

【数据结构】链表与LinkedList

作者主页&#xff1a;paper jie 的博客 本文作者&#xff1a;大家好&#xff0c;我是paper jie&#xff0c;感谢你阅读本文&#xff0c;欢迎一建三连哦。 本文录入于《JAVA数据结构》专栏&#xff0c;本专栏是针对于大学生&#xff0c;编程小白精心打造的。笔者用重金(时间和精…...

Flink RoaringBitmap去重

1、RoaringBitmap的依赖 <!-- 去重大哥--> <dependency><groupId>org.roaringbitmap</groupId><artifactId>RoaringBitmap</artifactId><version>0.9.21</version> </dependency> 2、Demo去重 package com.gwm.driver…...

Elasticsearch—(MacOs)

1⃣️环境准备 准备 Java 环境&#xff1a;终端输入 java -version 命令来确认版本是否符合 Elasticsearch 要求下载并解压 Elasticsearch&#xff1a;前往&#xff08;https://www.elastic.co/downloads/elasticsearch&#xff09;选择适合你的 Mac 系统的 Elasticsearch 版本…...

插入排序与希尔排序

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 前言&#xff1a; 这两个排序在思路上有些相似&#xff0c;所以有人觉得插入排序和希尔排序差别不大&#xff0c;事实上&#xff0c;他们之间的差别不小&#xff0c;插入排序只是希尔排序的最后一步。 目录 前言&#xff1a;…...

C# OpenCvSharp 基于直线检测的文本图像倾斜校正

效果 项目 代码 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; using OpenCvSharp;namespace OpenCvSharp_基于直线检测的文…...

“智慧时代的引领者:探索人工智能的无限可能性“

目录 一.背景 二.应用 2.1金融领域 2.2医疗领域 2.3教育领域 三.发展 四.总结: 一.背景 人工智能&#xff08;Artificial Intelligence&#xff0c;简称AI&#xff09;&#xff0c;是指通过计算机程序模拟人类智能的一种技术。它是计算机科学、工程学、语言学、哲学等多…...

PMSM——转子位置估算基于QPLL

文章目录 前言仿真模型观测器速度观测位置观测转矩波形电流波形 前言 今后是电机控制方向的研究生的啦&#xff0c;期待有同行互相交流。 仿真模型 观测器 速度观测 位置观测 转矩波形 电流波形...

Android Studio之Gradle和Gradle插件的区别

解释的很详细 Android Studio之Gradle和Gradle插件的区别...

DataExcel控件读取和保存excel xlsx 格式文件

需要引用NPOI库 https://github.com/dotnetcore/NPOI 调用Read 函数将excel读取到dataexcel控件 调用Save 函数将dataexcel控件文件保存为excel文件 using NPOI.HSSF.UserModel; using NPOI.HSSF.Util; using NPOI.SS.UserModel; using NPOI.SS.Util; using System; using …...

【JavaEE】CAS(Compare And Swap)操作

文章目录 什么是 CASCAS 的应用如何使用 CAS 操作实现自旋锁CAS 的 ABA 问题CAS 相关面试题 什么是 CAS CAS&#xff08;Compare and Swap&#xff09;是一种原子操作&#xff0c;用于在无锁情况下保证数据一致性的问题。它包含三个操作数——内存位置、预期原值及更新值。在执…...

第三章:最新版零基础学习 PYTHON 教程(第三节 - Python 运算符—Python 中的关系运算符)

关系运算符用于比较值。它根据条件返回 True 或 False。这些运算符也称为比较运算符。 操作员描述 句法> 大于:如果左操作数大于右操作数,则为 Truex > y...

【GDB】使用 GDB 自动画红黑树

阅读本文前需要的基础知识 用 python 扩展 gdb python 绘制 graphviz 使用 GDB 画红黑树 前面几节中介绍了 gdb 的 python 扩展&#xff0c;参考 用 python 扩展 gdb 并且 python 有 graphviz 模块&#xff0c;那么可以用 gdb 调用 python&#xff0c;在 python 中使用 grap…...

使用Vue3+elementPlus的Tree组件实现一个拖拽文件夹管理

文章目录 1、前言2、分析3、实现4、踩坑4.1、拖拽辅助线的坑4.2、数据的坑4.3、限制拖拽4.4、样式调整 1、前言 最近在做一个文件夹管理的功能&#xff0c;要实现一个树状的文件夹面板。里面包含两种元素&#xff0c;文件夹以及文件。交互要求如下&#xff1a; 创建、删除&am…...

小谈设计模式(7)—装饰模式

小谈设计模式&#xff08;7&#xff09;—装饰模式 专栏介绍专栏地址专栏介绍 装饰模式装饰模式角色Component&#xff08;抽象组件&#xff09;ConcreteComponent&#xff08;具体组件&#xff09;Decorator&#xff08;抽象装饰器&#xff09;ConcreteDecorator&#xff08;具…...

nginx 多层代理 + k8s ingress 后端服务获取客户真实ip 配置

1.nginx http 七层代理 修改命令空间&#xff1a; namespace: nginx-ingress : configmap&#xff1a;nginx-configuration kubectl get cm nginx-configuration -n ingress-nginx -o yaml添加如上配置 compute-full-forwarded-for: “true” forwarded-for-header: X-Forwa…...

6种最常用的3D点云语义分割AI模型对比

由于增强现实/虚拟现实的发展及其在计算机视觉、自动驾驶和机器人领域的广泛应用&#xff0c;点云学习最近引起了人们的关注。 深度学习已成功用于解决 2D 视觉问题&#xff0c;然而&#xff0c;由于其处理面临独特的挑战&#xff0c;深度学习技术在点云上的使用仍处于起步阶段…...

UG NX二次开发(C#)-获取UI中选择对象的handle值

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 1、前言2、设计一个简单的UI界面3、创建工程项目4、测试结果1、前言 我在哔哩哔哩的视频中看到有人问我如何获取UI选择对象的Handle,本来想把Tag、Taggedobject、Handle三者的关系讲一下,然后看…...

win10,WSL的Ubuntu配python3.7手记

1.装linux 先在windows上安装WSL版本的Ubuntu Windows10系统安装Ubuntu子系统_哔哩哔哩_bilibili &#xff08;WSL2什么的一直没搞清楚&#xff09; 图形界面会出一些问题&#xff0c;注意勾选ccsm出的界面设置 win10安装Ubuntu16.04子系统&#xff0c;并开启桌面环境_win…...

02-Zookeeper实战

上一篇&#xff1a;01-Zookeeper特性与节点数据类型详解 1. zookeeper安装 Step1&#xff1a; 配置JAVA环境&#xff0c;检验环境&#xff1a; java -versionStep2: 下载解压 zookeeper wget https://mirror.bit.edu.cn/apache/zookeeper/zookeeper-3.5.8/apache-zookeepe…...

【C语言深入理解指针(1)】

1.内存和地址 1.1内存 在讲内存和地址之前&#xff0c;我们想有个⽣活中的案例&#xff1a; 假设有⼀栋宿舍楼&#xff0c;把你放在楼⾥&#xff0c;楼上有100个房间&#xff0c;但是房间没有编号&#xff0c;你的⼀个朋友来找你玩&#xff0c;如果想找到你&#xff0c;就得挨…...

模拟实现简单的通讯录

前言&#xff1a;生活中处处都会看到或是用到通讯录&#xff0c;今天我们就通过C语言来简单的模拟实现一下通讯录。 鸡汤&#xff1a;跨越山海&#xff0c;终见曙光&#xff01; 链接:gitee仓库&#xff1a;代码链接 目录 主函数声明部分初始化通讯录实现扩容的函数增加通讯录所…...

rabbitMQ死信队列快速编写记录

文章目录 1.介绍1.1 什么是死信队列1.2 死信队列有什么用 2. 如何编码2.1 架构分析2.2 maven坐标2.3 工具类编写2.4 consumer1编写2.5 consumer2编写2.6 producer编写 3.整合springboot3.1 架构图3.2 maven坐标3.3 构建配置类&#xff0c;创建exchange&#xff0c;queue&#x…...

数位dp,338. 计数问题

338. 计数问题 - AcWing题库 给定两个整数 a 和 b&#xff0c;求 a 和 b 之间的所有数字中 0∼90∼9 的出现次数。 例如&#xff0c;a1024&#xff0c;b1032&#xff0c;则 a 和 b 之间共有 9 个数如下&#xff1a; 1024 1025 1026 1027 1028 1029 1030 1031 1032 其中 0 出…...

如何解决git clone http/https仓库失败(403错误)

本来不打算写这篇文章&#xff0c;但是后来又遇到这个问题忘了之前是怎么解决的了。 一般情况下&#xff0c;个人使用 GitHub 等平台时是使用 SSH 协议的&#xff0c;这样不光方便管理可访问用户&#xff0c;也保证了安全性。但是 GitHub 上仓库的 SSH 地址是要登陆才能看到&a…...

华为云云耀云服务器L实例评测 | 实例评测使用之硬件性能评测:华为云云耀云服务器下的硬件运行评测

华为云云耀云服务器L实例评测 &#xff5c; 实例评测使用之硬件性能评测&#xff1a;华为云云耀云服务器下的硬件运行评测 介绍华为云云耀云服务器 华为云云耀云服务器 &#xff08;目前已经全新升级为 华为云云耀云服务器L实例&#xff09; 华为云云耀云服务器是什么华为云云耀…...

Elasticsearch:使用 Elasticsearch 进行语义搜索

在数字时代&#xff0c;搜索引擎在通过浏览互联网上的大量可用信息来检索数据方面发挥着重要作用。 此方法涉及用户在搜索栏中输入特定术语或短语&#xff0c;期望搜索引擎返回与这些确切关键字匹配的结果。 虽然关键字搜索对于简化信息检索非常有价值&#xff0c;但它也有其局…...

JVM的主要组成及其作用

jvm主要组成部分有: 类加载器、运行时数据区 (内存结构)、执行引擎、本地接口库、垃圾回收机制 Java程序运行的时候&#xff0c;首先会通过类加载器把Java 代码转换成字节码。然后运行时数据区再将字节码加载到内存中&#xff0c;但字节码文件只是JVM 的一套指令集规范&#xf…...

网站如何横屏/石家庄seo网络优化的公司

master主机通过ssh远程连接slaves机子时出现下述错误 解决的方法&#xff1a; 一、删除/root/.ssh/下的kown_hosts文件 二、在master机子上又一次运行scp id_dsa.pub slaves:/root.ssh命令&#xff08;在/root/.ssh文件夹下运行&#xff09; 三、登录slaves机子。进入到root/.s…...

南京建设工程招聘信息网站/洛阳网站建设优化

json和dict的区别 JSON 是一种用于在系统应用之间进行数据传输的文本格式&#xff0c;而 Python 语言中的 dict 是一种内存中数据结构。由于 JSON 内容是文本&#xff0c;因此在其中查找一个 key 的时间复杂度是 O ( n )&#xff0c;而 dict 使用哈希值&#xff0c;时间复杂度…...

如何展示网站操作流程/长尾关键词

编辑&#xff1a;ll ASE65R330-ASEMI高压N沟道MOS管ASE65R330 型号&#xff1a;ASE65R330 品牌&#xff1a;ASEMI 封装&#xff1a;TO-220F 最大漏源电流&#xff1a;12.5A 漏源击穿电压&#xff1a;650V RDS&#xff08;ON&#xff09;Max&#xff1a;0.33mΩ 引脚数量…...

佛山正规网站建设报价/搜索引擎排名优化方案

http://examples.adobe.com/flex3/devnet/networkmonitor/main.html 转载于:https://www.cnblogs.com/taoj/archive/2011/03/31/2001288.html...

朔州网站建设价格/小程序开发软件

本文转载自&#xff1a;http://www.blogjava.net/BlueDavy/archive/2009/04/28/267970.html&#xff0c; 转载请注明 在这篇blog中放置了我收集的一些网站架构相关的PPT和文章&#xff0c;提供给大家下载&#xff0c;如果大家有相关的好的PPT、文章的话&#xff0c;也欢迎推…...

怎样做o2o网站/免费发软文的网站

<?xml:namespace prefix o ns "urn:schemas-microsoft-com:office:office" />移动电子商务的七大机会移动电子商务被很多人看作是一次新的机会。包括泛商务时代的一种潜在机会。不过在具体的发展规划和操作上&#xff0c;很多人还是对此有点摸不着头脑&…...