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