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

day-49 代码随想录算法训练营(19) 动态规划 part 10

121.买卖股票的最佳时机

思路一:贪心
  • 不断更新最小买入值
  • 不断更新当前值和最小买入值的差值最大值

思路二:动态规划(今天自己写出来了哈哈哈哈哈哈哈)
  • 1.dp存储:dp[i][0] 表示当前持有   dp[i][1]表示当前不持有
  • 2.状态转移方程(递推式)
    • dp[i][0]=max ( dp [ i - 1 ] [ 0 ] , - prices [ i ] )  之前就持有/当前买入
      • dp[i][1]=max ( dp [ i - 1 ] [ 1 ] , dp [ i - 1 ] [ 0 ] + prices [ i ] )  之前就没持有/当前卖出
  • 3.初始化:dp[0][0]=-prices[0]   dp[0][1] =0
  • 4.遍历顺序:1-n
class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(2));dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],-prices[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);}return dp[n-1][1];//最后肯定不持有利润最大}
};

122.买卖股票的最佳时机||(拿捏)

思路一:贪心
  • 只要有利润增长就卖出,最后一定获得最大利润

思路二:动态规划

1.dp存储:dp[i][0]为持有  dp[i][1]为不持有

2.状态转移方程(递推式):

  • dp [ i ] [ 0 ] = max ( dp [ i - 1 ] [ 0 ] , dp [ i - 1 ] [ 1 ] - prices [ i ] )  之前持有/现在买入(上一次不持有的金额 - 买入的金额)
  • dp [ i ] [ 1 ] = max ( dp [ i - 1 ] [ 1 ] , dp [ i - 1 ] [ 0 ] + prices [ i ] )  之前没持有/现在卖出(上一次持有的金额 + 卖出的金额)

3.初始化:dp[0][0]=-prices[0]   dp[0][1]=0

4.遍历顺序:1-n

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(2));dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);}return dp[n-1][1];}
};

123.买卖股票的最佳时机|||

思路:动态规划(5个状态)
class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(5,0));dp[0][1]=-prices[0];dp[0][3]=-prices[0];for(int i=1;i<n;i++){dp[i][0]=dp[i-1][0]; //第一天不持有dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);  //第一天买入dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i]);  //第一天卖出dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i]);  //第二天买入dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i]);}return dp[n-1][4];}
};

相关文章:

day-49 代码随想录算法训练营(19) 动态规划 part 10

121.买卖股票的最佳时机 思路一&#xff1a;贪心 不断更新最小买入值不断更新当前值和最小买入值的差值最大值 思路二&#xff1a;动态规划&#xff08;今天自己写出来了哈哈哈哈哈哈哈&#xff09; 1.dp存储&#xff1a;dp[i][0] 表示当前持有 dp[i][1]表示当前不持有2.状…...

检查文件名是否含不可打印字符的C++代码源码

本篇文章属于《518抽奖软件开发日志》系列文章的一部分。 我在开发《518抽奖软件》&#xff08;www.518cj.net&#xff09;的时候&#xff0c;有时候需要检查输入的是否是合法的文件名&#xff0c;文件名是否含不可打印字符等。代码如下&#xff1a; //----------------------…...

学习笔记-正则表达式

https://www.runoob.com/regexp/regexp-tutorial.html 正则表达式re(Regular Expression)是一种文本模式&#xff0c;包括普通字符&#xff08;例如&#xff0c;a 到 z 之间的字母&#xff09;和特殊字符&#xff08;称为"元字符"&#xff09;&#xff0c;可以用来描…...

Wireshark TS | 网络路径不一致传输丢包问题

问题背景 网络路径不一致&#xff0c;或者说是网络路径来回不一致&#xff0c;再专业点可以说是网络路径不对称&#xff0c;以上种种说法&#xff0c;做网络方向的工程师肯定会更清楚些&#xff0c;用简单的描述就是&#xff1a; A 与 B 通讯场景&#xff0c;C 和 D 代表中间…...

CMake高级用法实例分析(学习paddle官方的CMakeLists)

cmake基础学习教程 https://juejin.cn/post/6844903557183832078 官方完整CMakeLists cmake_minimum_required(VERSION 3.0) project(PaddleObjectDetector CXX C)option(WITH_MKL "Compile demo with MKL/OpenBlas support,defaultuseMKL." ON) o…...

数据采集: selenium 自动翻页接口调用时的验证码处理

写在前面 工作中遇到&#xff0c;简单整理理解不足小伙伴帮忙指正 对每个人而言&#xff0c;真正的职责只有一个&#xff1a;找到自我。然后在心中坚守其一生&#xff0c;全心全意&#xff0c;永不停息。所有其它的路都是不完整的&#xff0c;是人的逃避方式&#xff0c;是对大…...

IDEA安装翻译插件

IDEA安装翻译插件 File->Settings->Plugins 在Marketplace中&#xff0c;找到Translation&#xff0c;点击Install 更换翻译引擎 勾选自动翻译文档 翻译 鼠标右击->点击Translate...

DBeaver使用

一、导出表结构 二、导出数据CSV 导出数据时DBeaver并没有导出表结构&#xff0c;所以表结构需要额外保存&#xff1b; 导入数据CSV 导入数据时会因外键、字段长度导致失败&#xff1b;...

Nougat:一种用于科学文档OCR的Transformer 模型

随着人工智能领域的不断进步&#xff0c;其子领域&#xff0c;包括自然语言处理&#xff0c;自然语言生成&#xff0c;计算机视觉等&#xff0c;由于其广泛的用例而迅速获得了大量的普及。光学字符识别(OCR)是计算机视觉中一个成熟且被广泛研究的领域。它有许多用途&#xff0c…...

redis八股1

参考Redis连环60问&#xff08;八股文背诵版&#xff09; - 知乎 (zhihu.com) 1.是什么 本质上是一个key-val数据库,把整个数据库加载到内存中操作&#xff0c;定期通过异步操作把数据flush到硬盘持久化。因为纯内存操作&#xff0c;所以性能很出色&#xff0c;每秒可以超过10…...

人工智能基础-趋势-架构

在过去的几周里&#xff0c;我花了一些时间来了解生成式人工智能基础设施的前景。在这篇文章中&#xff0c;我的目标是清晰概述关键组成部分、新兴趋势&#xff0c;并重点介绍推动创新的早期行业参与者。我将解释基础模型、计算、框架、计算、编排和矢量数据库、微调、标签、合…...

Date日期工具类(数据库日期区间问题)

文章目录 前言DateUtils日期工具类总结 前言 在我们日常开发过程中&#xff0c;当涉及到处理日期和时间的操作时&#xff0c;字符串与Date日期类往往要经过相互转换&#xff0c;且在SQL语句的动态查询中&#xff0c;往往月份的格式不正确&#xff0c;SQL语句执行的效果是不同的…...

为什么需要 TIME_WAIT 状态

还是用一下上一篇文章画的图 TCP 的 11 个状态&#xff0c;每一个状态都缺一不可&#xff0c;自然 TIME_WAIT 状态被赋予的意义也是相当重要&#xff0c;咱们直接结论先行 上文我们提到 tcp 中&#xff0c;主动关闭的一边会进入 TIME_WAIT 状态&#xff0c; 另外 Tcp 中的有 …...

Linux——(第七章)文件权限管理

目录 一、基本介绍 二、文件/目录的所有者 1.查看文件的所有者 2.修改文件所有者 三、文件/目录的所在组 1.修改文件/目录所在组 2.修改用户所在组 四、权限的基本介绍 五、rwx权限详解 1.rwx作用到文件 2.rwx作用到目录 六、修改权限 一、基本介绍 在Linux中&…...

Scala在大数据领域的崛起:当前趋势和未来前景

文章首发地址 Scala在大数据领域有着广阔的前景和现状。以下是一些关键点&#xff1a; Scala是一种具有强大静态类型系统的多范式编程语言&#xff0c;它结合了面向对象编程和函数式编程的特性。这使得Scala非常适合处理大数据&#xff0c;因为它能够处理并发、高吞吐量和复杂…...

前端面试经典题--页面布局

题目 假设高度已知&#xff0c;请写出三栏布局&#xff0c;其中左、右栏宽度各为300px&#xff0c;中间自适应。 五种解决方式代码 浮动解决方式 绝对定位解决方式 flexbox解决方式 表格布局 网格布局 源代码 <!DOCTYPE html> <html lang"en"> <…...

【webrtc】接收/发送的rtp包、编解码的VCM包、CopyOnWriteBuffer

收到的rtp包RtpPacketReceived 经过RtpDepacketizer 解析后变为ParsedPayloadRtpPacketReceived 分配内存,执行memcpy拷贝:然后把 RtpPacketReceived 给到OnRtpPacket 传递:uint8_t* media_payload = media_packet.AllocatePayload(rtx_payload.size());RTC...

Bash常见快捷键

生活在 Bash Shell 中&#xff0c;熟记以下快捷键&#xff0c;将极大的提高你的命令行操作效率。 编辑命令 Ctrl a &#xff1a;移到命令行首Ctrl e &#xff1a;移到命令行尾Ctrl f &#xff1a;按字符前移&#xff08;右向&#xff09;Ctrl b &#xff1a;按字符后移&a…...

软件验收测试

1. 服务流程 验收测试 2. 服务内容 测试过程中&#xff0c;根据合同要求制定测试方案&#xff0c;验证工程项目是否满足用户需求&#xff0c;软件质量特性是否达到系统的要求。 3. 周期 10-15个工作日 4. 报告用途 可作为进行地方、省级、国家、部委项目的验收&#xff0…...

Java 与零拷贝

零拷贝是由操作系统实现的&#xff0c;使用 Java 中的零拷贝抽象类库在支持零拷贝的操作系统上运行才会实现零拷贝&#xff0c;如果在不支持零拷贝的操作系统上运行&#xff0c;并不会提供零拷贝的功能。 简述内核态和用户态 Linux 的体系结构分为内核态&#xff08;内核空间…...

AI性能指标解析:误触率与错误率

简介&#xff1a;随着人工智能&#xff08;AI&#xff09;技术的不断发展&#xff0c;它越来越多地渗透到我们日常生活的各个方面。从个人助手到自动驾驶&#xff0c;从语音识别到图像识别&#xff0c;AI正不断地改变我们与世界的互动方式。但你有没有想过&#xff0c;如何准确…...

count(*) 和 count(1) 有什么区别?哪个性能最好?

哪种 count 性能最好&#xff1f; count() 是什么&#xff1f; count() 是一个聚合函数&#xff0c;函数的参数不仅可以是字段名&#xff0c;也可以是其他任意表达式&#xff0c;该函数的作用是统计符合查询条件的记录中&#xff0c;函数指定的参数不为 NULL 的记录由多少条。…...

橡胶密封件为什么会老化?

橡胶密封件以其优良的密封性能被广泛应用于各个行业。然而&#xff0c;随着时间的推移&#xff0c;这些橡胶密封件往往会恶化和老化。在这篇文章中&#xff0c;我们将探讨橡胶密封件老化的原因。 1&#xff0c;导致橡胶密封件老化的主要因素之一是暴露在阳光和紫外线(UV)辐射下…...

Uboot中bootargs以及bootcmd设置

Uboot命令 一、Uboot基础命令 查看帮助信息&#xff1a; uboot#help打印环境变量&#xff1a; uboot#printenv其他命令&#xff1a; uboot#help ? - 帮助命令&#xff0c;等同于 help base - 打印或设置地址偏移量 bdinfo - 打印板级信息结构 boot …...

冠达管理:减肥药概念再度爆发,常山药业两连板,翰宇药业等大涨

减肥药概念12日盘中再度拉升&#xff0c;到发稿&#xff0c;常山药业“20cm”涨停&#xff0c;翰宇药业涨超14%&#xff0c;德展健康涨停&#xff0c;金凯生科涨近9%&#xff0c;争气股份、普利制药、昊帆生物涨约5%&#xff0c;诺泰生物、圣诺生物、华森制药等涨超4%。 常山药…...

实现在外网SSH远程访问内网树莓派的详细教程

文章目录 如何在局域网外SSH远程访问连接到家里的树莓派&#xff1f;如何通过 SSH 连接到树莓派步骤1. 在 Raspberry Pi 上启用 SSH步骤2. 查找树莓派的 IP 地址步骤3. SSH 到你的树莓派步骤 4. 在任何地点访问家中的树莓派4.1 安装 Cpolar4.2 cpolar进行token认证4.3 配置cpol…...

Pytorch框架详解

文章目录 引言1. 安装与配置1.1 如何安装PyTorch1.2 验证安装 2. 基础概念2.1 张量&#xff08;Tensors&#xff09;2.1.1 张量的基本特性2.1.2 创建张量2.1.3 张量操作 2.2 自动微分&#xff08;Autograd&#xff09;2.2.1 基本使用2.2.2 计算梯度2.2.3 停止追踪历史2.2.4 自定…...

2023年9月制造业NPDP产品经理国际认证报名来这错不了

产品经理国际资格认证NPDP是新产品开发方面的认证&#xff0c;集理论、方法与实践为一体的全方位的知识体系&#xff0c;为公司组织层级进行规划、决策、执行提供良好的方法体系支撑。 【认证机构】 产品开发与管理协会&#xff08;PDMA&#xff09;成立于1979年&#xff0c;是…...

linux(centos7)配置SSH免密登录

给三台机器配置主机名映射 在Windows系统中修改hosts文件&#xff0c;新增以下内容&#xff1b; 192.168.xxx.xxx bigdata_node1 192.168.xxx.xxx bigdata_node2 192.168.xxx.xxx bigdata_node33台Linux的/etc/hosts文件中&#xff0c;填入如下内容。 192.168.xxx.xxx bigda…...

cf 交互题

今天cf遇到了交互题&#xff0c;这个交互题的算法很很很简单&#xff0c;但是在交互上卡了&#xff0c;导致交上的代码都不算罚时。&#xff08;更伤心了。 所以&#xff0c;现在写一下交互题的做法&#xff0c;印象深刻嘛。 交互题&#xff0c;就是跟机器进行交互。你代码运…...

空间站 参考消息/免费发布信息不收费的网站

“安全第一、预防为主、综合治理”是关系到国家经济发展与社会稳定的安全方针。安全生产是涉及职工生命安全的大事&#xff0c;同时关系到企业的生存发展和稳定。 2021年6月&#xff0c;第十三次全国人民代表大会常务委员会第二十九次会议&#xff0c;通过《全国人民代表大会常…...

婚纱摄影网站首页/经典网络营销案例

二、操作系统应用41.请在考生文件夹下完成如下操作&#xff1a;(1)在考生文件夹下建立“计算机基础练习”文件夹;(2)在“计算机基础练习”文件夹下建立“文字”﹑“图片”和“多媒体”三个子文件夹;(3)在考生文件夹下查找一个名为“1.BMP”的图片文件&#xff0c;将它复制到“图…...

自己做网站需要啥/曲靖新闻今日头条

保存个链接&#xff0c;免得以后用的时候找不到 下载地址...

北京网站建设服务中心/qq代刷网站推广

一&#xff1a;软件测试的定义&#xff1a;根据用户需求行业规范&#xff0c;采用一些测试方法或一些工具对被测系统&#xff08;程序数据文档&#xff09;进行相应的测试&#xff08;审核&#xff0c;运行&#xff0c;评估&#xff09;&#xff0c;尽早尽快的发现软件问题&…...

wordpress教程 知乎/电商网站设计论文

一.Function函数基础 函数&#xff1a;就是将一些语句进行封装&#xff0c;然后通过调用的形式&#xff0c;执行这些语句。 1.函数的作用&#xff1a; 将大量重复的语句写在函数里&#xff0c;以后需要这些语句的时候&#xff0c;可以直接调用函数&#xff0c;避免重复劳动。 …...

对网站主要功能界面进行赏析/网站推广关键词工具

&#xff08;1&#xff09;计算器的定义为&#xff1a;接受用户输入指令不数据&#xff0c;经由中央处理器的数学与逻辑单元运算处理后&#xff0c;以产生或储存成有用的信息&#xff1b;&#xff08;2&#xff09;计算机的五大单元包括&#xff1a;输入单元、 输出单元、CPU内…...