###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++`

# 309. Best Time to Buy and Sell Stock with Cooldown

## [題目連結:] https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/

## 題目:
You are given an array ```prices``` where ```prices[i]``` is the price of a given stock on the ```ith``` day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

* After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

**Note:** You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

**Example 1:**

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

**Example 2:**

Input: prices = [1]
Output: 0

## 解題想法:
* 此題為買賣進階題目
* 不能先賣再買、不能連續買而不賣(基本規定)
* [121. Best Time to Buy and Sell Stock](/k1o9uteuT8GbpkFCT0isEw)
* [122. Best Time to Buy and Sell Stock II](/nOzARxUKRl-R9qKhT-1HLQ)
* 可以進行多次買賣:
* 但規定: **若今天買股票，則昨天必須休息**

* DP:
* **sell** = [0] * len(prices)
* 該天結束手裡沒有股票的情況下獲得的profit
* **hold** = [0] * len(prices)
* 該天結束手裡有股票的情況下獲得的profit
* hold[0] = -prices[0]
* 初始第一天要先買才能有後續

* 每次判斷更新sell、hold數組
* **case1**: **今天手中沒有股票的profit = 昨天手中就已經沒有股票了or昨天買了今天賣掉**
* sell[i] = max(sell[i - 1], hold[i - 1] + prices[i])
* **case2**: **今天手中有股票的profit = 昨天已經買了or '前天' 賣今天才能買**
* hold[i] = max(hold[i - 1], (sell[i - 2] if i >= 2 else 0) - prices[i])
* 最終sell[-1]即為解 (直觀來說肯定是手上沒有股票才會是最佳解)

## Python:

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices: 
            return 0
        #該天結束手裡沒有股票的情況下獲得的profit
        sell = [0] * len(prices)
        #該天結束手裡有股票的情況下獲得的profit
        #注意: 規定 若今天買股票則昨天必須休息
        hold = [0] * len(prices)
        #初始第一天要先買才能有後續
        hold[0] = -prices[0]
        for i in range(1, len(prices)):
            #今天手中沒有股票的profit = 昨天手中就已經沒有股票了or昨天買了今天賣掉
            sell[i] = max(sell[i - 1], hold[i - 1] + prices[i])
            #今天手中有股票的profit = 昨天已經買了or前天賣今天才能買
            hold[i] = max(hold[i - 1], (sell[i - 2] if i >= 2 else 0) - prices[i])
        print(sell)
        print(hold)
        return sell[-1]
    
result = Solution()
prices = [1,2,3,0,2]
print(result.maxProfit(prices))

## C++:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if (n==0)
            return 0;
        //init
        vector<int> sell(n,0), hold(n,0);
        hold[0]=-prices[0];
        //dp
        for (int i=1; i<n; i++){
            sell[i]=max(sell[i-1], hold[i-1]+prices[i]);
            hold[i]=max(hold[i-1], (i-2>=0? sell[i-2]:0)-prices[i]);
        }
        return sell.back();
    }
};

## C++: 優化
* 因為只關心i-1與i-2
* 可以簡化在O(1)space完成

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if (n==0)
            return 0;
        int sell=0, pre_sell=0;
        int hold=-prices[0], pre_hold=0;
        for (int i=1; i<n; i++){
            pre_hold=hold;
            hold=max(pre_sell-prices[i],hold);
            //在hold後面計算，確保hold使用時候，相當於sell[i-2]
            pre_sell=sell;
            sell=max(pre_hold+prices[i],sell);
        }
        return sell;
    }
};