Leetcode309、最佳买卖股票时机含冷冻期-依旧仅仅考虑两种状态

╰+哭是因爲堅強的太久メ 2023-01-08 10:25 98阅读 0赞

# 最佳买卖股票时机含冷冻期-dp前两天的状态 #

#### 思路解释: ####

因为该题目中存在冷冻期,因此我们在考虑当前持有股票的最大利润的时候要进行特殊考虑–**我们考虑前一天持有股票的最大利润与前两天不持有股票今天买股票的最大利润中的最大值即可**。

#### 理由: ####

**情况一:** 如果前一天不持股票的最大利润来自于前两天不持股票的最大利润。那么这两天不持股票的最大利润是相等的，我们考虑前一天的与考虑前两天的结果是相同的，**故当天持有股票的最大利润来自于前一天持有股票的最大利润与前两天不持有股票今天买股票的最大利润中的最大值即可。**  
**情况二:** 如果前一天不持股票的最大利润来自于前一天卖出股票的最大利润，**那么当天的持有股票的最大利润只能来自于前一天持有股票的最大利润与前两天不持有股票今天买股票的最大利润中的最大值。**

#### 代码 ####

**说明:文中的注释部分可以直接忽略**  
注释部分为第一次在考虑时尝试对前一天不持股票的最大值来自于前一天卖出股票的天进行标记来进行转移。

class Solution {
        
        public int maxProfit(int[] prices) {
        
        	// 考虑如果当前没有的最大利润是在上天卖出的 
        	//那么当前持有的最大利润一定是之前持有的最大利润与前两天不持有今天持有的最大利润
        	int n=prices.length;
            if(n==0) return 0;
        	//int[] record=new int[n];
        	int[][] dp=new int[n][2];
        	dp[0][0]=0; dp[0][1]=-prices[0];
        	for(int i=1;i<n;i++) {
        
        		/*//先计算当前不持有的最大利润
        		if(dp[i-1][0]>=dp[i-1][1]+prices[i]) {
        			dp[i][0]=dp[i-1][0];
        		}
        		else {
        			dp[i][0]=dp[i-1][1]+prices[i];
        			record[i]=1;
        		}
        		//开始计算当前持有的最大利润
        		if(record[i-1]==1) {
        			dp[i][1]=Math.max(dp[i-1][1], dp[i-2][0]-prices[i]);
        		}
        		else {
        			dp[i][1]=Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);
        		}*/
                dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
                if(i>1) dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0]-prices[i]);
        	    else dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            }
        	return dp[n-1][0];
        }
    }