题目链接:123. 买卖股票的最佳时机 III - 力扣(LeetCode)
前情提要:
本题是由122. 买卖股票的最佳时机 II - 力扣(LeetCode)变形而来,122是只能买卖多次股票,该题是只能买卖俩次股票,我相信当你做完这道题或者看完我上道题的题解力扣122.-买卖股票的最佳时机 II(Java详细题解)-CSDN博客,那么写这道题会轻松一点。
因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。
dp五部曲。
1.确定dp数组和i下标的含义。
2.确定递推公式。
3.dp初始化。
4.确定dp的遍历顺序。
5.如果没有ac打印dp数组 利于debug。
每一个dp题目如果都用这五步分析清楚,那么这道题就能解出来了。
题目思路:
买卖股票的最佳时机 II是可以买卖俩次,而本题是固定买卖俩次,那我怎么确定本次持股是第一次持股还是第二次呢?
关键在于至多买卖两次,这意味着可以买卖一次,可以买卖两次,也可以不买卖。
那么本题的状态就有所改变了,我们要设立五个状态才能表示所有的状态。
dp[i] [0] 表示 不操作
dp[i] [1] 表示 下标为i天 第一次持股的手头上的最大现金。
dp[i] [2] 表示 下标为i天 第一次不持股的手头上的最大现金。
dp[i] [3] 表示 下标为i天 第二次持股的手头上的最大现金。
dp[i] [4] 表示 下标为i天 第二次不持股的手头上的最大现金。
那么我们用dp五部曲来系统分析一下。
1.确定dp数组和i下标的含义。
dp[i] [0] 表示 不操作
dp[i] [1] 表示 下标为i天 第一次持股的手头上的最大现金。
dp[i] [2] 表示 下标为i天 第一次不持股的手头上的最大现金。
dp[i] [3] 表示 下标为i天 第二次持股的手头上的最大现金。
dp[i] [4] 表示 下标为i天 第二次不持股的手头上的最大现金。
2.确定递推公式。
我们定义的dp状态是由什么推出来的呢?
dp[i] [1] 表示 下标为i天 第一次持股的状态。
达到dp[i] [1]状态,有两个具体操作:
- 操作一:第i天买入股票了,那么dp[i] [1] = dp[i-1] [0] - prices[i]
- 操作二:第i天没有操作,而是沿用前一天买入的状态,即:dp[i] [1] = dp[i - 1] [1]
那么dp[i] [1]究竟选 dp[i-1] [0] - prices[i],还是dp[i - 1] [1]呢?
一定是选最大的,所以 dp[i] [1] = Math.max(dp[i-1] [0] - prices[i], dp[i - 1 ] [1]);
同理dp[i] [2]也有两个操作:
- 操作一:第i天卖出股票了,那么dp[i] [ 2] = dp[i - 1] [1] + prices[i]
- 操作二:第i天没有操作,沿用前一天卖出股票的状态,即:dp[i] [2] = dp[i - 1] [2]
所以dp[i] [2] = Math.max(dp[i - 1] [1] + prices[i], dp[i - 1] [2])
同理可推出剩下状态部分:
dp[i] [3] = Math.max(dp[i - 1] [3], dp[i - 1] [2] - prices[i]);
dp[i] [4] = Math.max(dp[i - 1] [4], dp[i - 1] [3] + prices[i]);
3.dp初始化。
由递推公式可以看出dp[i] [1] = Math.max(dp[i-1] [0] - prices[i], dp[i - 1 ] [1]);
dp[i]都是需要dp[i - 1]的,所以所有状态的起始是i 为 0。
所以我们应该初始化i为0的四种状态。
dp[0] [1] 表示下标为0天第一次持股 那肯定就是当天买入股票 就为 -prices[0]
dp[0] [2] 表示下标为0天第一次不持股 那就是当天买入股票再卖出 就为0
dp[0] [3] 表示下标为0天第二次持股 那就是第一买卖结束后 再买入股票 也是 -prices[0]
dp[0] [4] 表示下标为0天第二次不持股 当天第二次买入股票再卖出 也为0
4.确定dp的遍历顺序。
由递推公式可以看出dp[i] [1] = Math.max(dp[i-1] [0] - prices[i], dp[i - 1 ] [1]);
每一个状态需要他前一个的状态,所以我们需要从前往后遍历,才能利用好他前一个的状态。
5.如果没有ac打印dp数组 利于debug。
由这里可以看出我们收集结果的地方为dp[4] [4]为第二次不持股手上的最大现金,这是为什么?
现在确定的是不持股的手上现金肯定比持股手上的最大现金多。因为你不持股是能买股票卖出的,你持股只能买入股票,所以你手上的现金肯定小与卖出股票的。
那么我们要比较的就是第一次不持股和第二次不持股手上的最大现金。
其实应该是第二次不持股手上的最大现金大于等于第一次,如果第一次卖出已经是最大值了,那么我们第一次买卖股票可以在第一次卖出股票的当天立刻买入再立刻卖出。所以dp[4 ] [4]已经包含了dp[4] [2]的情况。也就是说第二次卖出手里所剩的钱一定是最多的。
最终代码:
class Solution {
public int maxProfit(int[] prices) {
//该题是让我们最多完成俩笔买卖 所以我们只要多推导几个状态即可
//定义dp数组
int [][] dp = new int [prices.length + 1][5];
//初始化
dp[0][1] = -prices[0];
dp[0][2] = 0;
dp[0][3] = -prices[0];
dp[0][4] = 0;
//dp遍历顺序
for(int i = 1;i < prices.length;i ++){
//递推公式
dp[i][1] = Math.max(dp[i - 1][1],-prices[i]);
dp[i][2] = Math.max(dp[i - 1][2],dp[i - 1][1] + prices[i]);
dp[i][3] = Math.max(dp[i - 1][3],dp[i - 1][2] - prices[i]);
dp[i][4] = Math.max(dp[i - 1][4],dp[i - 1][3] + prices[i]);
}
//返回第二次不持股手上的最大现金
return dp[prices.length - 1][4];
}
}
这一篇博客就到这了,如果你有什么疑问和想法可以打在评论区,或者私信我。
我很乐意为你解答。那么我们下篇再见!