2020-07-10 leetcode 最佳买卖股票时机含冷冻

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

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

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

示例：

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

解题思路：

参考题解动态规划思路，写得非常巧妙。实际上这类涉及到状态转移的问题都可以用DP来解决，第i天之后的累计收入与第i-1天的状态挂钩，根据持股与否和冷冻期，对第i天之后的累计收入f[i]进行分类。

f[i][0]:代表第i天之后，状态为仍然持有股票的累计收入
f[i][1]:代表第i天之后，状态为不持有持有股票，且处于冷冻期的累计收入
f[i][2]:代表第i天之后，状态为不持有股票，且不处于冷冻期的累计收入

有了以上的定义，我们可以来书写状态转移方程：

最后要做的就是比较最后一天时，三种可能状态的累计收入大小:

实际上在最后一天还持有股票时是不明智的，一定不是最大，所以我们只需要比较

即可。

最后，优化空间复杂度，因为状态转移方程表示第i天状态只跟i-1天状态有关，而与历史记录无关，所以我们并不需要二维数组，而仅仅使用三个变量存储并实时更新就好了。

完整代码：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        f0,f1,f2 = -prices[0],0,0
        for i in range(1,len(prices)):
            newf0 = max(f0, f2-prices[i])
            newf1 = f0 + prices[i]
            newf2 = max(f1,f2)
            f0,f1,f2 = newf0,newf1,newf2
        return max(f1,f2)