【算法】力扣【动态规划、状态机】309. 买卖股票的最佳时机含冷冻期

309. 买卖股票的最佳时机含冷冻期

文章目录

• 【算法】力扣【动态规划、状态机】309. 买卖股票的最佳时机含冷冻期
• • 题目描述
  • 输入输出示例
  • 解题思路
  • • 关键点澄清：
    • 状态转移方程
    • 边界条件
    • C++代码
  • 复杂度分析
  • 总结

---

【算法】力扣【动态规划、状态机】309. 买卖股票的最佳时机含冷冻期

题目描述

本文介绍解决力扣平台上第309号问题——“买卖股票的最佳时机含冷冻期”的算法。这是一个中等难度的问题，其核心是通过设计一个算法来计算在给定的股票价格数组prices下，能够获取的最大利润。股票价格数组prices中的每个元素prices[i]表示第i天的股票价格。

题目的主要约束条件如下：

• 卖出股票后，无法在第二天购买股票，即存在1天的冷冻期。
• 不能同时进行多笔交易，即在再次购买前，必须出售掉之前的股票。

输入输出示例

• 示例 1:

  输入: prices = [1,2,3,0,2]
  输出: 3
  1
  2

  • 解释：
    最优的交易方式为在第1天买入，第2天卖出，这时获得利润为1；第4天买入，第5天卖出，这时获得额外利润为2。因此，总利润为3。

• 示例 2:

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

  • 解释：
    只有一个价格，故无法进行交易，最大利润为0。

解题思路

这个问题可以用动态规划（DP）来解决。我们定义两个动态规划数组dp[i][0]和dp[i][1]，其中：

• dp[i][0]代表在第i天结束时，不持有股票的最大利润；
• dp[i][1]代表在第i天结束时，持有股票的最大利润。

关键点澄清：

• 在第i天卖出股票后，不能在第i+1天买入，这是由题目所规定的冷冻期导致的。

• 如果第i天不持股，说明我们在第i天卖出了股票，或者在第 i - 1 天时就已经不持股。

• 如果第i天持股，意味着我们要么是继续持有之前的股票，要么是在第i天买入。

  • 如果是买入第 i 天的股票，那么我们不能从dp[i-1][0]转移过来，只能从dp[i-2][0]转移过来。
  • 解释： 根据转移方程，“第i - 1天不持股”这一状态可以由两种状态转移过来：
    1. 卖出股票的操作转移而来，也就是dp[i][0] = dp[i-1][1] + prices[i]，受冷冻期影响，此时只能从dp[i-2][0]转移过来。
    2. 继续保持第 i - 2 天不持股的状态，也就是dp[i][0] = dp[i-1][0]，此时dp[i-2][0]等价于dp[i-1][0]。
    • 综上所述，无论第 i - 1 有没有卖出股票， 只要从dp[i-2][0]转移过来，就能保证正确性。

状态转移方程

• 不持股：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
• 持股：dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])

边界条件

• dp[0][0]初始化为0，因为在开始时我们不可能有利润。
• dp[0][1]初始化为负无穷，这表示我们不可能在第0天就持有股票，让从“第0天持股”转移而来的状态变成一个最不可能的答案。

C++代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 1) return 0; // 只有一天，不可能有交易

        // 初始化dp数组
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][1] = -prices[0]; // 第一天买入股票
        dp[0][0] = 0; // 第一天不可能卖出股票

        for(int i = 1; i < n; ++i) {
            // 第i天不持股的情况下，可能是第i-1天就不持股，或者是第i天卖出股票
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            // 第i天持股的情况下，可能是第i-1天就持股，或者是第i天买入股票
            dp[i][1] = max(dp[i-1][1], (i >= 2 ? dp[i-2][0] : 0) - prices[i]);
        }

        return dp[n-1][0]; // 返回最后一天不持股的情况，即可能的最大利润
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复杂度分析

• 时间复杂度：$O(n)$，其中n是数组prices的长度。我们只需要遍历一次数组，对于每一天，计算不持股和持股的最大利润。
• 空间复杂度：$O(n)$，用于存储动态规划数组。

总结

本文通过动态规划的方法解决了买卖股票的最佳时机含冷冻期的问题，强调了理解状态转移方程在解题过程中的重要性，并通过边界条件和状态方程的详细解释，保证了解题思路的清晰性和逻辑性。代码块中的注释也为理解每一步操作提供了方便。希望此篇博客对读者有所帮助。