题目:309. 最佳买卖股票时机含冷冻期
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown
给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。 示例: 输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
解题:
1、dp问题。每个时刻,都只有三种状况:持有股票、冷冻期、未持有股票。
我们使用三个dp数组分别存储这三种情况的最大利润,分别记为dp_with_buy 、dp_in_cool、dp_not_buy ,那么公式有:
# 未持有:前一时刻未持有股票的最大利润,此时卖出股票的最大利润,两者最大值
dp_not_buy[i] = max(dp_not_buy[i - 1], dp_with_buy[i - 1] + prices[i])
# 持有:前一时刻持有股票的最大利润,此时冷冻结束可以买入的最大利润,两者最大值 dp_with_buy[i] = max(dp_with_buy[i - 1], dp_in_cool[i - 1] - prices[i])
# 冷冻:前一时刻冷冻的最大利润,前一时刻卖出股票的最大利润,两者最大值 dp_in_cool[i] = max(dp_not_buy[i - 1], dp_in_cool[i - 1])
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) < 2:
return 0
dp_not_buy = [0] * len(prices)
dp_with_buy = [0] * len(prices)
dp_in_cool = [0] * len(prices )
dp_with_buy[0] = -prices[0]
for i in range(1, len(prices)):
dp_not_buy[i] = max(dp_not_buy[i - 1], dp_with_buy[i - 1] + prices[i])
dp_with_buy[i] = max(dp_with_buy[i - 1], dp_in_cool[i - 1] - prices[i])
dp_in_cool[i] = max(dp_not_buy[i - 1], dp_in_cool[i - 1])
return max(dp_not_buy[-1], dp_in_cool[-1])
PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。
PPS:还是得日更呀,总结一下总是好的。