当前位置: 首页 > 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;.代表当前目录…...

OpenClaw安全方案:百川2-13B-4bits量化模型的本地化数据边界

OpenClaw安全方案&#xff1a;百川2-13B-4bits量化模型的本地化数据边界 1. 为什么我们需要本地化数据边界 去年我在帮一家初创公司做财务自动化方案时&#xff0c;遇到一个棘手问题&#xff1a;他们需要分析包含客户银行账号的Excel报表&#xff0c;但公司严格禁止数据上传到…...

FlowState Lab问题排查大全:从依赖错误到显存溢出的解决方案

FlowState Lab问题排查大全&#xff1a;从依赖错误到显存溢出的解决方案 1. 引言 遇到技术问题时的挫败感&#xff0c;相信每个开发者都深有体会。特别是当你满怀期待地准备运行FlowState Lab时&#xff0c;突然蹦出的错误提示就像一盆冷水浇下来。别担心&#xff0c;这篇文章…...

vue3 diff算法中的-双端 Diff + 最长递增子序列 讲解

一句话总结 Vue3 Diff 双端比较&#xff08;快速复用&#xff09; 最长递增子序列&#xff08;最小移动 DOM&#xff09; 目的&#xff1a;在乱序节点中&#xff0c;只移动最少 DOM&#xff0c;实现最高效更新。1. 先搞懂&#xff1a;Vue3 对比 Vue2 差在哪&#xff1f; Vue2…...

城通网盘限速破解终极指南:ctfileGet工具让你免费享受10倍下载速度

城通网盘限速破解终极指南&#xff1a;ctfileGet工具让你免费享受10倍下载速度 【免费下载链接】ctfileGet 获取城通网盘一次性直连地址 项目地址: https://gitcode.com/gh_mirrors/ct/ctfileGet 你是否曾经被城通网盘的限速下载折磨得痛不欲生&#xff1f;面对几十KB/s…...

Comsol锂离子电池热管理模型

Comsol锂离子电池热管理模型 电化学热耦合模型&#xff1a; 风冷换热方形电池 绝热软包电池 石蜡相变换热圆柱电池模型 21700圆柱电池热失控模型&#xff08;附带说明文档&#xff09;一、引言随着电动汽车、储能系统等领域的快速发展&#xff0c;锂离子电池的应用越来越广泛。…...

德意志飞机通过全球协作升级支线航空驾驶舱人机工学

2026年1月15日 —— 作为总部位于德国舍瑙的MAFELEC集团旗下成员&#xff0c;COMTRONIC GmbH近五十年来一直是航空航天领域人机界面&#xff08;HMI&#xff09;解决方案领域值得信赖的供应商。凭借在照明面板、定制键盘及先进光学技术方面的深厚积淀&#xff0c;COMTRONIC长期…...

C++的std--ranges容错系统

C的std::ranges容错系统&#xff1a;现代编程的稳健之道 在C20标准中&#xff0c;std::ranges库的引入彻底改变了算法与容器的交互方式&#xff0c;其容错机制为开发者提供了更安全、更灵活的编程体验。传统迭代器容易因越界或无效操作导致未定义行为&#xff0c;而std::range…...

Go Routine 调度可视化分析

Go Routine调度可视化分析&#xff1a;揭开并发调度的神秘面纱 在Go语言中&#xff0c;Goroutine以其轻量级和高并发的特性成为开发者处理多任务的首选工具。Goroutine的调度机制对许多开发者来说仍然是一个“黑箱”&#xff0c;尤其是在高并发场景下&#xff0c;如何高效管理…...

Kivy中文显示乱码?3步搞定字体配置(附免费字体下载)

Kivy中文显示乱码&#xff1f;3步搞定字体配置&#xff08;附免费字体下载&#xff09; 当你在Kivy应用中看到中文变成一堆问号或方框时&#xff0c;别急着怀疑人生——这通常是字体配置的小问题。作为Python生态中最受欢迎的跨平台GUI框架之一&#xff0c;Kivy默认使用Roboto字…...

Qwen3.5-9B-AWQ-4bit惊艳效果:多对象复杂场景图中主次关系与逻辑推断展示

Qwen3.5-9B-AWQ-4bit惊艳效果&#xff1a;多对象复杂场景图中主次关系与逻辑推断展示 1. 模型能力概览 千问3.5-9B-AWQ-4bit是一款突破性的多模态AI模型&#xff0c;它能够像人类一样"看懂"图片并做出智能分析。不同于传统图像识别工具&#xff0c;这个模型最令人惊…...