跳转至

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

力扣链接(中等)：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown

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

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

  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

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

示例 2:

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

提示：

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

个人题解

完成本题前，请先完成 121-123/188. 买卖股票的最佳时机 I-IV。

本题的关键是如何处理冷冻期的问题，由于题目中冷冻期仅为一天，那么我们可以将第 i 天卖出股票这个状态从非持有状态中独立出来，通过判断前一天 i - 1 是否为当天卖出股票状态，得到今天是否为冷冻期状态，同理，冷冻期状态也属于非持有状态。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        const int length = prices.size(); 

        // 本题需要判断前一天是否为冷冻期
        // 所以需要有一个单独的状态来判断
        // 1.持有状态 2.非持有状态(除3,4外) 3.当天卖出状态(非持有的一种) 4.冷冻期状态(非持有的一种)
        // 4 可以根据前一天是否为 3 来判断
        const int N = 5000 + 10;
        int dp[N][5] = {};

        // 初始化 dp
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = 0;
        dp[0][4] = 0;

        for(int i = 1; i < length; i++) {
            // 当天持有状态 1.之前就持有 2.当天买入(1.前一天为冷冻期 2.前一天为非持有状态)
            dp[i][1] = max(dp[i - 1][1], max(dp[i - 1][4], dp[i - 1][2]) - prices[i]);
            // 当天非持有状态 1.之前就非持有 2.前一天为冷冻期      
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][4]);
            // 当天卖出状态 1.之前为持有状态
            dp[i][3] = dp[i - 1][1] + prices[i];
            // 当天为冷冻状态 1.之前为当天卖出状态
            dp[i][4] = dp[i - 1][3];
        }

        // 最大收入一定是把股票卖出后的状态
        return max(dp[length - 1][2], max(dp[length - 1][3], dp[length - 1][4]));
    }
};