309. 最佳买卖股票时机含冷冻期
2023-04-18 16:12:39 时间
一. 题目
二. 思路--动态规划
我把每天的持股状态分为四种,那么每天的收益情况就分为四种,这里就用二维dp数组来保存了 dp[i][j],i为天数,j为每天的状态 dp[i][j]各状态存最大收益
- j=0不持股,当天没卖出(说明本就不持股,前面就卖了)
- j=1不持股,当天卖了(前一天是持股状态)
- j=2持股,当天买了(前一天持股,为什么这里没有前一天没持股且没卖?因为由于冷却器存在,当天买了说明前一天没卖)
- j=3持股,当天没买(要么是前一天买的,要么是前一天本就持有的)
三. 代码:
class Solution {
public int maxProfit(int[] prices) {
final int len = prices.length;
//没有买卖机会
if (len <=1){
return 0;
}
//每天的持股状态dp[i][j],i为天数,j当前状态 dp[i][j]各状态存最大收益
// j=0不持股,当天没卖出(本就不持股,之前就卖的)
// j=1不持股,当天卖了
// j=2持股,当天买了(注意由于冷却器存在,当天买了说明前一天没卖)
// j=3持股,当天没买(要么是前一天买的,要么是前一天本就持有的)
int[][] dp=new int[len][4];
//初始化
dp[0][0]=0;//本来就不持有,啥也没干
dp[0][1]=0;//可以理解成第0天买入又卖出,那么第0天就是“不持股且当天卖出了”这个状态了,其收益为0,所以初始化为0是合理的
dp[0][2]=-1*prices[0];//第0天只买入,负收益
dp[0][3]=-1*prices[0];//当前的持股收益,负收益
for (int i = 1; i < len; i++) {
//前一天就不持股
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);
//前一天持股的收益+今天卖出的收益
dp[i][1]=Math.max(dp[i-1][2],dp[i-1][3])+prices[i];
//前一天可能不持股(非当天卖的)或者持股
dp[i][2]=Math.max(dp[i-1][0],dp[i-1][3])-prices[i];
//要么是前一天买的,要么是前一天本就持有的
dp[i][3]=Math.max(dp[i-1][2],dp[i-1][3]);
}
return Math.max(Math.max(dp[len-1][0],dp[len-1][1]),Math.max(dp[len-1][2],dp[len-1][3]));
}
}
相关文章
- Chrome标签开多就看不清:一招瞬间解决硬伤
- Chrome 88新功能曝光:查看PDF文档属性
- Mozilla 计划在 Firefox 86 中禁用退格键
- Windows 10 Build 21286发布,新功能亮相
- 红旗Linux桌面操作系统11社区预览版开放下载
- 聊聊Apt 和 Apt-Get 之间的区别是啥?
- 泄露代码曝光Windows 10 21H2 RTM完成时间:今年最重大版本
- 四个适合初学者的不是基于Ubuntu的Linux发行版
- P图P到神仙都不认得?教你识破图片有没有被P过
- 为什么Windows 10升级安装卡住了,原因在这
- 为 Linux 爱好者打造的极简 Mac 终端
- 和Sar比起来,其他Linux命令都是猹
- 值得推荐的Docker专用基础Linux发行版
- Linux用户空间与内核地址空间详解
- Firefox 85新增“批量删除密码”功能:再也不用一个一个删除密码了
- Windows 10新预览版21286推送:任务栏加入“负一屏”、磁盘管理重构
- 微软发布Edge浏览器89.0 Dev版:正式支持苹果M1处理器
- Linux 5.10.5正式发布:禁用FBCON加速滚动
- Windows 10 WSL现在可在启动时运行Linux命令
- 鸿蒙HarmonyOS开发板提前祝大家新年好!