力扣笔记（每日随机一题）——最佳买卖股票时机含冷冻期
问题（中等）
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
示例 1
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2
输入: prices = [1]
输出: 0
提示：
1 < = p r i c e s . l e n g t h < = 5000 1 <= prices.length <= 5000 1<=prices.length<=5000
0 < = p r i c e s [ i ] < = 1000 0 <= prices[i] <= 1000 0<=prices[i]<=1000
解题
思路
（BP问题太折磨了，思路参考官方解答）
每一天可以有三个状态：买、卖和冷冻期；
temp[i]表示截至第i天，最后一个操作是卖时的最大收益；
buy[i]表示截至第i天，最后一个操作是买时的最大收益；
frozen[i]表示截至第i天，最后一个操作是冷冻期时的最大收益；
递推公式：
temp[i] = max(buy[i-1]+prices[i], temp[i-1]) (第一项表示第i天卖出，第二项表示第i天冷冻)
buy[i] = max(frozen[i-1]-prices[i], buy[i-1]) （第一项表示第i天买进，第二项表示第i天冷冻）
frozen[i] = max(temp[i-1], buy[i-1], frozen[i-1])
代码实现
class Solution:def maxProfit(self, prices: List[int]) -> int:n = len(prices)if n == 0:return 0 temp = [0]*nbuy = [0]*nfrozen = [0]*nbuy[0] = -prices[0]for i in range(1,n):temp[i] = max(buy[i-1] + prices[i], temp[i-1])buy[i] = max(frozen[i-1] - prices[i], buy[i-1])frozen[i] = max(temp[i-1], buy[i-1],frozen[i-1])return temp[-1]
