最佳买卖股票时期含冷冻期(102min)

题目链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

题目

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:

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

题解

这道题，肯定也是在低买入，高卖出，但是难在卖完不能立马就再次买入，需要等一天后，再次买入。

真是看了半天题解，在看了一个高手画状态机后，才有点明白咋回事，但是还是不太明白，怎么想到这三种状态的，首先先来一个状态机的图，图中S0表示手里没有股票，但是可以买入股票，S1表示手里有股票，S2表示手里没有股票，但是不能买入股票，也就是题目中处于冷冻期。

由以上的状态机可以得出动态规划的状态转移方程：

S0={S0，S0前一个S2}

S1={S1前一个S0-买入的股票价格，S1}

S2={S2前一个S1+卖出的股票价格}

设S[i][0]代表S0状态，S[i][1]代表S1状态，S[i][2]代表S2状态，w代表股票的价格，则状态转移方程为：

S[i][0]=max{S[i-1][0],S[i-1][2]}

S[i][1]=max{S[i-1][0]-w,S[i-1][1]}

S[i][2]=S[i-1][1]+w

初始条件为：

S[0][0]=0;

S[0][1]=买了第一天的股票

S[0][2]=0；

结束条件：手里没有股票或者是有股票的最大收益。

错误尝试

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==0)
        return 0;
        int [][]S=new int [prices.length][3];
        S[0][0]=0;
        S[0][1]=-prices[0];
        S[0][2]=0; 
        for(int i=1;i<prices.length;i++) 
        {
            S[i][0]=Math.max(S[i-1][0],S[i-1][2]);
            S[i][1]=Math.max(S[i-1][0]-prices[i],S[i-1][1]);
            S[i][2]=S[i-1][1]+prices[i];
        }
        return Math.max(S[prices.length-1][1],S[prices.length-1][2]);
    }
}

写到这里才发现返回值写错了，应该返回没有持股票的两种状态下的最大值，因为持有股票一定是把钱买股票了，收益肯定不是最大了。

正确代码

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==0)
        return 0;
        int [][]S=new int [prices.length][3];
        S[0][0]=0;
        S[0][1]=-prices[0];
        S[0][2]=0; 
        for(int i=1;i<prices.length;i++) 
        {
            S[i][0]=Math.max(S[i-1][0],S[i-1][2]);
            S[i][1]=Math.max(S[i-1][0]-prices[i],S[i-1][1]);
            S[i][2]=S[i-1][1]+prices[i];
        }
        return Math.max(S[prices.length-1][0],S[prices.length-1][2]);
    }
}

正确结果

出来混总是要还的