【LeetCode】动态规划—309. 买卖股票的最佳时机含冷冻期（附完整Python/C++代码）

题目描述

前言

最佳买卖股票时机含冷冻期问题 是一个经典的动态规划问题。给定一个数组表示股票的价格，每天你只能做一件事：买入股票、卖出股票或者冷冻（休息）。如果你在一天卖出了股票，那么第二天你无法进行任何交易（有一天的冷冻期）。目标是通过买卖股票来获得最大的收益。该问题要求我们结合动态规划的思想，合理规划买卖操作，以获取最大的利润。

---

基本思路

1. 问题定义

给定一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。你可以在任意天选择买入或卖出股票，但在卖出股票后的第二天不能买入（有一天冷冻期）。目标是找到能够获得的最大利润。

2. 理解问题和递推关系

为了帮助我们理解该问题的动态规划思路，我们可以定义几种状态来表示我们在某一天的持有情况。主要有以下三种状态：

状态定义：

1. 持有股票的状态（hold）：

   • hold[i] 表示在第 i 天结束时，我们持有股票时的最大收益。
   • 这个状态可以从两种情况转移而来：要么是之前买入并继续持有（hold[i-1]），要么是今天刚刚买入。

2. 未持有股票且处于冷冻期的状态（cooldown）：

   • cooldown[i] 表示在第 i 天结束时，我们处于冷冻期时的最大收益（也就是说，第 i 天刚卖出股票，不能买入股票）。
   • 这个状态只能通过在 i 天卖出股票后进入，因此 cooldown[i] = hold[i-1] + prices[i]。

3. 未持有股票且不处于冷冻期的状态（sell）：

   • sell[i] 表示在第 i 天结束时，我们没有持有股票且没有处于冷冻期的最大收益。
   • 这个状态有两种来源：要么是处于冷冻期后过了一天（cooldown[i-1]），要么是之前一直不持有股票（sell[i-1]）。

状态转移公式：

1. hold[i] = max(hold[i-1], sell[i-1] - prices[i])

   • 要么我们继续持有股票，要么我们在第 i 天买入股票。

2. cooldown[i] = hold[i-1] + prices[i]

   • 表示我们在第 i 天卖出了股票，进入冷冻期。

3. sell[i] = max(sell[i-1], cooldown[i-1])

   • 表示我们处于不持有股票且不在冷冻期的状态，可以是冷冻期结束或者一直未持有股票。

初始条件：

• hold[0] = -prices[0]：表示在第 0 天买入股票的收益。
• sell[0] = 0：在第 0 天不持有股票，收益为 0。
• cooldown[0] = 0：在第 0 天没有冷冻期，收益为 0。

3. 解决方法

动态规划方法

1. 定义 hold[i]，cooldown[i] 和 sell[i] 来表示每一天的三种状态的最大收益。
2. 使用递推公式更新这三种状态的值。
3. 最终结果为 max(sell[n-1], cooldown[n-1])，即在最后一天没有持有股票时的最大收益。

伪代码：

initialize hold[0] = -prices[0], sell[0] = 0, cooldown[0] = 0
for each day i from 1 to n-1:hold[i] = max(hold[i-1], sell[i-1] - prices[i])cooldown[i] = hold[i-1] + prices[i]sell[i] = max(sell[i-1], cooldown[i-1])
return max(sell[n-1], cooldown[n-1])

4. 进一步优化

• 空间优化：由于 dp[i] 仅依赖于 dp[i-1]，我们可以将动态规划中的 hold、cooldown 和 sell 状态用常量来代替，从而将空间复杂度优化到 O(1)。

5. 小总结

• 问题思路：通过将状态分为持有股票、未持有且处于冷冻期、未持有且不在冷冻期三种情况，动态规划可以清晰地描述问题的状态转移过程。
• 时间复杂度：该算法的时间复杂度为 O(n)，空间复杂度可以优化为 O(1)。

以上就是买卖股票的最佳时机含冷冻期问题的基本思路。

---

Python代码

class Solution:def maxProfit(self, prices: list[int]) -> int:if not prices:return 0n = len(prices)# 初始化第0天的状态hold = -prices[0]sell = 0cooldown = 0for i in range(1, n):# 更新状态new_hold = max(hold, sell - prices[i])new_cooldown = hold + prices[i]new_sell = max(sell, cooldown)# 更新hold, cooldown, sellhold, cooldown, sell = new_hold, new_cooldown, new_sell# 返回sell和cooldown中的较大值return max(sell, cooldown)

Python代码解释总结

1. 初始化：在第 0 天，如果持有股票，则收益为 -prices[0]，否则为 0。
2. 状态转移：通过递推公式更新每一天的 hold、cooldown 和 sell 状态。
3. 返回结果：在最后一天，返回不持有股票状态下的最大收益，即 max(sell, cooldown)。

---

C++代码

#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.empty()) return 0;int n = prices.size();// 初始化第0天的状态int hold = -prices[0];int sell = 0;int cooldown = 0;for (int i = 1; i < n; ++i) {// 更新状态int new_hold = max(hold, sell - prices[i]);int new_cooldown = hold + prices[i];int new_sell = max(sell, cooldown);// 更新hold, cooldown, sellhold = new_hold;cooldown = new_cooldown;sell = new_sell;}// 返回sell和cooldown中的较大值return max(sell, cooldown);}
};

C++代码解释总结

1. 初始化：在第 0 天，如果持有股票，则收益为 -prices[0]，否则为 0。
2. 状态转移：通过递推公式更新每一天的 hold、cooldown 和 sell 状态。
3. 返回结果：在最后一天，返回不持有股票状态下的最大收益，即 max(sell, cooldown)。

---

总结

• 核心思想：通过将买卖股票问题划分为持有股票、未持有且处于冷冻期、未持有且不在冷冻期三种状态，动态规划可以清晰地模拟问题的状态转移过程。
• 时间复杂度：该算法的时间复杂度为 O(n)，可以处理大规模的输入。
• 空间优化：由于每个状态只依赖前一天的状态，空间复杂度可以从 O(n) 优化为 O(1)。