LeetCode-309-最佳买卖股票时机含冷冻期

解题思路1：

1. 第i天可能有三种状态：持仓dp[i][0]、空仓且冷冻期dp[i][1]、空仓非冷冻期dp[i][2]
2. 第i天持仓dp[i][0]由两种状态转移过来：即昨天持仓今天继续dp[i-1][0]、昨天空仓非冷冻期+今天买入dp[i-1][2]-prices[i]
3. 第i天空仓且冷冻期dp[i][1]由一种状态转移过来：即昨天持仓+今天卖出dp[i-1][0] + prices[i]
4. 第i天空仓且在非冷冻期dp[i][2]由两种状态转移过来：昨天冷冻期今天非冷冻dp[i-1][1]、昨天非冷冻今天也非冷冻dp[i-1][2]

python3代码如下：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        dp = [[0 for _ in range(3)] for _ in range(len(prices))]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        dp[0][2] = 0

        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][2]-prices[i])  # 昨天持仓、昨天空仓非冷冻+今天买入
            dp[i][1] = dp[i-1][0] + prices[i]  # 昨天持仓+今天卖出
            dp[i][2] = max(dp[i-1][1],dp[i-1][2])  # 昨天冷冻期今天非冷冻、昨天非冷冻今天也非冷冻 
        return max(dp[-1][1], dp[-1][2])

解题思路2：

1. 只有两种状态，即持仓和空仓
2. 当日空仓 = max(昨天空仓，昨天持仓+今天卖出）
3. 当日持仓 = max(昨天持仓，前天卖出+今日买入）
4. 需对前两天的收益初始化
   python3代码如下：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices or len(prices)==1:
            return 0
        dp = [[0 for _ in range(2)] for _ in range(len(prices))]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        dp[1][0] = max(dp[0][0], dp[0][1]+prices[1])
        dp[1][1] = max(dp[0][1], -prices[1])

        for i in range(2, len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-2][0]-prices[i])
        return dp[-1][0]