LeetCode每日一题: 309. 最佳买卖股票时机含冷冻期

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

标签: 动态规划

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

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

思路

1. 划分阶段: 
    - 3个阶段, 开始阶段, 状态转移阶段, 结束阶段
2. 确定状态和状态变量
    - 状态: 持股, 不持股, 卖出(第二天进入冷冻期)
    - 状态变量: 记录n-1天持股/不持股状态下的最大利润, 以及n-2天的冷冻卖出状态下的最大利润, 才能时第n天的决策完整无误
3. 状态转移决策: 
    - 0 不持股状态:      当前不持股 = max(前2天卖出->不持股, 不持股->不持股)
    - 1 持股状态:       当天持股 = max(持股, 持股->持股, 不持股->持股, 前2天卖出->持股)
    - 2 卖出状态:       卖出 = 持股->卖出
4. 边界条件
    - 第1天和第2天为边界条件, 因为只有1天不能完成交易, 2天可以完成一次交易, 提供状态信息

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])