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

代码随想录算法训练营第四十九天| 121. 买卖股票的最佳时机、122.买卖股票的最佳时机II

文章目录

      • 121. 买卖股票的最佳时机
      • 122.买卖股票的最佳时机II

121. 买卖股票的最佳时机

为什么定义dp数组为二维数组
dp数组定义,dp(i)[0] 表示第i天持有股票所得最多现金,dp(i)[1]表示第i天不持有股票的状态(未必当前卖出)
这样定义可以表示所有状态,否则dp[i]表示买入,那还要定义第i天卖出,和剩下两种状态持有和不持有

  • 题目链接:代码随想录

  • 解题思路:
    ①dp数组,dp(i)[0]表示第i天持有股票的最大现金,dp(i)[1]表示第i天不持有股票的最大现金
    ②递推公式

    ​ 1.第i天持有股票,可能第i天没买,最大现金为前一天持有股票的最大状态;有可能第i天买了,而且一定是第一次买,所以为-price[i]
    ​ 2.第i天不持有股票**,可能是第i - 1天就不持有状态顺延;也有可能是正好这一天卖出股票,所以总现金为前一天持有状态 + 今天卖出状态
    ​ ③初始化:
    ​ 因为要用到i - 1状态,所以要有第0个元素
    ​ ④遍历顺序:从前向后,因为后状态依赖前状态

  • 推导过程

    image-20230502200150588
public int maxProfit(int[] prices) {//dp数组//dp[i][0]表示第i天持有股票的最大现金,dp[i][0]表示第i天不持有股票的最大现金int[][] dp = new int[prices.length][2];//初始化//因为i - 1所以,要有第0个元素dp[0][0] = -prices[0];dp[0][1] = 0;//遍历for (int i = 1; i < prices.length; i++) {//第i天持有股票,可能第i天没买,最大现金为前一天持有股票的最大状态;有可能第i天买了,而且一定是第一次买,所以为-price[i]dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);//第i天不持有股票,可能是第i - 1天就不持有状态顺延;也有可能是正好这一天卖出股票,所以总现金为前一天持有状态 + 今天卖出状态dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] + prices[i]);}//一定是第i天不持有股票现金多,不持有一定现金更多return dp[prices.length - 1][1];
}

122.买卖股票的最佳时机II

本题和上一题唯一的区别在于:
当第i天持有并且第i天买入的情况,不再是单纯的-了,而是要算上前一天不持有的状态,因为可以买卖多次
而第i天不持有的情况和之前状态一样

  • 题目链接:代码随想录
public int maxProfit(int[] prices) {//dp数组int[][] dp = new int[prices.length][2];//初始化dp[0][0] = -prices[0];dp[0][1] = 0;//遍历for (int i = 1; i < prices.length; i++) {//第i天持有股票,当第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[prices.length - 1][1];
}

相关文章:

代码随想录算法训练营第四十九天| 121. 买卖股票的最佳时机、122.买卖股票的最佳时机II

文章目录 121. 买卖股票的最佳时机122.买卖股票的最佳时机II 121. 买卖股票的最佳时机 为什么定义dp数组为二维数组&#xff1f; dp数组定义&#xff0c;dp(i)[0] 表示第i天持有股票所得最多现金&#xff0c;dp(i)[1]表示第i天不持有股票的状态&#xff08;未必当前卖出&#x…...

零基础如何学习挖漏洞?看这篇就够了【网络安全】

前言 有不少阅读过我文章的伙伴都知道&#xff0c;我从事网络安全行业已经好几年&#xff0c;积累了丰富的经验和技能。在这段时间里&#xff0c;我参与了多个实际项目的规划和实施&#xff0c;成功防范了各种网络攻击和漏洞利用&#xff0c;提高了安全防护水平。 也有很多小…...

Twitter 推荐算法底有多牛? 已斩获11.7K star

点击上方“Github中文社区”&#xff0c;关注 看Github&#xff0c;每天提升第070期分享 &#xff0c;作者&#xff1a;Huber | Github中文社区 大家好&#xff0c;我是Huber。 在美国当地时间 3 月 31 日&#xff0c;马斯克履行当初的诺言&#xff0c;他宣布了 Twitter 算法的…...

看过这篇文章,读懂数据分析

一、为什么需要数据分析 数据分析的重要性不言而喻&#xff0c;没有数据&#xff0c;就是感性。数据不会被观点打败&#xff0c;数据只能被数据打败。我们现在妥妥地已经进入了数据时代。 量化IT投资成效&#xff0c;以数据驱动决策 站在公司或者决策者角度&#xff0c;数据最…...

[计算机图形学]光场,颜色与感知(前瞻预习/复习回顾)

一、Light Field / Lumigraph—光场 1.我们看到的是什么 我们的眼睛能够把3D世界转换为2D的成像信号被我们感知&#xff0c;如上面第一幅图&#xff0c;这就是我们看到整个世界的过程&#xff0c;那么如果我们把之前记录的光的信息都完美的放在一个幕布上&#xff0c;那么我们…...

L4公司进军辅助驾驶,放话无图也能跑遍中国

作者 | Amy 编辑 | 德新 高阶智能驾驶走向规模量产&#xff0c;高精地图成为关键的门槛之一。今年&#xff0c;多家车企和智驾公司都喊出「不依赖高精地图&#xff0c;快速大规模落地」的口号。 华为、小鹏、元戎以及毫末等&#xff0c;可能是最快在国内量产 无高精图智…...

【Java笔试强训 17】

&#x1f389;&#x1f389;&#x1f389;点进来你就是我的人了博主主页&#xff1a;&#x1f648;&#x1f648;&#x1f648;戳一戳,欢迎大佬指点! 欢迎志同道合的朋友一起加油喔&#x1f93a;&#x1f93a;&#x1f93a; 目录 一、选择题 二、编程题 &#x1f525;杨辉三角…...

【IPv6】基本概念及字段

IPV4知识点&#xff1a; 字段值 IPv4字段共 字段值解释Version版本版本字段&#xff0c;可以区分V4和V6版本&#xff0c;V4是0100&#xff0c;V6是0110&#xff0c;需要注意的是V4和V6头部除了版本字段位置相同外&#xff0c;其他都是不一样的&#xff0c;因此两个协议不能直…...

数据库中的 Schema 变更实现

线上沙龙-技术流第 30 期营业啦 05月09日&#xff08;周二&#xff09;19:30 KaiwuDB - B站直播间 传统数据库操作 Schema 变更时&#xff0c;第一步便是锁表&#xff0c;需持续到 Schema 变更操作完成。这样的做法虽然实现简单&#xff0c;无需考虑事务并发带来的影响&#…...

【C++ 学习 ②】- 类和对象(上)

目录 一、 面向对象的基本理念 1.1 - 什么是对象&#xff1f; 1.2 - 类和对象 1.3 - 面向对象的五条原则 1.4 - 面向过程 vs 面向对象 二、C 中的结构体 三、类的定义 3.1 - 类的两种定义方式 3.2 - 成员变量的命名规范 四、类的访问限定符和封装 4.1 - 访问限定符 …...

最好的物联网教程:软硬结合——从零打造物联网

在大学里不同专业有着不同的追求&#xff1a;机械类与强电类专业学生追求的是 “机电合一” &#xff0c;既懂机械又懂电气&#xff0c;整个电气机械自动化便能打通。弱电类专业学生追求的是 “软硬结合” &#xff0c;既懂硬件又懂软件&#xff0c;整个电子产品便能打通。我作…...

猫狗训练集训练报错:Failed to find data adapter that can handle input

这里写自定义目录标题 Jupyter Notebook6.5.4 tensorflow 2.12.0 pillow 9.5.0 numpy 1.23.5 keras 2.12.0 报错详细内容&#xff1a; ValueError: Failed to find data adapter that can handle input: (<class ‘tuple’> containing values of types {“<class ‘k…...

中国网络安全人才需求

如果你是一个想要入门网络安全行业的小白、如果你是网络安全专业在读的大学生、如果你是正在找工作的新手&#xff0c;那么这篇文章你一定要仔细看。毕竟知己知彼百战百胜&#xff0c;知道行业的人才需求才能更好得发挥自己的优势。 当你打开BOSS直聘、拉钩等招聘网站&#xf…...

设计模式之组合模式

目录 1、组合模式的定义 2、组合模式例子 3、组合模式实现 3.1 组合模式的结构 3.2 组合模式的分类 3.3 组合模式代码实现&#xff08;透明组合模式&#xff09; 4、组合模式的优点 5、组合模式使用场景 1、组合模式的定义 组合模式又名部分整体模式&#xff0c;是用于把…...

计算机基础书籍

一操作系统 二常见问题总结 1.操作系统的特征&#xff1f; 并发、共享、虚拟、异步性 2.进程阻塞与唤醒的条件 等待 I/O 操作完成请求系统资源失败等待信号量或事件等待子进程结束被高优先级进程抢占 3.如何避免死锁&#xff1f; 1、避免资源竞争 2、破坏循环等待条件 3、优…...

保龄球游戏的获胜者、找出叠涂元素----2023/4/30

保龄球游戏的获胜者----2023/4/30 给你两个下标从 0 开始的整数数组 player1 和 player2 &#xff0c;分别表示玩家 1 和玩家 2 击中的瓶数。 保龄球比赛由 n 轮组成&#xff0c;每轮的瓶数恰好为 10 。 假设玩家在第 i 轮中击中 xi 个瓶子。玩家第 i 轮的价值为&#xff1a; …...

jQuery事件

1. jQuery事件注册 单个事件注册 语法&#xff1a; element.事件(function(){}) eg&#xff1a;$(“div”).click(function(){ 事件处理程序 }) 其他事件和原生基本一致。比如mouseover、mouseout、blur、focus、change、keydown、keyup、resize、scroll 等 <!DOCTYP…...

初识SpringCloud

一、软件架构演进 单体架构 垂直架构 分布式架构 SOA架构 微服务架构 二、微服务架构 2.1 微服务理念 "微服务”一词源 于 Martin Fowler的名为 Microservices的博文,可以在他的官方博客上找到http://martinfowler.com/articles/microservices.html微服务是系统架构上…...

安装java配置

目录 安装JDK ​编辑 环境变量配置 3、检验环境变量配置 二、安装tomcat 验证Tomcat配置是否成功 三、安装Mysql 一、安装 二、卸载 四、安装Maven 安装JDK 点击更改将C直接给为F即可。 点击确定后进行安装&#xff0c;安装完以后会提示安装JRE; 检测是否已经安装JDK的…...

KBO的选秀会有哪些规定和流程`棒球7号位

KBO&#xff08;韩国职业棒球联盟&#xff09;的选秀会有以下规定和流程&#xff1a; 1. 选秀对象&#xff1a;KBO的选秀会主要面向年满18岁及以上的高中和大学生&#xff0c;以及海外球员和自由球员。KBO的球队可以在选秀会中挑选所需的球员&#xff0c;每个球队有一定数量的选…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...

【WebSocket】SpringBoot项目中使用WebSocket

1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖&#xff0c;添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...

前端调试HTTP状态码

1xx&#xff08;信息类状态码&#xff09; 这类状态码表示临时响应&#xff0c;需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分&#xff0c;客户端应继续发送剩余部分。 2xx&#xff08;成功类状态码&#xff09; 表示请求已成功被服务器接收、理解并处…...

webpack面试题

面试题&#xff1a;webpack介绍和简单使用 一、webpack&#xff08;模块化打包工具&#xff09;1. webpack是把项目当作一个整体&#xff0c;通过给定的一个主文件&#xff0c;webpack将从这个主文件开始找到你项目当中的所有依赖文件&#xff0c;使用loaders来处理它们&#x…...