当前位置：首页 > article >正文

力扣122.-买卖股票的最佳时机 II（Java详细题解）

article 2024/11/14 19:31:30

题目链接：122. 买卖股票的最佳时机 II - 力扣（LeetCode）

前情提要：

本题是由121. 买卖股票的最佳时机 - 力扣（LeetCode）变形而来，121是只能买卖一次股票，该题是可以买卖多次股票，我相信当你做完这道题或者看完我上道题的题解，力扣121-买卖股票的最佳时机（Java详细题解）-CSDN博客

那么写这道题会轻松很多。

因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。

dp五部曲。

1.确定dp数组和i下标的含义。

2.确定递推公式。

3.dp初始化。

4.确定dp的遍历顺序。

5.如果没有ac打印dp数组利于debug。

每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。

题目思路:

该题唯一的区别就是与121买卖股票的次数不同，该题是可以买卖多次股票，所以我们就对递推公式进行修改即可。就不用dp五部曲分析了。

121的递推公式如下：

下标为i天持股手上的最大现金的状态可以由俩个状态推出。

我当天持股可能我前一天也是持股的状态，也可能是我当天买入股票的状态。

dp[i] [0] = Math.max(dp[i - 1] [0],-prices[i]);

dp[i] [1] = Math.max(dp[i - 1] [1],dp[i - 1] [0] + prices[i]);

下标为i天不持股手上的最大现金的状态也可以由俩个状态推出。

我当天不持股可能我前一天也是不持股的状态，也可能是我当天卖出股票的状态。

我当天卖出，那我的前一天肯定是持股的状态，那我就将前一天持股手上的最大现金加上我当天卖出的股票最大现金，也就是我的最大不持股的现金（所得的利润）。

由于只能买卖一次，所以我在当天买入股票的状态肯定是 0 - prices[i];

但是该题可以买卖多次，那我买入股票的时候可能前面已经进行过一次买卖了，那我手上的现金就不是0了，就为上一次买卖后所得的最大现金。

那我第二次再买股票的时候，我就要将上一次买卖后所得的最大现金减去当前买入股票的价格即可。

那买卖多次也同理。

所以该题的递推公式就为：

p[i] [0] = Math.max(dp[i - 1] [0],dp[i - 1] [1] - prices[i]);

dp[i] [1] = Math.max(dp[i - 1] [1],dp[i - 1] [0] + prices[i]);

dp[i - 1] [1]就是指上一次不持股手上的最大现金。也就是可能是上一次买卖后所得的最大现金。

其他与121无异。

最终代码：

class Solution {
    public int maxProfit(int[] prices) {
        //买卖股票一次和多次的区别在于持股的状态公式，因为之前买卖一次的时候，我在买股票之前的现金为0，所以持股时期就是为0 - prices[i]
        //而现在可以买入多次，可能我这次手头的现金已经是上次买卖完股票后所得的最大现金了 所以这次我所得的买股的状态转换方程为
        //第i天之前已经持股 那就是dp[i - 1][0]
        //如果是当天买入的股票 就是dp[i - 1][1] - prices[i]
         int [][] dp = new int [prices.length + 1][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i = 1;i < prices.length;i ++){
            dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] + prices[i]);
        }
        //最后一天的不持股（没有股票，可能在最后一天之前就已经卖了）得到的现金因为递推公式，被前面最大的卖出股票的价格所覆盖了，所以获得的最大利润就为dp[prices.length - 1][1]
        //在本题持股的最大现金一定为负数，所以得的最大值就是不持股的最大现金
        return dp[prices.length - 1][1];
    }
}