最佳买卖股票时机(含冷冻期)[动态规划]

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

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

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

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

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

分析：
【思路】：将股票的买入和卖出分开进行考虑：【买入】为负收益，【卖出】为正收益。在初入股市的时候，只有【买入】的权利，只能获得负收益。当【买入】以后，才有【卖出】的权利，可以获得正收益。我们需要尽可能的降低负收益而提高正收益，因此目标就是将收益值最大化。可以使用动态规划，维护每天股市中结束以后的【累计最大收益】，并以此进行状态转移，得到最终答案；

【动态规划】：<br />    采用profit_dp[i]表示【第i天结束以后】的【累计最大收益】。由于最多只能同时买入(持有)一只股票，并且卖出股票以后有冷冻期的限制，因此最后会有三种不同的状态：<br />    * 目前持有一支股票，对应的【累计最大收益】为profit_dp[i][0];<br />    * 目前不持有股票，并且处于冷冻期，对应的【累计最大收益】为profit_dp[i][1];<br />    * 目前不持有股票，并且不处于冷冻期，对应的【累计最大收益】为profit_dp[i][2];
【状态转移】<br />    在不违反规则的前提下，第i天状态从第i-1天转移而来;<br />    1、对于profit_dp[i][0], 目前持有一支股票，可以是第i-1天已经持有的，对应为profit_dp[i-1][0],也可以是第i天买入的；此时第i-1天不能处于冷冻期，对应的状态对profit[i-1][2]加上买股票的负收益prices[i];状态转移方程为：<br />                profit_dp[i][0] = max(profit_dp[i-1][0], profit_dp[i][2] - prices[i])<br />    2、对于profit_dp[i][1], 在第i天结束以后处于冷冻期，原因是当天卖出了股票，说明第i-1天必须持有一支股票。对应的状态为profit_dp[i-1][1]加上卖股票的收益prices[i]; 状态转移方程为：<br />                profit_dp[i][1] = profit_dp[i-1][1] + prices[i]<br />    3、对于profit_dp[i][2]，在第i天结束以后不持有任何股票并且不处于冷冻期，说明当天没有进行任何操作，说明第i-1天不持有任何股票；如果不处于冷冻期，对应状态为profit_dp[i-1][2], 如果处于冷冻期，对应状态为profit_dp[i-1][1]; 状态转移方程：<br />                profit_dp[i][2] = max(profit_dp[i-1][1], profit_dp[i-1][2])<br />    <br />    【最大收益】：最大收益为max(profit_dp[n-1][0], profit_dp[n-1][1], profit_dp[n-1][2])<br />    但其实最后一天结束以后，手上持有股票是没有意义的。因此更加精确的最大收益是：max(profit_dp[n-1][1], profit_dp[n-1][2])
【状态初始化】<br />    第0天作为动态规划的边界条件：<br />                profit_dp[0][0] = -prices[0]    // 买入为负收益<br />                profit_dp[0][1] = 0;<br />                profit_dp[0][2] = 0;

int maxProfit(vector<int>& prices) {
    if (prices.empty())
        return 0;
    int n = prices.size();
    vector<vector<int>> profit_dp(n, vector<int>(3));
    profit_dp[0][0] = -prices[0];
    for(int i = 1; i < n; ++i){
        profit_dp[i][0] = max(profit_dp[i-1][0], profit_dp[i-1][2]-prices[i]);
        profit_dp[i][1] = profit_dp[i-1][0] + prices[i];
        profit_dp[i][2] = max(profit_dp[i-1][1], profit_dp[i-1][2]);
    }
    return max(profit_dp[n-1][1], profit_dp[n-1][2]);
}

// **内存优化:**<br />    // 状态转移方程中的profit_dp[i]只与profit_dp[i-1]有关，<br />    // 可以设置3个状态记录profit_dp[i-1]对应的三个状态<br /> 

int maxProfit(vector<int> & prices){
    if (prices.empty())
        return 0;
    int n = prices.size();
    int status_0 = -prices[0];
    int status_1 = 0;
    int status_2 = 0;
    for(int i=1; i<n; ++i){
        int new_status_0 = max(status_0, status_2 - prices[i]);
        int new_status_1 = status_0 + prices[i];
        int new_status_2 = max(status_1, status_2);
        status_0 = new_status_0;
        status_1 = new_status_1;
        status_2 = new_status_2;
    }
    return max(status_1, status_2);
}