> For the complete documentation index, see [llms.txt](https://liuyang89116.gitbook.io/my-leetcode-book/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuyang89116.gitbook.io/my-leetcode-book/chapter_8_high_frequency/buying-and-selling-stock/problem-309-best-time-to-buy-and-sell-stock-with-cooldown.md).

# Problem 309: Best Time to Buy and Sell Stock with Cooldown

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

## 思路

> <https://discuss.leetcode.com/topic/30421/share-my-thinking-process>

这个讲解实在是太棒了！

* 首先对于一个 dp 问题，我们首先应该考虑 state，然后根据不同的 state，得出 transition function。这里应该有三个不同的 state：`buy`，`sell`，`rest`，其中 `rest` 就是买完股票被冷冻的状态。
* 根据这三个状态我们可以得出转移方程：\</br>

  `buy[i]`：在第 i 天，买股票所能得到的最大收益；\</br>

  `sell[i]`：在第 i 天，卖股票所能得到的最大收益；\</br>

  `rest[i]`：在第 i 天，被冷冻所能得到的最大收益；\</br>

  ```
  buy[i] = max(rest[i - 1] - price, buy[i - 1])
  sell[i] = max(buy[i - 1] + price, sell[i - 1])
  rest[i] = max(sell[i - 1], buy[i - 1], rest[i - 1])
  ```
* 一个简单的逻辑就是：**buy 之前必须是 rest 的状态； 只有先 buy，才能 sell**\</br>
* 易错点：如果出现`[buy, rest, buy]` 怎么办？用 `buy[i] <= rest[i]` 可以限制，它等价于 `rest[i] = max(sell[i - 1], rest[i - 1])`。由此还可以推出另一个关系：`rest[i] = sell[i - 1]`
* 结合这两个关系式，代入最上面，可以得出：\</br>

  ```
  buy[i] = max(sell[i - 2] - price, buy[i - 1])
  sell[i] = max(buy[i - 1] + price, sell[i - 1])
  ```

  因为第 i 天只和第 i - 1 天和第 i - 2 天有关，所以可以进一步简化为 `O(1)` 的 space

```java
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;

        int sell = 0, prevSell = 0, buy = Integer.MIN_VALUE, prevBuy;
        for (Integer price : prices) {
            prevBuy = buy;
            buy = Math.max(prevSell - price, prevBuy);
            prevSell = sell;
            sell = Math.max(prevBuy + price, prevSell);
        }

        return sell;
    }
}
```