【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]));}
}