代码随想录算法训练营第五十一天| LeetCode309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费

一、LeetCode309.最佳买卖股票时机含冷冻期

题目链接/文章讲解/视频讲解:https://programmercarl.com/0309.%E6%9C%80%E4%BD%B3%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E6%97%B6%E6%9C%BA%E5%90%AB%E5%86%B7%E5%86%BB%E6%9C%9F.html

状态:已解决

1.思路 

        这道题多了一个限制条件:卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。也就是说,卖出股票后的第二天不能再买,那么股票要多出两个状态:首先,由于需要知道某天是否是卖出股票后的第二天,我们需要拆分以前的 “未持有股票” 状态为:当天卖出股票、卖出股票>=2天。其次,要多一个冰冻期状态。

(1)确定dp数组以及下标含义

        这道题只是股票状态多了两个,故还是一个二维数组,第一维代表天数,第二维代表股票状态,根据上面的分析,我们知道现在有四个股票状态:

        dp[i][0]:第 i 天持有股票

        dp[i][1]:第 i 天卖出股票

        dp[i][2]:第 i 天处于冷淡期

        dp[i][3]:第 i 天已卖出股票超过1天

(2)确定递推公式:

        对于dp[i][0],第 i 天持有股票要么第i-1天也持有股票,要么是第 i-1 天卖出股票超过1天或刚好处于冷淡期然后今天重新购入一份。故dp[i][0] = max(dp[i-1][0], max(dp[i-1][3] - prices[i],dp[i-1][2]-prices[i]))。

        对于dp[i][1],第 i 天卖出股票必定是第 i-1天能持有股票。故dp[i][1] = dp[i-1][0]+prices[i]。

        对于dp[i][2],第 i 天处于冷淡期,那么必定是因为第 i-1天卖出了股票,由于冷淡期买不了也没有什么可卖的,故dp[i][2] = dp[i-1][1]。

        对于dp[i][3],第 i 天已卖出股票超过1天,那么第 i-1 天也是已卖出股票很久要么处于冷淡期,故dp[i][3] = max(dp[i-1][3], dp[i-1][2])。

(3)初始化dp数组:

        根据递推公式,我们需要初始化:dp[0][0-3]。

        dp[0][0] = -prices[0];

        dp[0][1] = 0; 

        dp[0][2] = 0;(无具体含义,根据递推公式确定的)

        dp[0][3] = 0;(无具体含义,根据递推公式确定的)

(4)确定遍历顺序:

        跟以前一样,依旧是外层从前往后遍历天数。 

(5)举例推导dp数组:

         以 [1,2,3,0,2] 为例,dp数组如下:

        根据前面的分析我们知道卖出状态一定包含最大值所处的状态,但现在状态2、3、4都是卖出状态,因此最后要取三者中的最大值。

2.代码实现 

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

时间复杂度:O(n)

空间复杂度:O(4*n) 

二、 714.买卖股票的最佳时机含手续费

题目链接/文章讲解/视频讲解:https://programmercarl.com/0714.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA%E5%90%AB%E6%89%8B%E7%BB%AD%E8%B4%B9%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html

状态:已解决

1.思路 

        相对于动态规划:122.买卖股票的最佳时机II (opens new window),本题只需要在计算卖出操作的时候减去手续费就可以了,代码几乎是一样的。唯一差别在于递推公式部分,因此我们只主要讲解一下递推公式部分。

如果第i天持有股票即dp[1](状态压缩), 那么可以由两个状态推出来

  • 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[1]
  • 第i天买入股票,所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即:dp[0] - prices[i]

所以:dp[i][0] = max(dp[1], dp[0] - prices[i]);

如果第i天不持有股票即dp[0]的情况, 依然可以由两个状态推出来

  • 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:dp[0]
  • 第i天卖出股票,所得现金就是按照今天股票价格卖出后所得现金,注意这里需要有手续费了即:dp[1] + prices[i] - fee

所以:dp[i][1] = max(dp[0], dp[1] + prices[i] - fee);

2.代码实现 

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

时间复杂度:O(n)

空间复杂度:O(1) 

 

         

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/582925.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

实验一: 设备密码配置与远程管理

1.实验环境 用路由器和交换机搭建实验环境 2.需求描述 实现管理员主机对交换机和路由器的远程管理 设备上配置的密码都要被加密 3.推荐步骤 对路由器配置的步骤如下&#xff1a; 实现路由器和PC的连通性配置VTY密码和特权模式密码在PC上Telnet 到路由器。 对交换机配置的…

03-JAVA设计模式-观察者模式

观察者模式 什么是观察者模式 Java中的观察者模式是一种常见的设计模式&#xff0c;它允许对象&#xff08;观察者&#xff09;订阅另一个对象&#xff08;被观察者&#xff09;的状态变化&#xff0c;并在状态变化时自动得到通知。 核心&#xff1a; 观察者模式主要用于1&a…

HTML学习笔记(二)

1.HTML图像 图像标签&#xff08;<img>)和源属性&#xff08;src&#xff09; HTML中&#xff0c;图像由<img>标签来定义&#xff0c;<img>是空标签&#xff0c;只包含属性&#xff0c;没有闭合标签。在页面上显示图像需要使用源属性&#xff08;src),src是指…

Docker基本操作 Linux里边操作

docker镜像操作命令: docker images:查看所有镜像; docker rmi:删除镜像 后边可以跟镜像的名字或者id指定要删除的镜像&#xff1b; docker pull:拉取镜像&#xff1b; docker push:推送镜像到服务&#xff1b; docker save :打包镜像 后边有用法; docker load:加载镜像&…

前端JS必用工具【js-tool-big-box】,字符串反转,驼峰转换以及版本号对比

这一小节&#xff0c;我们针对前端工具包&#xff08;npm&#xff09;js-tool-big-box的使用做一些讲解&#xff0c;主要是针对字符串反转&#xff0c;aa-bb-cc转驼峰&#xff0c;以及版本号对比的内容 目录 1 安装和引入 2 字符串反转 3 带有横岗的转驼峰 3.1 转小驼峰 3…

docker-compose编排集成工具,

一、引言 我们知道使用一个 Dockerfile 模板文件可以定义一个单独的应用容器&#xff0c;如果需要定义多个容器就需要服务编排。服务编排有很多种技术方案&#xff0c;今天给大家介绍 Docker 官方产品 Docker-Compose Dockerfile 可以定义一个单独的应用容器&#xff1…

linux,从零安装mysql 8.0.30 ,并且更新至mysql 8.0.36

前言&#xff1a; 系统使用的CentOS 7&#xff0c;系统默认最小安装。 一、基础配置 配置虚拟机IP&#xff0c;需要更改的内容&#xff0c;如下红框中 修改之后 至此&#xff0c;基础配置完成。注意&#xff1a;此处虚拟机网络适配器使用的是&#xff1a;桥接模式 二、软件…

【问题实操】银河麒麟高级服务器操作系统实例,CPU软锁报错触发宕机

1.服务器环境以及配置 处理器&#xff1a; Kunpeng 920 内存&#xff1a; 256G DDR4 整机类型/架构&#xff1a; TaiShan 200 (Model 2280) 内核版本 4.19.90-23.8.v2101.ky10.aarch64 2.问题现象描述 两台搭载麒麟v10 sp1的机器均在系统CPU软锁报错时&#xff0c;触…

Springboot+mybatis升级版(Postman测试)

一、项目结构 1.导入依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apach…

高级数据结构与算法期中测试题

一、判断题 1、In dynamic programming algorithms, some results of subproblems have to be stored even they do not compose the optimal solution of a larger problem. T F 解析:T。在动态规划算法中,必须存储子问题的某些结果,因为他们可能需要用来…

区块链技术:NFG元宇宙电商模式

大家好&#xff0c;我是微三云周丽 随着互联网技术的迅猛发展&#xff0c;电子商务行业逐渐崛起为现代经济的重要支柱。而在这一浪潮中&#xff0c;元宇宙电商以其独特的商业模式和巨大的发展潜力&#xff0c;成为行业的新宠。其中&#xff0c;NFG作为元宇宙电商模式的代表&am…

【4110】基于小程序实现的名片管理系统

作者主页&#xff1a;Java码库 主营内容&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app等设计与开发。 收藏点赞不迷路 关注作者有好处 文末获取源码 技术选型 【后端】&#xff1a;Java 【框架】&#xff1a;spring…

std::ignore的定义

有个全局变量。 把一个变量赋值给ignore&#xff0c;还行&#xff0c;没有拷贝等动作&#xff0c;不用担心性能损失。 VS2017D:\DevTools\VS2017\VC\Tools\MSVC\14.16.27023\include\tuple// STRUCT _Ignore struct _Ignore{ // struct that ignores assignmentstemplate<…

如何利用 GPT 自我提高写作能力

GPT革命&#xff1a;如何用AI技术重新定义写作 介绍 在我们的数字时代&#xff0c;了解自我提高写作的必要性至关重要。 随着 GPT 的兴起&#xff0c;我们正在见证书写的变革时代。 这篇扩展文章深入探讨了 GPT 如何显着提高写作技能。 拥抱未来&#xff1a; 人工智能时代的写…

Oracle 数据迁移同步优化(三)

简述 CloudCanal 最近再次对其 Oracle 源端数据同步进行了一系列优化&#xff0c;这些优化基于用户在真实场景中的反馈&#xff0c;具备很强的生产级别参考意义。 本文将简要介绍这些优化项&#xff0c;希望带给读者一些收获。 增量事件 SCN 乱序问题MISSING_SCN 事件干扰新…

物联网和互联网有什么区别?从多个方面进行探讨——青创智通

工业物联网解决方案-工业IOT-青创智通 物联网和互联网是现代信息技术的两大重要领域&#xff0c;它们在许多方面有着紧密的联系&#xff0c;但也有着明显的区别。本文将从多个方面对物联网和互联网的区别进行探讨。 首先&#xff0c;从定义上来看&#xff0c;互联网是一种全球…

38.WEB渗透测试-信息收集-信息收集-企业信息收集(5)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;37.WEB渗透测试-信息收集-企业信息收集&#xff08;4&#xff09; 上个内容用到了cdn&am…

【赠书活动第3期】《PyTorch 2.0深度学习从零开始学》

1. 赠书活动 《PyTorch 2.0深度学习从零开始学》免费赠书 5 本&#xff0c; 可在本帖评论中简单评论一下本书的优缺点&#xff0c; 或者在本帖评论中简单写一下你学习PyTorch想要达到什么目的&#xff0c; 博主从本帖评论中写得较好的朋友中选5人赠送。 截止日期为2024年5…

leetcode-有效括号序列-94

题目要求 思路 1.使用栈的先进后出的思路&#xff0c;存储前括号&#xff0c;如果st中有对应的后括号与之匹配就说明没问题 2.有两个特殊情况就是字符串第一个就是后括号&#xff0c;这个情况本身就是不匹配的&#xff0c;还有一种是前面的n个字符串本身是匹配的&#xff0c;这…

vue3插槽的name和v-slot的研究

slot可以分为具名插槽和默认,默认插槽name是default 在父组件的template需要些v-slot/#,没写不生效,而在父组件下,而没被template包含的默认放在template且含有#default. 1)没写slot,可以不写template,也可写default的template2)写了name的slot,即使是default也必须些template…