309. 最佳买卖股票时机含冷冻期
Difficulty
Medium
Tags
动态规划
Star
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2] 输出:3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
法1 动态规划
典型的时间序列题目。定义如下状态
- 0:这轮我刚持有股票的最大收益
- 1:这轮我已持有股票一天以上的最大收益
- 2:这轮我已清空股票的最大收益
状态转移如下：
法2 动态规划
定义状态如下：
dp[i][0] : 第 i 天 持有股票的最大收益dp[i][1]: 第i 天不持有股票的最大收益理解转移方程：
售出状态：
- 可能是当天售出，也肯能是之前售出的
持有状态：
- 可能是当天买入的，也可能是之前买入的。如果是当前买入，那么需要注意买入时间不能是昨天售出状态。必须为前天售出状态
题解
class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) <= 1: return 0 dp = [[0] * 2 for _ in range(len(prices))] # 初始化需要初始化前两天的 dp[0][0] = 0 - prices[0] dp[0][1] = 0 dp[1][0] = 0 - min(prices[0:2]) dp[1][1] = max(dp[0][0] + prices[1], dp[0][1]) for i in range(2, len(dp)): dp[i][0] = max(dp[i-1][0], dp[i-2][1]-prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]) return dp[-1][-1]
优化上述代码
class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) <= 1: return 0 # 初始化： 计算前两天的 最大收益 buy = - min(prices[0:2]) # 当前持有的最大收益 sell = max(0, prices[1]-prices[0]) # 当前不持有的最大收益 lastSell = 0 # 前一天不持有的最大收益 # 从第三天开始买入（注：第三天的下标为 2） for i in range(2, len(prices)): buy = max(buy, lastSell-prices[i]) # 在更新sell 前更新一下lastSell lastSell = sell sell = max(sell, buy+prices[i]) return sell