# 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](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/121.best-time-to-buy-and-sell-stock)
* [122.best-time-to-buy-and-sell-stock-ii](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/122.best-time-to-buy-and-sell-stock-ii)

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

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