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

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

解法一：状态机dp

k 为正无穷，参考122. 买卖股票的最佳时机，只是多了冷冻期一天的条件，状态方程变为

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])
解释：第 i 天选择 `buy` 的时候，要从 i-2 的状态转移，而不是 i-1 。

初始条件：

dp[0][0] = 0, dp[0][1] = -∞
由状态方程1推得dp[0][1] = max(dp[0][0], dp[0][1] + prices[i])
                      = max(0, -∞) = 0
易推知dp[1][1] = -prices[i] （解释：第1天持有，只能是以第1天价格买入）

直接出代码：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0:
            return 0
        dp = [[0] * 2 for _ in range(n + 1)] 
        for i in range(n+1):
            if i == 0:
                dp[i][0] = 0
                dp[i][1] = -sys.maxsize
                continue
            if i == 1:
                dp[i][0] = 0
                dp[i][1] = -prices[i-1]
                continue
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1])
            dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i-1])
        print(dp)
        return dp[n][0]