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:/…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...
Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...
Axure 下拉框联动
实现选省、选完省之后选对应省份下的市区...
