LeetCode 第309题：最佳买卖股票时机含冷冻期

📖 文章摘要

本文详细解析LeetCode第309题“最佳买卖股票时机含冷冻期”，这是一道动态规划题目。文章提供了状态机DP的解决方案，包含C#、Python、C++三种语言实现，配有详细的状态转移分析和性能分析。适合想要提升动态规划能力的程序员。

核心知识点： 动态规划、状态机、状态转移、空间优化
难度等级： 中等
推荐人群： 具有基础算法知识，想要提升动态规划解题能力的程序员

题目描述

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
• 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例

示例 1：

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2：

输入: prices = [1]
输出: 0

提示

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

解题思路

本题可以使用动态规划来解决，关键是设计好状态转移方程。我们可以定义三种状态：

关键点：

• 定义三种状态：持有股票、不持有股票且在冷冻期、不持有股票且不在冷冻期
• 设计状态转移方程
• 考虑空间优化

具体步骤：

1. 定义状态数组
2. 初始化状态
3. 遍历数组进行状态转移
4. 返回最终最大利润

图解思路

状态机分析表

当前状态	可转移状态	转移条件	收益变化
持有股票	继续持有	无	0
持有股票	卖出(进入冷冻期)	卖出	+prices[i]
不持有(冷冻期)	不持有不冷冻	等待一天	0
不持有(非冷冻)	买入	买入	-prices[i]
不持有(非冷冻)	继续不持有	无	0

状态转移分析表

天数	持有股票	不持有(冷冻期)	不持有(非冷冻)
0	-prices[0]	0	0
i	max(前一天持有, 前一天非冷冻买入)	前一天持有+卖出	max(前一天冷冻, 前一天非冷冻)

代码实现

C# 实现

public class Solution {
    public int MaxProfit(int[] prices) {
        if (prices == null || prices.Length <= 1) return 0;
        
        int[] hold = new int[prices.Length];        // 持有股票
        int[] sold = new int[prices.Length];        // 不持有股票，且在冷冻期
        int[] rest = new int[prices.Length];        // 不持有股票，且不在冷冻期
        
        // 初始化状态
        hold[0] = -prices[0];
        
        // 状态转移
        for (int i = 1; i < prices.Length; i++) {
            hold[i] = Math.Max(hold[i-1], rest[i-1] - prices[i]);
            sold[i] = hold[i-1] + prices[i];
            rest[i] = Math.Max(rest[i-1], sold[i-1]);
        }
        
        return Math.Max(sold[prices.Length-1], rest[prices.Length-1]);
    }
}

Python 实现

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices or len(prices) <= 1:
            return 0
            
        n = len(prices)
        # 空间优化，只使用三个变量
        hold = -prices[0]  # 持有股票
        sold = 0          # 不持有股票，且在冷冻期
        rest = 0          # 不持有股票，且不在冷冻期
        
        for i in range(1, n):
            pre_hold = hold
            pre_sold = sold
            pre_rest = rest
            
            hold = max(pre_hold, pre_rest - prices[i])
            sold = pre_hold + prices[i]
            rest = max(pre_rest, pre_sold)
            
        return max(sold, rest)

C++ 实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty() || prices.size() <= 1) return 0;
        
        int n = prices.size();
        vector<int> hold(n, 0);    // 持有股票
        vector<int> sold(n, 0);    // 不持有股票，且在冷冻期
        vector<int> rest(n, 0);    // 不持有股票，且不在冷冻期
        
        // 初始化状态
        hold[0] = -prices[0];
        
        // 状态转移
        for (int i = 1; i < n; i++) {
            hold[i] = max(hold[i-1], rest[i-1] - prices[i]);
            sold[i] = hold[i-1] + prices[i];
            rest[i] = max(rest[i-1], sold[i-1]);
        }
        
        return max(sold[n-1], rest[n-1]);
    }
};

执行结果

C# 实现

• 执行用时：84 ms
• 内存消耗：38.2 MB

Python 实现

• 执行用时：40 ms
• 内存消耗：15.1 MB

C++ 实现

• 执行用时：0 ms
• 内存消耗：11.4 MB

性能对比

语言	执行用时	内存消耗	特点
C#	84 ms	38.2 MB	性能适中，内存占用较大
Python	40 ms	15.1 MB	执行较快，内存占用适中
C++	0 ms	11.4 MB	执行最快，内存占用最小

代码亮点

1. 🎯 使用状态机DP优雅解决股票交易问题
2. 💡 Python实现中使用空间优化，只需要三个变量
3. 🔍 清晰的状态定义和转移方程
4. 🎨 代码结构简洁，易于理解和维护

常见错误分析

1. 🚫 忽略数组为空或只有一个元素的边界情况
2. 🚫 状态转移方程写错，导致结果不正确
3. 🚫 未考虑冷冻期的影响
4. 🚫 返回值选择错误状态

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
朴素DP	O(n)	O(n)	思路直观	空间消耗大
状态机DP	O(n)	O(n)	状态清晰	实现稍复杂
空间优化DP	O(n)	O(1)	空间效率高	代码易错

相关题目

• LeetCode 121. 买卖股票的最佳时机 - 简单
• LeetCode 122. 买卖股票的最佳时机 II - 中等
• LeetCode 714. 买卖股票的最佳时机含手续费 - 中等

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第309题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！