当前位置: 首页 > 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;每个球队有一定数量的选…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

Python 高效图像帧提取与视频编码:实战指南

Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

Spring Boot + MyBatis 集成支付宝支付流程

Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例&#xff08;电脑网站支付&#xff09; 1. 添加依赖 <!…...