本文主要是介绍【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]));}
}
这篇关于【dp力扣】买卖股票的最佳时机III的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!