当前位置: 首页 > news >正文

【dp力扣】买卖股票的最佳时机III

目录

审题

通过动态规划固定套路思考:

1、定义状态表示(关键)

2、推导状态转移方程(重点)

对于buy(可买入股票):

回顾状态表示:

第一种情况:

第二种情况:

联立两种情况(取两种情况的最大值):​

对于own(持有股票)

回顾状态表示:

第一种情况:

第二种情况:

(最终结果)联立两种情况(还是取max):

3、初始化特殊数据(重点)

第0天交易0次:

第0天交易1次和第0天交易2次:

关于状态方程的补充修改:

4、填表顺序

5、确定返回值

AC代码:


买卖股票的最佳时机III

class Solution {public int maxProfit(int[] prices) {}
}

本题还是用动态规划的思想去解决。

动态规划的固定解决套路:

审题

题目给定每天的股票价格,要求最多进行2次交易(可以进行0次或者1次或者2次交易),最终得到的最大利润。

题目要求其实很简单,不过要注意,进行0次交易获得最大利润也是可能的

prices{5,4,3,2,1}

像这种情况,只要进行交易,那么就是亏的,所以不进行交易就赚了(赚了0元😅)

通过动态规划固定套路思考:

1、定义状态表示(关键)

要定义好状态表示,我们要分析这道题目到底有那些状态。

最明显的,buy可买入股票),own(持有股票)这两种。

但是还有一个重要的状态,就是交易次数(最多两次),题目明确约束了交易次数最多两次。

另一个重要的状态就是当前的天数(最大取决于prices长度

也就是说这个状态表示要包含这样的信息:【第i天】,【最终是j交易状态】,【交易了k次】

也就是三个维度。

所以要用用3维数组?

可以,但没必要。

因为交易状态就只有两种,所以我们可以简单的用两个二维数组去表示:

class Solution {public int maxProfit(int[] prices) {/*own[i][j]代表第i天持有股票,交易了j次的最大利润* buy[i][j]代表第i天可买股票,交易了j次的最大利润** j大小是3 表示0次或者1次或者2次** i是prices的长度** 卖出去的时候,交易次数加一!!!* */int n=prices.length;if(n==1)return 0;int[][] own = new int[n][3];int[][] buy = new int[n][3];}
}

2、推导状态转移方程(重点)

事先说明,交易次数什么啥时候进行修改?

这个一定要想好,不然等一下会乱套。

实际上,既可以在卖股票的是后进行交易次数加1,

也可以选择先不加1,等到把股票卖出去了,然后在加1,这里我选择后者,也就是把股票买了的时候,对交易次数加1.

换而言之,卖出多少次股票,就交易了几次。

对于buy(可买入股票):

回顾状态表示:

第一种情况:

第二种情况:

立两种情况(取两种情况的最大值):

注意:上面这个状态方程实际上还有一个小问题,等一下会在初始化的时候讲解为什么,然后进行一个小小的修改。

对于own(持有股票)

回顾状态表示:

第一种情况:

第二种情况:

注意:因为只是进行了买股票操作,没有卖股票,所以交易次数j是不变的。

(最终结果)联立两种情况(还是取max):

3、初始化特殊数据(重点)

初始化特殊数据的原因就是为了保证状态方程能够正常的执行。

上面的状态方程都有i-1,所以为了确保数组不越界,我们必须对第0天进行初始化

想要对own和buy的第0天进行初始化,那么我们必须判断第0天的各种状态是否存在

第0天交易0次:

实际上第0天,own(持有股票)和buy(可交易)都是可能存在的。

buy很简单,own的话,只需要在当天进行股票购买即可。

所以这样初始化:

第0天交易1次和第0天交易2次:

这两种状态都是不可能出现的。

第0天交易1次是没有意义的,因为同一天股票价格一样,买卖等与没买。

第0天交易2次是同理,重复了两次无意义的操作。

那么对于这种不会存在的情况,如何处理呢?

在状态方程种使用了max函数,如果想要规避这种无效数据,最简单的办法就是赋值成极小值

但是如果这样赋值:,是会出现问题的。

因为状态方程种有这样一个式子:

buy[i-1][j]可能就是极小值,这时在减去一个数字不就出现数据溢出了吗?

最常用的办法就是使用这个数据:0x3f3f3f3f (16进制)它相当于

所以这样赋值:

关于状态方程的补充修改:

刚才我们提到,这个状态方程有一个小问题:

问题就在与,不仅i会越界(刚才的初始化已经解决),j实际上也会越界(当j=0)。

这里就有一个小技巧了,就是:

把方程才开来,做个判断,对于越界的情况,舍弃即可(舍弃的原因是,交易了-1次的状态不可能转化成交易了0次的状态,因为交易了-1次的状态是不可能存在的!):

4、填表顺序

这个很简单,先从从第0天开始,然后是从第0次交易开始。

对于二维数组就是外层先从上到下,然后从左到右:

5、确定返回值

在这道题中,交易多少次,与利润没有直接关系。

最大利润可能交易1次就是了,也可能交易2次才是,也可能是0次(比如上文给出的例子,不亏就行了)

所以j是要遍历一次的。

至于天数i,肯定是最后一天啊。即i=n-1(n是prices的长度)

另外,卖出状态肯定比买入状态利润大(如果你不放心,own[n-1][j]和buy[n-1][j]都遍历也没问题):

AC代码:

class Solution {public int maxProfit(int[] prices) {//定义状态表示111111111111111111111111111111111111//own持有股票//buy可买股票/*own[i][j]代表第i天持有股票,交易了j次的最大利润* buy[i][j]代表第i天可买股票,交易了j次的最大利润** j大小是3 表示0次或者1次或者2次** i是prices的长度** 卖出去的时候,交易次数加一!!!* *//*** own[i][j]表示 第i天 最终交易了j次,的状态是“持有股票”,且获得了最大利润**前一天(i-1)的own(持有股票),在今天(i)能转化成持有股票的状态吗?* 同样可以,今天什么都不做即可*own[i][j]=own[i-1][j];** 前一天(i-1)的buy(可交易),在今天(i)能转化成持有股票的状态吗?* 当然可以,昨天是可交易那今天还是可交易,今天买股票,那么今天的状态就变成了own* own[i][j]=buy[i-1][j]-prices[i];** own[i][j]=max(own[i-1][j],buy[i-1][j]-prices[i]);** */int n=prices.length;if(n==1)return 0;int[][] own = new int[n][3];int[][] buy = new int[n][3];//定义状态方程11111111111111111111111111111111111111111111111111111111/**own[i][j]* own[i][j]=own[i-1][j];//前天到今天什么都不做* own[i][j]=buy[i-1][j]-prices[i];//昨天可以买股票,那就今天把股票买了** own[i][j]=Math.max(own[i-1][j],buy[i-1][j]-prices[i]);** *//**buy[i][j]* buy[i][j]=own[i-1][j-1]+prices[i];//前一天有股票,今天卖出去,交易次数加一* buy[i][j]=buy[i-1][j];//昨天到今天什么都不干,那么钱就不会变。** if(i-1>=0)buy[i][j]=Math.max(own[i-1][j-1]+prices[i],buy[i][j]);* else buy[i][j]=buy[i-1][j]* *///初始化11111111111111111111111111111111//在第0天刚开始//own[0][0]第0天最终的状态就是买入当天的股票own[0][0]=-prices[0];buy[0][0]=0;//可买入状态,就是什么都不做final int INF=0x3f3f3f3f;//常用的最大值for (int j = 1; j <3 ; j++) {own[0][j]=Integer.MIN_VALUE/2;buy[0][j]=Integer.MIN_VALUE/2;}for (int i = 1; i <n; i++) {for (int j = 0; j <3 ; j++) {/**套状态方程1*/own[i][j]=Math.max(own[i-1][j],buy[i-1][j]-prices[i]);/**套状态方程2*/buy[i][j]=buy[i-1][j];//如果j>=1在考虑own的状态转移if(j-1>=0)buy[i][j]=Math.max(own[i-1][j-1]+prices[i],buy[i][j]);}}//遍历可交易(把股票都卖了)的0次、1次、2次交易的最大值return Math.max(buy[n-1][0],Math.max(buy[n-1][1],buy[n-1][2]));}
}


http://www.mrgr.cn/news/15118.html

相关文章:

  • iOS/iPadOS18.1Beta3发布,新增通知摘要和AI消除功能
  • 基于web旅游信息平台的设计与实现
  • 后端微服务架构:构建分布式博客系统
  • 武器弹药制造5G智能工厂物联数字孪生平台,推进制造业数字化转型
  • YOLO | YOLO目标检测算法(YOLO-V1)
  • 趣味算法------过河卒
  • wpf datagrid 使单元格获得焦点
  • 【Linux】05.Linux 下的编辑器——vim
  • js | XMLHttpRequest
  • Nuxt3入门:介绍、项目安装和了解视图(第一节)
  • CURE算法原理及Python实践
  • Python 开放端口进行数据传输
  • 设计模式-适配器模式
  • Linux:NAT等相关问题
  • go 切片slice学习总结
  • SQLi-LABS通关攻略【26-30关】
  • PHP伪协议
  • Nginx负载均衡中动态资源缓存配置指南
  • Vulkan进阶系列1 - Raytracing 光线查询
  • 51单片机最快能生成多高频率的方波?