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

## 题目地址(309. 最佳买卖股票时机含冷冻期)

<https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/>

## 题目描述

```
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

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

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

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

## 前置知识

* 记忆化递归
* [动态规划](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md)

## 公司

* 阿里
* 腾讯
* 字节

## 记忆化递归

### 思路

用 f(i, state) 表示第 i 天（从 0 开始），当前状态是 state 的最大利润。

* state 为 0 表示手上没有股票
* state 为 1 表示手上有股票
* state 为 -1 表示手上没有股票，但是在冷冻期，所以不能买。

那么转移方程就容易了。

* 如果 state 为 0，那么当前可以什么都不做，也可以买入，也就是说不能卖出了。因此最大利润就是两种的最大值。

```python
max(f(i+1, 0), f(i+1, 1) - prices[i])
```

* 如果 state 为 1，那么当前可以什么都不做，也可以卖出，也就是说不能买入了。因此最大利润就是两种的最大值。

```python
max(f(i+1, 1), f(i+1, -1) + prices[i])
```

* 如果 state 为 -1，那么当前只能什么都不做，因此最大利润维持不变，但是状态变为 0。（因为冷冻期只有一天，思考下如果冷冻期是 k 天如何修改我们的逻辑？）

```python
f(i+1, 0)
```

临界条件就是 i == n - 1，此时如果 state == 1， 我们可以将其卖掉，否则无法卖出。

### 代码

代码支持：Python3

Python3 Code:

```python
class Solution:
    def maxProfit(self, prices):
        if not prices:
            return 0
        n = len(prices)

        @lru_cache(None)
        def f(i, state):
            if i == n - 1:
                return prices[i] if state == 1 else 0

            if state == -1:
                return f(i + 1, 0)
            if state == 0:
                return max(f(i + 1, 0), -prices[i] + f(i + 1, 1))
            if state == 1:
                return max(prices[i] + f(i + 1, -1), f(i + 1, 1))

        return f(0, 0)
```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度: 状态总数为 3 \* n ，单个状态所需时间为 $O(1)$，因此时间复杂度为 $O(n)$
* 空间复杂度：状态总数为 3 \* n ，因此空间复杂度为 $O(n)$

## 动态规划

### 思路

这是一道典型的 DP 问题， DP 问题的核心是找到状态和状态转移方程。

这道题目的状态似乎比我们常见的那种 DP 问题要多，这里的状态有 buy sell cooldown 三种，我们可以用三个数组来表示这这三个状态，buy,sell, cooldown。其中：

* buy\[i]表示第 i 天，且手里有股票（不在冷冻期）的最大利润
* sell\[i]表示第 i 天，且手里没有股票的最大利润
* cooldown\[i]表示第 i 天，且手里有股票（但是在冷冻期不能卖）的最大利润

我们思考一下，其实 cooldown 这个状态数组似乎没有什么用，因为 cooldown 不会对`profit`产生任何影响。 我们可以进一步缩小为两种状态。

* buy\[i] 表示第 i 天，且手里有股票的最大利润
* sell\[i] 表示第 i 天，且手里没股票的最大利润

对应的状态转移方程如下：

> 这个需要花点时间来理解

```javascript
buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
```

我们来分析一下，buy\[i]对应第 i 的 action 只能是 buy 或者 cooldown。（如果是 sell 的话手里就没有股票了）

* 如果是 cooldown，那么 profit 就是 buy\[i - 1]
* 如果是 buy，那么就是`前一个卖的profit减去今天买股票花的钱`，即 sell\[i -2] - prices\[i]

> 注意这里是 i - 2，不是 i-1 ，因为有 cooldown 一天的限制

sell\[i]对应第 i 的 action 只能是 sell 或者 cooldown。

* 如果是 cooldown，实际上就是 sell\[i - 1]。
* 如果是 sell，那么利润就是`前一次买的时候获取的利润加上这次卖的钱`，即 buy\[i - 1] + prices\[i]

### 关键点解析

* 多状态动态规划

### 代码

代码支持：JS

JS Code:

```javascript
/*
 * @lc app=leetcode id=309 lang=javascript
 *
 * [309] Best Time to Buy and Sell Stock with Cooldown
 *
 */
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  if (prices == null || prices.length <= 1) return 0;

  // 定义状态变量
  const buy = [];
  const sell = [];
  // 寻常
  buy[0] = -prices[0];
  buy[1] = Math.max(-prices[0], -prices[1]);
  sell[0] = 0;
  sell[1] = Math.max(0, prices[1] - prices[0]);
  for (let i = 2; i < prices.length; i++) {
    // 状态转移方程
    // 第i天只能是买或者cooldown
    // 如果买利润就是sell[i - 2] - prices[i], 注意这里是i - 2，不是 i-1 ，因为有cooldown的限制
    // cooldown就是buy[i -1]
    buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
    // 第i天只能是卖或者cooldown
    // 如果卖利润就是buy[i  -1] + prices[i]
    // cooldown就是sell[i -1]
    sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
  }

  return Math.max(buy[prices.length - 1], sell[prices.length - 1], 0);
};
```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(n)$（同上）
* 空间复杂度：$O(n)$（同上）

## 相关题目

* [121.best-time-to-buy-and-sell-stock](/leetcode-solution/easy/121.best-time-to-buy-and-sell-stock.md)
* [122.best-time-to-buy-and-sell-stock-ii](/leetcode-solution/easy/122.best-time-to-buy-and-sell-stock-ii.md)

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了， 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。我是 lucifer，维护西湖区最好的算法题解，Github 超 40K star 。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 另外我整理的 1000 多页的电子书已限时免费下载，大家可以去我的公众号《力扣加加》后台回复电子书获取。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/309.best-time-to-buy-and-sell-stock-with-cooldown.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.