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

数据结构预算法之买股票最好时机动态规划(可买卖多次)

一.题目

二.思路

在动规五部曲中,这个区别主要是体现在递推公式上,其他都和上一篇文章思路是一样的

所以我们重点讲一讲递推公式。

这里重申一下dp数组的含义:

  • dp[i][0] 表示第i天持有股票所得现金。

  • dp[i][1] 表示第i天不持有股票所得最多现金

如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来

  • 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]

  • 第i天买入股票,所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即:dp[i - 1][1] - prices[i]

注意这里和上一题唯一不同的地方,就是推导dp[i][0]的时候,第i天买入股票的情况

在上一题中,因为股票全程只能买卖一次,所以如果买入股票,那么第i天持有股票即dp[i][0]一定就是 -prices[i]。

而本题,因为一只股票可以买卖多次,所以当第i天买入股票的时候,所持有的现金可能有之前买卖过的利润。

那么第i天持有股票即dp[i][0],如果是第i天买入股票,所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格 即:dp[i - 1][1] - prices[i]。

再来看看如果第i天不持有股票即dp[i][1]的情况, 依然可以由两个状态推出来

  • 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:dp[i - 1][1]

  • 第i天卖出股票,所得现金就是按照今天股票价格卖出后所得现金即:prices[i] + dp[i - 1][0]

注意这里和上一题就是一样的逻辑,卖出股票收获利润(可能是负值)天经地义!

C++代码如下:

(注意代码中的注释,标记了和121.买卖股票的最佳时机唯一不同的地方)

class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();vector<vector<int>> dp(len, vector<int>(2, 0));dp[0][0] -= prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}return dp[len - 1][1];}
};
  • 时间复杂度:O(n)

  • 空间复杂度:O(n)

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

这正是因为本题的股票可以买卖多次! 所以买入股票的时候,可能会有之前买卖的利润即:dp[i - 1][1],所以dp[i - 1][1] - prices[i]。

想到到这一点,对这两道题理解的就比较深刻了。

Java语言版本:

// 动态规划
class Solution // 实现1:二维数组存储// 可以将每天持有与否的情况分别用 dp[i][0] 和 dp[i][1] 来进行存储// 时间复杂度:O(n),空间复杂度:O(n)public int maxProfit(int[] prices) {int n = prices.length;int[][] dp = new int[n][2];     // 创建二维数组存储状态dp[0][0] = 0;                   // 初始状态dp[0][1] = -prices[0];for (int i = 1; i < n; ++i) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);    // 第 i 天,没有股票dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);    // 第 i 天,持有股票}return dp[n - 1][0];    // 卖出股票收益高于持有股票收益,因此取[0]}
}

相关文章:

数据结构预算法之买股票最好时机动态规划(可买卖多次)

一.题目二.思路在动规五部曲中&#xff0c;这个区别主要是体现在递推公式上&#xff0c;其他都和上一篇文章思路是一样的。所以我们重点讲一讲递推公式。这里重申一下dp数组的含义&#xff1a;dp[i][0] 表示第i天持有股票所得现金。dp[i][1] 表示第i天不持有股票所得最多现金如…...

华为OD机试真题Java实现【蛇形矩阵】真题+解题思路+代码(20222023)

蛇形矩阵 蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。 例如,当输入5时,应该输出的三角形为: 1 3 6 10 15 2 5 9 14 4 8 13 7 12 11请注意本题含有多组样例输入。 🔥🔥🔥🔥🔥👉👉👉👉👉👉 华为OD机试(Java)真题目录汇总 输入描述:…...

spring Bean的生命周期 IOC

文章目录 1. 基础知识1.1 什么是 IoC ?2. 扩展方法3. 源码入口1. 基础知识 1.1 什么是 IoC ? IoC,控制反转,想必大家都知道,所谓的控制反转,就是把 new 对象的权利交给容器,所有的对象都被容器控制,这就叫所谓的控制反转。 IoC 很好地体现了面向对象设计法则之一 —…...

详解cors跨域

文章目录同源策略cors基本概念cors跨域方式简单请求 simple request非简单请求- 预检请求CORS兼容情况CORS总结同源策略 在以前的一篇博客中有介绍&#xff0c;同源策略是一种安全机制&#xff0c;为了预防某些恶意的行为&#xff0c;限制浏览器从不同源文档和脚本进行交互的行…...

ARM uboot 源码分析7 - uboot的命令体系

一、uboot 命令体系基础 1、使用 uboot 命令 (1) uboot 启动后进入命令行环境下&#xff0c;在此输入命令按回车结束&#xff0c;uboot 会收取这个命令然后解析&#xff0c;然后执行。 2、uboot 命令体系实现代码在哪里 (1) uboot 命令体系的实现代码在 uboot/common/cmd_xx…...

物理服务器与云服务器备份相同吗?

自从云计算兴起以来&#xff0c;服务器备份已经从两阶段的模拟操作演变为由云服务器备份软件执行的复杂的多个过程。但是支持物理服务器和虚拟服务器之间的备份相同吗?主要区别是什么?我们接下来将详细讨论这个问题。 物理服务器与云服务器备份的区别 如果您不熟悉虚拟服务器…...

【Linux】system V共享内存 | 消息队列 | 信号量

​&#x1f320; 作者&#xff1a;阿亮joy. &#x1f386;专栏&#xff1a;《学会Linux》 &#x1f387; 座右铭&#xff1a;每个优秀的人都有一段沉默的时光&#xff0c;那段时光是付出了很多努力却得不到结果的日子&#xff0c;我们把它叫做扎根 目录&#x1f449;system V共…...

FSC的宣传许可 答疑

【FSC的宣传许可 答疑】问&#xff1a;已经采购了认证产品但没有贴FSC标签&#xff0c;是否可以申请宣传许可&#xff1f;答&#xff1a;不可以。要宣传您采用了FSC认证产品的前提条件之一是产品必须是认证且贴有标签的。如果产品没有贴标&#xff0c;则不可申请宣传许可。您的…...

Leetcode力扣秋招刷题路-0100

从0开始的秋招刷题路&#xff0c;记录下所刷每道题的题解&#xff0c;帮助自己回顾总结 100. 相同的树 给你两棵二叉树的根节点 p 和 q &#xff0c;编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同&#xff0c;并且节点具有相同的值&#xff0c;则认为它们是…...

协作对象死锁及其解决方案

协作对象死锁及其解决方案 1.前言 在遇到转账等的需要保证线程安全的情况时&#xff0c;我们通常会使用加锁的方式来保证线程安全&#xff0c;但如果无法合理的使用锁&#xff0c;很可能导致死锁。或者有时我们使用线程池来进行资源的使用&#xff0c;如调用数据库&#xff0…...

良许也成为砖家啦~

大家好&#xff0c;我是良许。 没错&#xff0c;良许成为砖家啦&#xff0c;绝不是口嗨&#xff0c;有图有真相&#xff01; 有人会说&#xff0c;咦&#xff0c;这明明是严宇啊&#xff0c;跟你良许有啥关系&#xff1f; 额。。老读者应该知道良许的来历—— 鄙人真名严宇&a…...

Java中的编程细节

前言&#xff1a; 学习过程中有不少时候遇到一些看似简单&#xff0c;做起来事倍功半的问题。我也想自己是个聪明人&#xff0c;学东西一听就懂&#xff0c;一学就会&#xff0c;马上就能灵活应用。但这种事不能强求&#xff0c;要么自己要看个十遍二十遍最后理清逻辑&#xf…...

Yolov8从pytorch到caffe (一) 环境搭建

Yolov8从pytorch到caffe (一) 环境搭建 1. 创建虚拟环境2. 安装pytorch与v8相关库3. 测试安装是否成功4. 测试推理图像在windows上配置YOLOv8的环境,训练自己的数据集并转换到caffemodel1. 创建虚拟环境 利用conda创建虚拟环境 conda create -n yolo python=3.8 -y 并进入ac…...

2023年CDGA考试-第16章-数据管理组织与角色期望(含答案)

2023年CDGA考试-第16章-数据管理组织与角色期望(含答案) 单选题 1.在定义任何新组织或尝试改进现有组织之前了解当前组织的哪些方面非常重要? A.企业文化、运营模式和人员 B.业务战略、技术战略、数据战略 C.工具、方法和流程 D.事业环境因素、组织过程资产,行动路线图 …...

Stream——集合数据按照某一字段排序

文章目录前言假设业务场景排序前的准备正序排序1、数据集合的判空 Optional.isPresent()2、使用sort排序3、将排序后的数据流转换为list你以为这样就完了&#xff1f;倒序排序前言 之前&#xff0c;针对Stream链式编程中的几个方法做了大致的说明。详情可以参考&#xff1a; J…...

ubuntu:20.04编译arrow

1)拉取代码 git clone https://github.com/apache/arrow.git 2&#xff09;切换分支 git checkout apache-arrow-11.0.0 3)拉入测试数据并设置环境变量 pushd arrow git submodule update --init export PARQUET_TEST_DATA"${PWD}/cpp/submodules/parquet-testing/da…...

2023如果纯做业务测试的话,在测试行业有出路吗?

直接抛出我的结论&#xff1a;手工做业务类测试&#xff0c;没有前途。 个人建议赶紧从业务测试跳出来&#xff0c;立即学习代码&#xff0c;走自动化测试方向。目前趋势&#xff0c;业务测试需要用自动化做。 为了让大家能够信服我的观点&#xff0c;本文将从以下方面进行阐…...

golang grpc ssl

无CA场景 在不考虑CA的场景下呢&#xff0c;client有client.key和client.crt&#xff0c;server有server.key和server.crt&#xff0c;生成方式可以如下&#xff1a; $ openssl genrsa -out server.key 2048 $ openssl req -new -x509 -days 3650 \-subj "/CGB/LChina/Og…...

华为服务器驱动下载及安装

1.服务器技术支持网站 https://support.xfusion.com/support/#/zh/home 2.选择软件下载 3.选择服务器型号 4.选择驱动 5.根据需求选择驱动 例如红帽7.4系统 6.安装驱动 自动安装驱动步骤&#xff1a; 1)使用BMC虚拟光驱挂载onboard_driver_xxx.iso: 2)mount /dev/sr0 /mnt …...

【Shell】常用命令合集

常用命令: 文件和目录: cd /home 进入 ‘/home’ 目录 cd … 返回上一级目录 cd …/… 返回上两级目录 cd - 返回上次所在目录 cp file1 file2 将file1复制为file2 cp -a dir1 dir2 复制一个目录 cp -a /tmp/dir1 . 复制一个目录到当前工作目录&#xff08;.代表当前目录…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

Java后端检查空条件查询

通过抛出运行异常&#xff1a;throw new RuntimeException("请输入查询条件&#xff01;");BranchWarehouseServiceImpl.java // 查询试剂交易&#xff08;入库/出库&#xff09;记录Overridepublic List<BranchWarehouseTransactions> queryForReagent(Branch…...

rm视觉学习1-自瞄部分

首先先感谢中南大学的开源&#xff0c;提供了很全面的思路&#xff0c;减少了很多基础性的开发研究 我看的阅读的是中南大学FYT战队开源视觉代码 链接&#xff1a;https://github.com/CSU-FYT-Vision/FYT2024_vision.git 1.框架&#xff1a; 代码框架结构&#xff1a;readme有…...

C#最佳实践:为何优先使用as或is而非强制转换

C#最佳实践&#xff1a;为何优先使用as或is而非强制转换 在 C# 的编程世界里&#xff0c;类型转换是我们经常会遇到的操作。就像在现实生活中&#xff0c;我们可能需要把不同形状的物品重新整理归类一样&#xff0c;在代码里&#xff0c;我们也常常需要将一个数据类型转换为另…...