LeetCode100之买卖股票的最佳时机含冷冻期(309)--Java

标签：309 状态 -- 股票 LeetCode100 max prices 冷冻 dp

1.问题描述

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

示例1

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例2

输入: prices = [1]
输出: 0

提示

1 <= prices.length <= 5000
0 <= prices[i] <= 1000

难度等级

中等

题目链接

买卖股票的最佳时机含冷冻期

2.解题思路

这道股市市场交易的题目我们得用动态规划的思想来解决，有点困难，因为加入冷冻期之后，股票的状态有点多，不过没关系，我们一步一步来分析。

在这道题里面，一共有四种状态，第一种是持有股票的状态，第二种是不持有股票的状态，第三种当天卖出股票的状态，第四种是冷冻期的状态。

首先第一步，我们得有一个dp数组。创建一个dp[prices.length][4]的数组，dp数组的含义是第i天第k种状态的收益。在这道题里我们一共有4种状态，0 表示持有股票的状态、1 表示不持有股票的状态、2 表示当天卖出股票的状态、3 表示冷冻期的状态。如果一开始不知道有多少种状态，可以向空着，一步一步分析完再来填写。

        //dp数组:第i天股票第k种状态的收益
        int[][] dp = new int[prices.length][4];

明确了dp数组的含义之后，我们接下来就要确定递推公式。我们先从简单的开始入手。

如果当天是冷冻期的状态，那么前一天一定是卖出了股票，所以我们就可以得到冷冻期状态的递推公式：dp[i][3] = dp[i-1][2]。

            //今天是冷冻期状态
            dp[i][3] = dp[i-1][2];

如果当天是卖出股票的状态，那么前一天一定持有股票，卖出股票就能够得到收益，所以我们也可以得到当天卖出股票状态的递推公式：dp[i][2] = dp[i-1][0] + prices[i]。

            //今天卖出状态
            dp[i][2] = dp[i-1][0] + prices[i];

如果当天是不持有股票的状态，那么可能是前一天我们卖出了股票(dp[i-1][2])，也可能是前一天是冷冻期(dp[i-1][3])，还有可能前一天我们本来就不持有股票(dp[i-1][1])，所以我们也可以得到不持有股票状态的递推公式:dp[i][1] = max(dp[i-1][2],dp[i-1][3],dp[i-1][1])。

            //不持有股票的状态
            dp[i][1] = Math.max(Math.max(dp[i-1][1],dp[i-1][3]),dp[i-1][2]);

如果当天是持有股票的状态，那么可能是我们前一天就持有股票(dp[i-1][0])，也可能是我们前一天是冷冻期，过了冷冻期今天买股票，买股票是要扣钱的(dp[i-1][3] - prices[i])，还有一种可能是我们前一天不是冷冻期但是也没有持有股票，然后今天买股票(dp[i-1][1] - prices[i])。

            //持有股票状态
            dp[i][0] = Math.max(Math.max(dp[i-1][0],dp[i-1][1] - prices[i]),dp[i-1][3] - prices[i]);

这样一通分析，我们的递推公式就全部出来了，接着我们就要来初始化一下我们的dp数组。根据dp数组的含义和我们四个状态的递推公式，来初始化。还是从简单的开始来。冷冻期状态，我们没有-1天，所以第0天不可能是冷冻期，初始化为0。卖出股票状态，我们第0天还没开始操作了，所以也初始化为0。不持有股票的状态，我们第0天肯定是持有股票的，这是不然都没办法交易，所以也初始化为0。持有股票的状态，我们第0天肯定要持有股票，才有后续的操作，所以第0天我们要买入股票，初始化为-prices[0]。这样一来，我们的初始化就全部完成了。

        //初始化dp数组
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;

接着只要遍历数组，递推公式进行推到即可。最大的收益可能在不持有股票，今天卖出股票和冷冻期中的其中一个，我们去最后一天这三个的最大值就可以了。为什么没有状态一持有股票呢？因为卖掉肯定赚钱，买还要倒扣钱。

        return Math.max(Math.max(dp[prices.length-1][3],dp[prices.length-1][1]),dp[prices.length-1][2]);

3.代码展示

class Solution {
    public int maxProfit(int[] prices) {
        //dp数组:第i天股票第k种状态的收益
        int[][] dp = new int[prices.length][4];
        //初始化dp数组
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;
        //遍历
        for(int i = 1;i < prices.length;i++){
            //持有股票状态
            dp[i][0] = Math.max(Math.max(dp[i-1][0],dp[i-1][1] - prices[i]),dp[i-1][3] - prices[i]);
            //不持有股票的状态
            dp[i][1] = Math.max(Math.max(dp[i-1][1],dp[i-1][3]),dp[i-1][2]);
            //今天卖出状态
            dp[i][2] = dp[i-1][0] + prices[i];
            //今天是冷冻期状态
            dp[i][3] = dp[i-1][2];
        }
        return Math.max(Math.max(dp[prices.length-1][3],dp[prices.length-1][1]),dp[prices.length-1][2]);
    }
}

4.总结

这道题比较难的地方就在于状态比较多，我们需要耐心的分析出各个状态的情况和如何初始化，分析完之后，这道题其实也就解决了大半了。我们一共有四种状态，持有股票、不持有股票、当天卖出和冷冻期，状态较多，我们可以从容易的开始，一步一步逐个击破。我在昨天发的一道MarsCode的题(股票市场交易策略优化)和这道题完全一模一样，只是变量名和描述换了而已，大家也可以去做一下那道题。好了，今天这道题就讲到这里了，祝大家刷题愉快~

标签：309,状态,--,股票,LeetCode100,max,prices,冷冻,dp
From： https://blog.csdn.net/2301_79318558/article/details/143449840