[LeetCode in Python] 309 (M) best time to buy and sell stock with cooldown 最佳买卖股票时机含冷冻期

题目：

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

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

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

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

示例:

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

解题思路

• DP
• 设置两个状态，hold[i]和unhold[i]，分别表示第i天时持有及未持有股票的最大利润
• 计算base state，分别写出i=0和i=1的结果
• 写出递推公式，因为有冷冻期，所以前推用到i-2和i-1的值

代码

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # - sanity check
        if (not prices) or (len(prices)==1):
            return 0

        n = len(prices)

        # - dp state
        # - hold[i] means max profit if hold stock at day i
        # - unhold[i] means max profit if not hold stock at day i
        hold = [0] * n
        unhold = [0] * n

        # - base state

        # - hold at day 0 means buy at day 0
        hold[0] = -prices[0]

        # - hold at day 1 means:
        # -   buy at day 0, do nothing at day 1
        # -   or do nothing at day 0, and buy at day 1
        hold[1] = max(-prices[0], -prices[1])

        # - unhold at day 0
        unhold[0] = 0

        # - unhold at day 1 means:
        # -     do nothing at day 0 and day 1
        # -     buy at day 0 and sell at day 1
        unhold[1] = max(0, hold[0]+prices[1])

        # - dp formula

        # - hold[i] = max of
        # -     hold at day i-1, do nothing at day i
        # -     unhold at day i-2, do nothing at day i-1, buy at day i
        # - hold[i] = max(hold[i-1], (unhold[i-2] - prices[i]))

        # - unhold[i] = max of
        # -     unhold at day i-1, do nothing at day i
        # -     hold at day i-1, sell at day i
        # - unhold[i] = max(unhold[i-1], (hold[i-1] + prices[i]))

        for i in range(2, n):
            hold[i] = max(hold[i-1], (unhold[i-2] - prices[i]))
            unhold[i] = max(unhold[i-1], (hold[i-1] + prices[i]))

        return max(hold[n-1], unhold[n-1])