309. 最佳買賣股票時機含冷凍期

標簽: 動態(tài)規(guī)劃

給定一個整數(shù)數(shù)組，其中第 i 個元素代表了第 i 天的股票價格 。?
設計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:
你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。

示例:
輸入: [1,2,3,0,2]
輸出: 3
解釋: 對應的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]

思路

1. 劃分階段: 
    - 3個階段, 開始階段, 狀態(tài)轉移階段, 結束階段
2. 確定狀態(tài)和狀態(tài)變量
    - 狀態(tài): 持股, 不持股, 賣出(第二天進入冷凍期)
    - 狀態(tài)變量: 記錄n-1天持股/不持股狀態(tài)下的最大利潤, 以及n-2天的冷凍賣出狀態(tài)下的最大利潤, 才能時第n天的決策完整無誤
3. 狀態(tài)轉移決策: 
    - 0 不持股狀態(tài):      當前不持股 = max(前2天賣出->不持股, 不持股->不持股)
    - 1 持股狀態(tài):       當天持股 = max(持股, 持股->持股, 不持股->持股, 前2天賣出->持股)
    - 2 賣出狀態(tài):       賣出 = 持股->賣出
4. 邊界條件
    - 第1天和第2天為邊界條件, 因為只有1天不能完成交易, 2天可以完成一次交易, 提供狀態(tài)信息

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0

        lst = []
        lst.append([0,-prices[0],0]) 
        lst.append([0,max(-prices[0],-prices[1]),prices[1]-prices[0]])

        for i in range(2, len(prices)):
            lst.append([])
            # 不持股, 前2天賣出->不持股, 不持股->不持股
            lst[i].append(max(lst[i-1][0], lst[i-2][2]))
            # 持股, 持股->持股, 不持股->持股, 前2天賣出->持股
            lst[i].append(max(lst[i-1][1], lst[i-1][0]-prices[i], lst[i-2][2]-prices[i]))
            # 賣出, 持股->賣出
            lst[i].append(lst[i-1][1]+prices[i])
        return max(lst[-1]+lst[-2])