第五十一天| 309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费

本文主要是介绍第五十一天| 309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

第四十八天| 121. 买卖股票的最佳时机、122.买卖股票的最佳时机II-CSDN博客

第五十天| 123.买卖股票的最佳时机III、188.买卖股票的最佳时机IV-CSDN博客

Leetcode 309.最佳买卖股票时机含冷冻期 

题目链接:309 最佳买卖股票时机含冷冻期

题干:给定一个整数数组prices,其中第  prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

  • 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

思考:动态规划。本题是在 122.买卖股票的最佳时机II 的基础上加上冷冻期。

  • 确定dp数组以及下标的含义(本题的难点)

dp[i][j]:第i天,状态为j,所剩的最多现金为dp[i][j]。

出现冷冻期后,状态比较复杂度。尤其要注意 不进行买入卖出 的几种情况。

具体可以区分出如下四个状态:

  • 状态一:持有股票状态(今天 或 之前就买入了股票然后没有操作,一直持有)
  • 不持有股票状态,这里就有两种卖出股票状态
    • 状态二:保持卖出股票状态(前一天处于冷冻期 或 之前就是卖出股票状态,一直没操作)
    • 状态三:今天卖出股票(真实卖出股票)
  • 状态四:今天为冷冻期状态,但冷冻期状态不可持续,只有一天!

 以上状态j分别用0,1,2,3代指。

本题之所以要将不持有股票的状态分为状态二和状态三,是由于如果本题的冷冻期从不持有股票的状态推出,则冷冻期连续,不止一天,与题干矛盾。

  • 确定递推公式

达到买入股票状态(状态一)即:dp[i][0],有两个具体操作:

  • 操作一:前一天就是持有股票状态(状态一),dp[i][0] = dp[i - 1][0]
  • 操作二:今天买入股票,有两种情况
    • 前一天是冷冻期(状态四),dp[i - 1][3] - prices[i]
    • 前一天是保持卖出股票的状态(状态二),dp[i - 1][1] - prices[i]

那么dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);


达到保持卖出股票状态(状态二)即:dp[i][1],有两个具体操作:

  • 操作一:前一天就是状态二,dp[i - 1][1]
  • 操作二:前一天是冷冻期(状态四),dp[i - 1][3]

dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);


达到今天就卖出股票状态(状态三),即:dp[i][2] ,只有一个操作:

昨天一定是持有股票状态(状态一),今天卖出。即:dp[i][2] = dp[i - 1][0] + prices[i];


达到冷冻期状态(状态四),即:dp[i][3],只有一个操作:

昨天卖出了股票(状态三)。dp[i][3] = dp[i - 1][2];

  • dp数组如何初始化

从递推公式可以看出,基础为dp[0][j],即第0天如何初始化。

如果是持有股票状态(状态一)那么:dp[0][0] = -prices[0],一定是当天买入股票。

之后三种状态的初始化,从定义难以解释,因此我们直接从递推公式来推导。

如果i为1,第1天买入股票,那么递归公式中需要计算 dp[i - 1][1] - prices[i] ,即 dp[0][1] - prices[1],此处的 dp[0][1] (即第0天的保持卖出股票状态(状态二))相当于第0天的利润作本金,因此初始为0。

同理第0天的今天卖出股票(状态三),dp[0][2]也应初始化为0。

此外由于冷冻期不操作,状态四和状态三的值恒等。因此dp[0][3]也初始为0。

  • 确定遍历顺序

从递归公式上可以看出,dp[i] 依赖于 dp[i-1],所以是从前向后遍历。

  • 举例推导dp数组

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

最后 获取最大金额一定不是持有股票的状态,只可能是最后一天卖出股票(状态三)或最后一天不操作(状态二和状态四),并且返回这三种状态的最大值。 

代码:

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(4));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][1], dp[i - 1][3]) - prices[i]);//保持卖出股票状态、之前处于冷冻期状态本次处于卖出股票状态dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);//之前处于持有股票状态本次真实卖出股票dp[i][2] = dp[i - 1][0] + prices[i];//之前真实卖出股票本次处于冷冻期dp[i][3] = dp[i - 1][2];}//最后一天卖出股票 或 最后一天无操作return max(dp[prices.size() - 1][2], max(dp[prices.size() - 1][1], dp[prices.size() - 1][3]));}
};

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

题目链接:714 买卖股票的最佳时机含手续费

题干:给定一个整数数组 prices,其中 prices[i]表示第 i 天的股票价格 ;整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。

思考:动态规划。本题与 122.买卖股票的最佳时机II 的区别就是这里需要多一个减去手续费的操作。减去手续费的操作既可以放在购入股票时也可以放在卖出股票时。(下面的代码将费用放在购票时)。递推公式和初始化稍加修改即可。

代码:

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {//dp[i][0]:第i天持有股票状态    dp[i][1]:第i天不持有股票状态vector<vector<int>> dp(prices.size(), vector<int>(2));dp[0][0] = - prices[0] - fee;       //买入股票时考虑手续费dp[0][1] = 0;for (int i = 1; i < prices.size(); i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i] - fee);   //一直持有股票 或 第i天买入股票(上一次交易利润作本金)dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);         //第i天卖出股票 或 之前就卖出股票}return dp[prices.size() - 1][1]; }
};

股票问题总结:

股票问题的重点有两处:

        对于股票交易次数的限制 可以从 每次交易的本金 和 交易状态考虑。只需一次交易则交易本金一直为0;无限次交易则将上次交易的利润当作本次交易的本金;有限次(大于一次)交易通过添加 不同次交易状态 来同步更新 保证不超过指定交易次数。

​​​​​​​        对于交易情况的限制 可以从 交易状态考虑。本质上和有限次交易次数限制一样,但是要考虑具体的状态种类 来确定dp数组含义 以及 考虑全各种状态之间的转换情况 来确定递推公式。

这篇关于第五十一天| 309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/784904

相关文章

如何确定 Go 语言中 HTTP 连接池的最佳参数?

确定 Go 语言中 HTTP 连接池的最佳参数可以通过以下几种方式: 一、分析应用场景和需求 并发请求量: 确定应用程序在特定时间段内可能同时发起的 HTTP 请求数量。如果并发请求量很高,需要设置较大的连接池参数以满足需求。例如,对于一个高并发的 Web 服务,可能同时有数百个请求在处理,此时需要较大的连接池大小。可以通过压力测试工具模拟高并发场景,观察系统在不同并发请求下的性能表现,从而

Prometheus与Grafana在DevOps中的应用与最佳实践

Prometheus 与 Grafana 在 DevOps 中的应用与最佳实践 随着 DevOps 文化和实践的普及,监控和可视化工具已成为 DevOps 工具链中不可或缺的部分。Prometheus 和 Grafana 是其中最受欢迎的开源监控解决方案之一,它们的结合能够为系统和应用程序提供全面的监控、告警和可视化展示。本篇文章将详细探讨 Prometheus 和 Grafana 在 DevO

springboot整合swagger2之最佳实践

来源:https://blog.lqdev.cn/2018/07/21/springboot/chapter-ten/ Swagger是一款RESTful接口的文档在线自动生成、功能测试功能框架。 一个规范和完整的框架,用于生成、描述、调用和可视化RESTful风格的Web服务,加上swagger-ui,可以有很好的呈现。 SpringBoot集成 pom <!--swagge

股票数据接口-陈科肇

陈科肇 新浪财经 sz-深圳sh-上海历史分价表:http://market.finance.sina.com.cn/pricehis.php?symbol=sz000506&startdate=2016-12-27&enddate=2016-12-27历史成交明细(当日成交明细):http://vip.stock.finance.sina.com.cn/quotes_service/v

《C++中的移动构造函数与移动赋值运算符:解锁高效编程的最佳实践》

在 C++的编程世界中,移动构造函数和移动赋值运算符是提升程序性能和效率的重要工具。理解并正确运用它们,可以让我们的代码更加高效、简洁和优雅。 一、引言 随着现代软件系统的日益复杂和对性能要求的不断提高,C++程序员需要不断探索新的技术和方法来优化代码。移动构造函数和移动赋值运算符的出现,为解决资源管理和性能优化问题提供了有力的手段。它们允许我们在不进行不必要的复制操作的情况下,高效地转移资源

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

避免Java程序中NullPointerException的技巧和最佳实践

Java应用中抛出的空指针异常是解决空指针的最好方式,也是写出能顺利工作的健壮程序的关键。俗话说“预防胜于治疗”,对于这么令人讨厌的空指针异常,这句话也是成立的。值得庆幸的是运用一些防御性的编码技巧,跟踪应用中多个部分之间的联系,你可以将Java中的空指针异常控制在一个很好的水平上。顺便说一句,这是Javarevisited上的第二个空指针异常的帖子。在上个帖子中我们讨论了Java中导致空指针异

构建现代API:FastAPI中Query与Body参数的最佳搭配

在FastAPI中,Query 和 Body 是两种不同的依赖注入器,它们的应用场景取决于你的具体需求。以下是它们各自常见的使用场景: Query 参数 使用场景: 当你需要从URL中获取一些简单的参数时,例如过滤、排序、分页等。 当数据量不大,且可以作为URL的一部分安全传输时。当数据不需要复杂的结构时。 Body 参数 使用场景: 当你需要发送较为复杂的数据结构时,例如包含多个字段

[含视频和源码]CRUD的最佳实践,联动前后端,包含微信小程序,API,HTML等(三)

关说不练假把式,在上一,二篇中介绍了我心目中的CRUD的样子 基于之前的理念,我开发了一个命名为PasteTemplate的项目,这个项目呢后续会转化成项目模板,转化成项目模板后,后续需要开发新的项目就可以基于这个模板创建,这样就不要copy一个旧的项目,然后删删删,改改改,重命名等操作了 强迫症,一个项目的名字就得统一,心里才舒服 那么本次作者就带来了实物,本次主要介绍管理端的内容,我们一起

佰朔资本:股票为什么会跌?跌了还会涨回来吗?

或许导致股票下跌的原因: 1、遭到商场环境要素影响,商场环境要素是指影响股票商场整体走势的要素,比如宏观经济、政策法规、商场资金、商场心境等。假如商场环境出现改变,比如经济添加放缓、政策收紧、资金紧张、商场不确定性添加等,那么投资者对股票的需求和持股决心就会下降,然后导致股价下跌。 2、遭到个股基本面要素影响,基本面要素是指影响股票内在价值的要素,比如企业的财务情况、成果表现、发展战略、管理水