309. 最佳买卖股票时机含冷冻期 ——【Leetcode每日一题】

ゝ一世哀愁。 2024-03-25 20:28 36阅读 0赞

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

给定一个整数数组 `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.  目前**不持有任何股票，并不处于冷冻期**

我们设`dp[i]`表示第 `i` 天结束后的 **「累计最大收益」**，对应 **三种不同的状态**， 分别用 `dp[i][0]` 、`dp[i][1]` 、`dp[i][2]`：

1.  目前持有一支股票`dp[i][0]` ，有两种可能：
    
     *  第`i − 1`天就已经持有，即 `dp[i][0]` = `dp[i - 1][0]`
     *  或者第 `i` 天刚买入，那么第 `i−1` 天就不能持有股票并且不处于冷冻期中 ，即 `dp[i][0]` = `dp[i - 1][2]` \- `prices[i]`
2.  目前不持有任何股票，并处于冷冻期`dp[i][1]` ，只有一种可能：
    
     *  第 i 天结束之后处于冷冻期的原因是在当天卖出了股票, 说明第 `i - 1` 天持有一支股票，对应的状态为 `f[i−1][0]` 加上卖出股票的正收益 `prices[i]`，即：`dp[i][1]` = `dp[i - 1][0]` \+ `prices[i]`
3.  目前不持有任何股票，并不处于冷冻期 `dp[i][2]` ,说明当天没有进行任何操作，且第 `i − 1` 天肯定也没有持有任何股票，有两种情况：
    
     *  第 `i − 1` 天处于冷冻期, 即：`dp[i][2]` = `dp[i - 1][1]`
     *  第 `i − 1` 天不处于冷冻期，对应的状态为： `dp[i][2]` = `dp[i - 1][2]`

这样我们就得到了所有的状态转移方程。如果一共有 n天，那么最终的答案即为：  
 m a x ( d p \[ n − 1 \] \[ 0 \] , d p \[ n − 1 \] \[ 1 \] , d p \[ n − 1 \] \[ 2 \] ) max(dp\[n - 1\]\[0\], dp\[n - 1\]\[1\],dp\[n - 1\]\[2\]) max(dp\[n−1\]\[0\],dp\[n−1\]\[1\],dp\[n−1\]\[2\])

注意到如果在最后一天（第 `i - 1` 天) 结束之后，手上仍然持有股票，那么显然是没有任何意义的。因此更加精确地，最终的答案实际上是 `dp[n - 1][1]` 和`dp[n - 1][2]` 中的较大值，即：  
 m a x ( d p \[ n − 1 \] \[ 1 \] , d p \[ n − 1 \] \[ 2 \] ) max( dp\[n - 1\]\[1\],dp\[n - 1\]\[2\]) max(dp\[n−1\]\[1\],dp\[n−1\]\[2\])

#### 代码：(Java) ####

public class MaxProfit {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int [] prices = {
        1,2,3,0,2};
    		System.out.println(maxProfit(prices));
    	}
    	public static int maxProfit(int[] prices) {
        
    		int n = prices.length;
    		if(n == 1) {
        
    			return 0;
    		}
    
    		int[][] dp = new int[n][3];
    		dp[0][0] = -prices[0];
    		for(int i = 1; i < n; i++) {
        
    			dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
    			dp[i][1] = dp[i - 1][0] + prices[i];
    			dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);
    		}
    		
    		return Math.max(dp[n - 1][1], dp[n - 1][2]);
        }
    }

##### 运行结果：![在这里插入图片描述][dd2d7d801ff349328b69bff93ad87499.png] #####

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)，其中 n 为数组 `prices` 的长度。
 *  **空间复杂度**： O ( n ) O(n) O(n)。我们需要 3n的空间存储动态规划中的所有状态，对应的空间复杂度为  O ( n ) O(n) O(n)。

##### 注：仅供学习参考！ #####

题目来源：[力扣。][Link 1]

[dd2d7d801ff349328b69bff93ad87499.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/bcae2c06ed684e25a875b2bee742593e.png
[Link 1]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/