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

代码随想录 Day41 动态规划09 LeetCode T121 买卖股票的最佳时机 T122 买卖股票的最佳时机II

前言

这两题看起来是不是有点眼熟,其实我们在贪心章节就已经写过了这两道题,当时我们用的是将利润分解,使得我们始终得到的是最大利润

假如第 0 天买入,第 3 天卖出,那么利润为:prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

这样就是每天得到的最大利润 ,下面我也会给出贪心的思路

LeetCode T121 买卖股票的最佳时机

题目链接:121. 买卖股票的最佳时机 - 力扣(LeetCode)

题目思路:

我们还是用动规五部曲来解决问题

1.确定动规数组含义

这里我们定义两种状态,

1.dp[i][0] 表示持有股票的状态

2.dp[i][1]表示不持有股票的状态

所以此时的dp[i][0]和dp[i][1]都是持有股票时的最大钱数和不持有的最大钱数

注:这里的持有和不持有股票不是指当天买入股票,也可能是之前延续下来的一种状态

2.确定递推公式

这里持有股票可能是前面延续下来的一种状态也可能是当时购买股票的一个状态,我们取最大值即可

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

同样下面也是一样我们讨论没有持有股票的最大值

dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i])

3.初始化dp数组

由递推公式可知只要初始化第一个即可

dp[i][0] = -prices[0]

dp[i][1] = 0

4.确定遍历方式

顺序遍历,因为后一个结果的产生取决于前一个结果

5.打印dp数组排错

题目代码:

//贪心
class Solution {public int maxProfit(int[] prices) {// 找到一个最小的购入点int low = Integer.MAX_VALUE;// res不断更新,直到数组循环完毕int res = 0;for(int i = 0; i < prices.length; i++){low = Math.min(prices[i], low);res = Math.max(prices[i] - low, res);}return res;}
}//动规
class Solution {public int maxProfit(int[] prices) {if(prices.length<=1){return 0;}int[][] dp = new int[prices.length][2];dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1;i<prices.length;i++){dp[i][0] = Math.max(dp[i-1][0],-prices[i]);dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);}int result = Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);return result;}
}

LeetCode T122 买卖股票的最佳时机 II 

题目链接:122. 买卖股票的最佳时机 II - 力扣(LeetCode)

题目思路:

这道题和之前的区别就是买卖股票的次数不仅仅是一次了,所以我们需要将持有股票的状态修改一下,其余代码均不变

dp[i][0]  = Math.max(dp[i-1][0],dp[i-1][1]-price[i])这是因为之前只能购买一次,所以不持有股票的状态的钱数一定是0,这里就不一样了,可以购买多次.

题目代码:

//贪心
class Solution {public int maxProfit(int[] prices) {int maxP = 0;for(int i = 0;i<prices.length-1;i++){maxP += Math.max(prices[i+1] - prices[i],0);}return maxP;}
}//动规
class Solution {public int maxProfit(int[] prices) {if(prices.length<=1){return 0;}int[][] dp = new int[prices.length][2];dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1;i<prices.length;i++){dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);}int result = Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);return result;}
}

 

相关文章:

代码随想录 Day41 动态规划09 LeetCode T121 买卖股票的最佳时机 T122 买卖股票的最佳时机II

前言 这两题看起来是不是有点眼熟,其实我们在贪心章节就已经写过了这两道题,当时我们用的是将利润分解,使得我们始终得到的是最大利润 假如第 0 天买入&#xff0c;第 3 天卖出&#xff0c;那么利润为&#xff1a;prices[3] - prices[0]。 相当于(prices[3] - prices[2]) (pri…...

ubuntu18-recvfrom接收不到广播报文异常分析

目录 前言 一、UDP广播接收程序 二、异常原因分析 总结 前言 在ubuntu18.04系统中&#xff0c;编写udp接收程序发现接收不到广播报文&#xff0c;使用抓包工具tcpdump可以抓取到广播报文&#xff0c;在此对该现象分析解析如下文所示。 一、UDP广播接收程序 UDP广播接收程序如…...

漏刻有时百度地图API实战开发(6)多个标注覆盖层级导致不能响应点击的问题

漏刻有时百度地图API实战开发(1)华为手机无法使用addEventListener click 的兼容解决方案漏刻有时百度地图API实战开发(2)文本标签显示和隐藏的切换开关漏刻有时百度地图API实战开发(3)自动获取地图多边形中心点坐标漏刻有时百度地图API实战开发(4)显示指定区域在移动端异常的解…...

使用Net2FTP轻松打造免费的Web文件管理器并公网远程访问

文章目录 1.前言2. Net2FTP网站搭建2.1. Net2FTP下载和安装2.2. Net2FTP网页测试 3. cpolar内网穿透3.1.Cpolar云端设置3.2.Cpolar本地设置 4.公网访问测试5.结语 1.前言 文件传输可以说是互联网最主要的应用之一&#xff0c;特别是智能设备的大面积使用&#xff0c;无论是个人…...

MySQL的表格去重,史上最简便的算法,一看就会

首先&#xff0c;表格my_tab02存在很多重复的数据&#xff1a; #表格的去重 方法一&#xff1a; 详细内容传送门&#xff1a;表格的去重 -- 思路&#xff1a; -- 1.先创建一张临时表 my_tmp,该表的结构和my_tab02一样 -- 2.把my_tmp的记录通过distinct关键字 处理后 把记录复…...

this是指向的哪个全局变量,改变this指向的方法有几种?

在JavaScript中&#xff0c;this关键字指向当前执行上下文中的对象。它的具体指向取决于函数的调用方式。 改变this指向的方法有四种&#xff1a; 1.使用call()方法&#xff1a;call()方法在调用函数时将指定的对象作为参数传递进去&#xff0c;从而改变函数的this指向。用法示…...

电脑msvcp110.dll丢失怎么办,msvcp110.dll缺失的详细修复步骤

在现代科技发展的时代&#xff0c;电脑已经成为我们生活和工作中不可或缺的工具。然而&#xff0c;由于各种原因&#xff0c;电脑可能会出现一些问题&#xff0c;其中之一就是msvcp110.dll文件丢失。这个问题可能会导致一些应用程序无法正常运行&#xff0c;给我们的生活和工作…...

cookie 里面都包含什么属性?

结论先行&#xff1a; Cookie 中除了名称和值外&#xff0c;还有几个比较常见的&#xff0c;例如&#xff1a; Domain 域&#xff1a;指定了 cookie 可以发送到哪些域&#xff0c;只有发送到指定域或其子域的请求才会携带该cookie&#xff1b; Path 路径&#xff1a;指定哪些…...

LinuxMySql

结构化查询语言 DDL&#xff08;数据定义语言&#xff09; 删除数据库drop database DbName; 创建数据库create database DbName; 使用数据库use DbName; 查看创建数据库语句以及字符编码show create database 43th; 修改数据库属性&#xff08;字符编码改为gbk&#xff09;…...

《微服务架构设计模式》之三:微服务架构中的进程通信

概述 交互方式 客户端和服务端交互方式可以从两个维度来分&#xff1a; 维度1&#xff1a;一对一和多对多 一对一&#xff1a;每个客户端请求由一个实例来处理。 一对多&#xff1a;每个客户端请求由多个实例来处理。维度2&#xff1a;同步和异步 同步模式&#xff1a;客户端…...

μC/OS-II---内核:任务调度

目录 内核&#xff1a;调度&#xff08;oc_core.c文件的函数&#xff09;OS_TCB&#xff08;任务控制块&#xff09;初始化任务控制块列表(ucos_ii.h文件的函数)系统调用&#xff0c;主动让渡CPU发生中断&#xff0c;强制当前任务让渡CPU就绪表(ucos_ii.h文件的函数)设置任务进…...

小程序发成绩

在这个数字化快速发展的时代&#xff0c;让学生能够方便快捷地获取自己的成绩已经成为一项基本的需求。那么&#xff0c;如何实现这一目标呢&#xff1f;对于许多老师来说&#xff0c;可能首先想到的是使用各种代码或者Excel来发布成绩查询。今天&#xff0c;我们就来探讨一下这…...

tensorflow内存泄漏或模型只加载不运行

使用tf2模型进行推理的过程中&#xff0c;发现模型的内存占用在逐步增加&#xff0c;甚至会因为OOM被kill掉进程&#xff0c;有时候模型只加载不运行&#xff0c;搜索得到很多五花八门的答案&#xff0c;有些认为是tf2本身的问题&#xff0c;但在使用内存追踪的时候发现&#x…...

npm和yarn的一些命令

文章目录 前言 前言 提示&#xff1a;生命并不短暂&#xff0c;短暂的是人。 --阿多尼斯 yarn config set registry https://registry.npmjs.org --globalnpm install -g cnpm --registryhttps://registry.npm.taobao.org # 切换淘宝源&#xff1a; yarn config set registry…...

Linux开发工具之自动化构建工具-make/Makefile

文章目录 1.make/Makefile的介绍2.简单编写及使用3.ACM时间4.extern的复习5.多文件的编译5.0复习翻译过程5.1多文件的构成5.2手动编译5.3利用Makefile 1.make/Makefile的介绍 make是一个命令 makefile是一个文件[makefile也对] 之前的学习都没有维护项目结构 当有多个.c文件 先…...

UE5蓝图接口使用方法

在内容区右键创建蓝图接口 命名自定义&#xff08;可以用好识别的&#xff09; 双击打开后关闭左边窗口 右键函数 -- 重命名 -- 名称自定义&#xff08;用好记的&#xff09; 点击下边输入后面的 号创建一个变量 点击编译并保存 在一个蓝图类里面 -- 点击类设置 在右侧已实现的…...

vue动态修改css样式

<span :style"{backgroundColor:colorHex}">测试文字</span> <button click"changeColor">更改颜色</button>export default{data(){return{colorHex:"#eeeeee",}},methods:{changeColor(){this.colorHex"#000&quo…...

小解List的使用【C++】

小解List的使用【C】 一. List1.1. 与vector的不同1.2 与vector的使用不同1.2.1 迭代器失效1.2.2. insert1.2.3 erase1.2.4 sort1.3. 其他接口 补充迭代器容器与迭代器的关系迭代器的类型 一. List 学习了STL&#xff0c;也已经到了List的内容 因为List与string以及vector比起…...

自动驾驶高效预训练--降低落地成本的新思路(AD-PT)

自动驾驶高效预训练--降低落地成本的新思路 1. 之前的方法2. 主要工作——面向自动驾驶的点云预训练2.1. 数据准备 出发点&#xff1a;通过预训练的方式&#xff0c;可以利用大量无标注数据进一步提升3D检测 https://arxiv.org/pdf/2306.00612.pdf 1. 之前的方法 1.基于对比学…...

Spring笔记(四)(黑马)(web层解决方案-SpringMVC)

01、Spring MVC 简介 1.1 SpringMVC概述 SpringMVC是一个基于Spring开发的MVC轻量级框架&#xff0c;Spring3.0后发布的组件&#xff0c;SpringMVC和Spring可以无 缝整合&#xff0c;使用DispatcherServlet作为前端控制器&#xff0c;且内部提供了处理器映射器、处理器适配器…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...