LeetCode-309. 最佳买卖股票时机含冷冻期
目录
- 题目思路
- 动态规划
题目来源
309. 最佳买卖股票时机含冷冻期
题目思路
每天最多只可能有三种状态中的一种
0表示当前处于买入状态(持有股票)
1表示当前处于卖出状态(不持有股票)
2表示当前处于冷冻状态 设dp[i][j]表示i - 1天状态为j时所拥有的最大现金
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i]); //持有股票dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]); //不持有股票dp[i][2] = dp[i-1][1]; //冷冻期
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i])意思是你只有在股票冷冻期之后才能买入
dp[i][2] = dp[i-1][1]意思是冷冻期肯定是卖出的状态(手上没有股票)
动态规划
- 1.确定dp数组以及下标的含义
dp[i][j],第i天状态为j,所剩的最多现金为dp[i][j]。
可以定义下面三个状态
0表示当前处于买入状态(持有股票)
1表示当前处于卖出状态(不持有股票)
2表示当前处于冷冻状态 设dp[i][j]表示i - 1天状态为j时所拥有的最大现金
- 2.确定递推公式
买入状态
操作一:前一天就是持有股票状态(状态一),dp[i][0] = dp[i - 1][0]
操作二:冷冻期之后才能买 dp[i][0] = dp[i-1][2]-prices[i]
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
卖出状态
操作一:前一天就是卖出状态,dp[i][1] = dp[i - 1][1]
操作二:持有股票才能卖出,dp[i][1] = dp[i-1][0]+prices[i]
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
冷冻状态
只有卖出的状态
dp[i][2] = dp[i-1][1];
- 3.dp数组如何初始化
如果是持有股票状态那么:dp[0][0] = -prices[0],一定是当天买入股票。
如果是不持有股票状态,dp[0][1] = 0,当天买当天卖
如果是冷冻期状态,dp[0][2] = 0,延续不持有股票的状态
- 4.确定遍历顺序
从递归公式上可以看出,dp[i] 依赖于 dp[i-1],所以是从前向后遍历。
- 5.举例推导dp数组
以 [1,2,3,0,2] 为例,dp数组如下:

代码实现
class Solution {public int maxProfit(int[] prices) {if(prices == null || prices.length == 0){return 0;}int[][] dp = new int[prices.length][3];dp[0][0] = -prices[0];dp[0][1] = 0;dp[0][2] = 0;for(int i = 1;i<prices.length;i++){dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i]); //持有股票dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]); //不持有股票dp[i][2] = dp[i-1][1]; //冷冻期}return Math.max(dp[prices.length-1][1],dp[prices.length-1][2]);}
}

相关文章:
LeetCode-309. 最佳买卖股票时机含冷冻期
目录题目思路动态规划题目来源 309. 最佳买卖股票时机含冷冻期 题目思路 每天最多只可能有三种状态中的一种 0表示当前处于买入状态(持有股票) 1表示当前处于卖出状态(不持有股票) 2表示当前处于冷冻状态 设dp[i][j]表示i - 1天状态为j时所拥有的最大现金 dp[i][0] Math.ma…...
AUTOSAR知识点Com(七):CANSM初认知
目录 1、概述 2、CanSM主要做什么 2.1、CAN控制器状态管理 2.2、CAN收发器状态管理 2.3、Busoff检测 1、概述 CANSM(Controller Area Network State Manager)是AUTOSAR(Automotive Open System Architecture)标准中的一个模块…...
递归:斐波那契数列、递归实现指数型枚举、递归实现排列型枚举
递归:O(2^n) 调用自己 例题及代码模板: 斐波那契数列 输入一个整数 n ,求斐波那契数列的第 n 项。 假定从 0 开始,第 0 项为 0。 数据范围 0≤n≤39 样例 输入整数 n5 返回 5 #include <iostream> #include <cstring&g…...
oracle模糊查询时字段内容包含下划线的解决办法
最近项目中遇到一个关于模糊查询问题。表tabA中的字段name的值有下划线的情况,在模糊查询时发现查询的记录不对。 表的结构 表名:tabA id name sex 1 test_601 1 2 test_602 2 3 test16 1 4 t…...
C++:explicit关键字
C中的explicit关键字只能用于修饰只有一个参数的类构造函数,它的作用是表明该构造函数是显示的,而非隐式的,跟它相对应的另一个关键字是implicit,意思是隐藏的,类构造函数默认情况下即声明为implicit(隐式)。那么显示声…...
【C5】bmc wtd,post
文章目录1.bmc_wtd_cpld:syscpld.c中wd_en和wd_kick节点对应寄存器,crontab,FUNCNAME2.AST芯片WDT切换主备:BMC用WDT2作为主备切换的控制器2.1 AC后读取:bmc处于主primary flash(设完后:实际主&…...
200.Spark(七):SparkSQL项目实战
一、启动环境 需要启动mysql,hadoop,hive,spark。并且能让spark连接上hive(上一章有讲) #启动mysql,并登录,密码123456 sudo systemctl start mysqld mysql -uroot -p#启动hive cd /opt/module/ myhadoop.sh start#查看启动情况 jpsall#启动hive cd /opt/module/hive/…...
区块链系统:挖矿原理
在比特币的P2P网络中,有一类节点,它们时刻不停地进行计算,试图把新的交易打包成新的区块并附加到区块链上,这类节点就是矿工。因为每打包一个新的区块,打包该区块的矿工就可以获得一笔比特币作为奖励。所以,…...
【博弈】【清华冬令营2018模拟】取石子
写完敢说全网没有这么详细的题解了。 注意:题解长是为了方便理解,所以读起来速度应该很快。 题目描述 有 nnn 堆石子,第 iii 堆有 xix_ixi 个。 AliceAliceAlice 和 BobBobBob 轮流去石子(先后手未定), …...
嵌入式:BSP的理解
BSP概念总结BSP定义BSP的特点BSP的主要工作BSP在嵌入式系统和Windowsx系统中的不同BSP和PC机主板上的BIOS区别BSP与 HAL关系嵌入式计算机系统主要由 硬件层,中间层,系统软件层和应用软件层四层组成。硬件层:包含CPU,存储器(SDRAM&…...
Linux主机Tcpdump使用-centos实例
1、安装前系统信息 ifconfig查看系统网络接口情况。这里可以看到3个interface,ens160是正常使用的网口,lo是主机的loopback地址127.0.0.1。另外,由于centos安装在虚拟主机上,virbr0是KVM默认创建的一个Bridge,其作用是为连接其上的…...
线性DP——AcWing 898. 数字三角形、AcWing 895. 最长上升子序列
AcWing 898. 数字三角形 1.题目 898. 数字三角形 2.思路 DP问题首先考虑状态转移方程,定义一个集合f ( i , j) ,表示从第一个数字(1,1)走到第 i行,第 j列(i , j)的所有方案的集合,…...
SpringMVC
SpringMVC配置 引入Maven依赖 (springmvc)web.xml配置DispatcherServlet配置 applicationContext 的 MVC 标记开发Controller控制器 几点注意事项: 在web.xml中 配置<load-on-startup> 0 </load-on-startup> 会自动创建Spring…...
C++模板基础(二)
函数模板(二) ● 模板实参的类型推导 – 如果函数模板在实例化时没有显式指定模板实参,那么系统会尝试进行推导 template<typename T> void fun(T input, T input2) {std::cout << input << \t << input2 << …...
什么是linux内核态、用户态?
目录标题为什么需要区分内核空间与用户空间内核态与用户态如何从用户空间进入内核空间整体结构为什么需要区分内核空间与用户空间 在 CPU 的所有指令中,有些指令是非常危险的,如果错用,将导致系统崩溃,比如清内存、设置时钟等。如…...
day8—选择题
文章目录1.Test.main() 函数执行后的输出是(D)2. JUnit主要用来完成什么(D)3.下列选项中关于Java中super关键字的说法正确的是(A)1.Test.main() 函数执行后的输出是(D) public clas…...
ngx错误日志error_log配置
ngx之error_log 日志配置格式: 常见的错误日志级别 错误日志可配置位置 关闭error_log配置 设置debug 日志级别的前提: ngx之error_log 日志配置格式: error_log 存放路径 日志级别 例: error_log /usr/local/log…...
1.11、自动化
自动化 一、java 手机自动化 首先new DesertCapabilities(这是一个类) setCapability – 设置信息 获取appium的驱动对象 new AppiumDriver – 本机IP地址:端口号/wd/hub,前面的设置值信息 driver.findElementById() – 通过id找位置 click() – 点击 &…...
函数的定义与使用及七段数码管绘制
函数的定义 函数是一段代码的表示 函数是一段具有特定功能的、可重用的语句组 函数是一种功能的抽象,一般函数表达特定功能 两个作用:降低编程难度 和 代码复用 求一个阶乘 fact就是 函数名 n就是参数 return就是输出部分即返回值 而函数的调用就是…...
怎么压缩pdf文件大小?pdf文件太大如何压缩?
喜爱看小说的小伙伴们都会在网上下载很多的pdf格式电子书以方便随时阅览,但是pdf的电子书一般都过于的冗长,下载后的储存也是一个问题,怎么pdf压缩大小呢?可以试试今天介绍的这款pdf在线压缩工具来进行pdf压缩(https:/…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时,性能会显著下降。以下是优化思路和简易实现方法: 一、核心优化思路 减少 JOIN 数量 数据冗余:添加必要的冗余字段(如订单表直接存储用户名)合并表:将频繁关联的小表合并成…...
Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
