代码随想录 | Day 51 - LeetCode 309.最佳买卖股票时机含冷冻期、LeetCode 714.买卖股票的最佳时机含手续费

        依然是买卖股票问题的延续，分别关于冷冻期和手续费。主要是第1题的冷冻期问题比较复杂。第1题冷冻期意味着状态数的增加；第2题手续费意味着状态转移时手续费要计算在内。

        第1题（LeetCode 309.最佳买卖股票时机含冷冻期）相比day 49中第2题（LeetCode 122.买卖股票的最佳时机II）增加了一天的冷冻期，也就是在每次卖出后，要隔一天后才能再次买入。有了前面的经验，这次自己摸索着做出来了。这道题的重点仍然是状态的定义和划分，状态整体上仍然分为“持有”和“不持有”两大类。其中“不持有”又分为“当天卖出”、“当天是冷冻期”、和“当天已经过了冷冻期”这3种状态，加上“持有”共计4种状态。将“持有”、“当天卖出”、“当天是冷冻期”、和“当天已经过了冷冻期”分别设为状态0~3。

• 对于“持有”状态，其上一状态有可能是自身（dp[i - 1][0]），也可能是“当天是冷冻期”（dp[i - 1][2] - prices[i]）或“当天已经过了冷冻期”（dp[i - 1][3] - prices[i]），所以dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][2], dp[i - 1][3]) - prices[i])；
• 对于“当天卖出”状态，其上一状态只可能是“持有”（dp[i - 1][0] + prices[i]），所以dp[i][1] = dp[i - 1][0] + prices[i]；
• 对于“当天是冷冻期”状态，其上一状态只可能是“当天卖出”（dp[i - 1][1]），所以dp[i][2] = dp[i - 1][1]；
• 对于“当天已经过了冷冻期”状态，其上一状态可能是自身（(dp[i - 1][3]），或“当天是冷冻期”（dp[i - 1][2]），所以max(dp[i - 1][3], dp[i - 1][2])。

        初始化方面，“持有”状态代表第0天就买入股票，对应-prices[0]。而对于3中“不持有”状态，设置为0以不影响后面的比较大小即可。遍历方向同前面几个题一样，也是正向遍历。最后的结果需要从最后一天的3个“不持有”状态中，选择最大的一个返回。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vectorint>> dp(prices.size(), vector<int>(4, 0));
        dp[0][0] = -prices[0];
        int n = prices.size();
        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][2], dp[i - 1][3]) - prices[i]); // 持有
            dp[i][1] = dp[i - 1][0] + prices[i]; // 今天卖出
            dp[i][2] = dp[i - 1][1]; // 今天冷冻期
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2]); // 今天未持有，且已度过冷冻期
        }
        return max(dp[n - 1][1], max(dp[n - 1][2], dp[n - 1][3]));
    }
};

        跟前面的题一样，这道题也可以将空间缩小为只用两行，这里就不写出来了。

        第2天（LeetCode 714.买卖股票的最佳时机含手续费）在day 37中用贪心算法做过一次。这道题相比day 49中第2题（LeetCode 122.买卖股票的最佳时机II）改变了一处地方，就是增加了手续费，每买卖一次都要付一次手续费。所以要做出的相应改变就是，从“持有”状态向“不持有”状态转移时，要减掉手续费，也就是将原本的dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])改为dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)。

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        vectorint>> dp(prices.size(), vector<int>(2, 0));
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[prices.size() - 1][0];
    }
};

        也同样可以参考 day 49中第2题（LeetCode 122.买卖股票的最佳时机II）用节省空间的版本只用2行矩阵实现，这里也不写了。