# \[309]\[中等]\[动态规划] 最佳买卖股票时机含冷冻期

## 题目描述

[309. 最佳买卖股票时机含冷冻期](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)

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

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

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

示例:

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

## 解题思路

动态规划是一个比较直接的思路. 题目求解的其实是最后一天的最大利润, 很容易想到将第$$i$$天的最大利润作为状态, 这样最后的答案就是最后一天的数值.

接下来就是考虑状态转移方程, 这与交易的状态是息息相关的. 一般来说有两种状态, 持有和空仓, 由于本题增加了一个冷冻期, 因此是**持有**, **冷冻期空仓**, **空仓**三种状态.

考虑每一天状态的定义, 由于买入和卖出操作, 会使一天的状态发生改变:

* 买入: 由空仓到持有, **冷冻期空仓不能转为持有**, 即不能买入
* 卖出: 持有到冷冻期

因此, 每天用一个状态来表示的话, 需要将每一天的状态定义为操作前, 或操作后. 这里使用**操作后**的状态, 即有买入行为的一天定义为持有状态, 有卖出行为的定义为冷冻期状态. 这样对于三种状态, 可能的来源是:

* 持有
  * 上一天已经持有
  * 当天买入
* 冻结期
  * 当天卖出
* 空仓
  * 上一天空仓
  * 上一天冻结期

综上所述, 结合逻辑, 状态的转移是有一定的逻辑关系的, 因此, 需要每种状态在每天的表现, 我们的转移方程就能从状态的切换和相互之间的关系出发.

因此, 定义三个序列, 分别记录第$$i$$天, 作为**持有**, **冷冻期空仓**, **空仓**三种状态的**最大利润**, 即 $$\text{dp1}$$, $$\text{dp2}$$, $$\text{dp3}$$, 如$$\text{dp2}\[i]$$就代表第$$i$$天结束为冷冻期状态下的**最大利润**.

然后我们定义利润. 一次买卖中间的差价肯定是利润. 另外, 需要注意的是, 根据世界通用的**浮赢不算赢, 落袋才算赚**的原则, 如果我们买入之后一直没有卖出行为, 就算涨的再多也不算赚钱. 此外, 我们的资金只看落袋的金额, 持有状态下股票的价值, 是不应该计入到账户资金中的, 即买入一支股票相当于暂时损失了这笔钱.

现在我们可以定义初始状态和状态转移方程了. 首先定义初始状态. 首先天数要不小于两天, 否则一买一卖的操作都无法完成, 利润最大肯定是0. 初始状态第一天, 持有状态相当于第一天买入, 冻结期状态不存在, 利润设置为0, 空仓状态相当于不操作, 利润也为0. 因此初始状态初始化为:

$$\text{dp1}\[0]=-\text{prices}\[0],\qquad \text{dp2}\[0]=0,\qquad \text{dp3}\[0]=0$$

状态转移方程.

* 对于持有状态, 如果上一天已经持有, 那利润等于上一天持有状态的利润(之前某一天扣除过买入价后的利润); 如果是当天买入, 利润是上一天空仓状态的利润减去当天的价格. 两者取其大

  $$\text{dp1}\[i] = \max(\text{dp1}\[i-1],\text{dp2}\[i-1]-\text{prices}\[i])$$
* 对于冻结期状态, 只有当天卖出才会转移, 利润等于上一天持有利润加上当日卖出的价格

  $$\text{dp2}\[i] = \text{dp1}\[i-1] + \text{prices}\[i]$$
* 对于空仓状态, 如果上一天也空仓, 利润直接等于上一天空仓状态的利润; 还有一种是上一天是冻结期, 利润等于冻结期状态上一天的利润

  $$\text{dp3}\[i] = \max(\text{dp2}\[i - 1], \text{dp3}\[i - i])$$

最终的最大利润会在最后一天**冷冻期**和**空仓**的状态下产生, 持有状态下的部分利润被在仓的股票占用了, 肯定不是最大利润.

综上所述, 代码如下:

```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n <= 1:
            return 0

        dp1 = [-prices[0]]  # 持有状态
        dp2 = [0]  # 冻结期
        dp3 = [0]  # 空仓

        for i in range(1, n):
            dp1.append(max(dp1[i - 1], dp3[i - 1] - prices[i]))
            dp2.append(dp1[i - 1] + prices[i])
            dp3.append(max(dp3[i - 1], dp2[i - 1]))
        return max(dp2[-1], dp3[-1])
```


---

# 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://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/309-zui-jia-mai-mai-gu-piao-shi-ji-han-leng-dong-qi.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.