【重拾算法~Leetcode每日一题】309.最佳买卖股票时机含冷冻期（难度：中等）

309. 最佳买卖股票时机含冷冻期
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易(多次买卖一支股票)：

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

首先最一开始的想法，我在第i天可能有两种情况：①持股②不持股，而不持股又分为两种：①处于冷冻期（即前一天刚卖过股票）②不处于冷冻期
我们从前往后推（从后往前推也行，但是容易遗漏状态），第i-1天有三种状态：①持股②不持股但处于冷冻期③不持股且不处于冷冻期，可以推出经过某种操作得到第i天的3种状态

就像一阶马尔科夫信源一样，当前状态仅取决于前一状态和前一状态下进行的操作。
那么我们就有了最简单的处理办法，使用动态规划，将所有可能的状态从前往后推，如果我在第i天，处于第k种状态，我的总收益为f[i][k]，实际上这个f[i][k]是由f[i-1][0]，f[i-1][1], f[i-1][2]这三种状态决定的。
比如我处于第5天第3种状态（不持股，无冷冻期），那么我的第4天可能有以下情况：

1. 处于第2种状态（不持股，有冷冻期）且不进行操作
2. 处于第3种状态（不持股，无冷冻期）且不进行操作

那么我如何选择应处于那种状态呢，正如题目所说的【最大利润】，假如我如果处于情况1，已经受益了两块八毛钱，处于情况2，已经受益了三块一毛钱，那我肯定选择情况2
也就是说我的受益f[i][k] 等于前一天 f[i-1][0]，f[i-1][1], f[i-1][2]这三种状态中可能到达我当前状态k，且盈利最多的一个【注意买入和卖出时对应受益的变化】。
最后我们要考虑的只有初始状态了：

1. 如果我在一开始的时候买入股票，我的总收益就是-prices[0]
2. 如果我在一开始的时候未买入股票，我的总收益就是0

PS：由于状态变化需要，我需要初始化第一天处于冷冻期时的总收益，但是实际上这个情况是不会出现的，因为我这是我的第一天，不可能处于冷却期，根据状态变化，我后一天如果处于状态3（不持股，无冷冻期），是可以经过前一天的状态2（不持股，有冷冻期）和状态3（不持股，无冷冻期）得来，由于我需要取其中的最大值，所以把第一天的状态2初始化为一个小于等于0的数即可。

class Solution: 
    def maxProfit(self, prices: List[int]) -> int:  #prices这个数组表示第i天的股票价格
        if prices == []:
            return 0
        n = len(prices)
        f = [ [-prices[0],0,0] ] + [ [0,0,0] for i in range (n-1) ]
        for i in range (1,n):
            f[i][0] = max( f[i-1][0],f[i-1][2]-prices[i] )
            f[i][1] =      f[i-1][0]+prices[i] 
            f[i][2] = max( f[i-1][1],f[i-1][2] )
        return max(f[n-1][0],f[n-1][1],f[n-1][2])

在内存消耗这一项，由于其状态转移特性，在计算第i天的状态时，只需考虑第i-1天的状态，之前的状态都可以抛弃，所以进行内存优化：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if prices == []:
            return 0
        n = len(prices)
        f0,f1,f2 = -prices[0],0,0   #把用于存储的数组换成单个变量
        for i in range (1,n):
            f0_new = max(f0,f2-prices[i])
            f1_new =     f0+prices[i]
            f2_new = max(f1,f2)
            f0,f1,f2 = f0_new,f1_new,f2_new
        return max(f1,f2)

但是最终结果好像也没有太大区别QAQ