# Leetcode 309. Best Time to Buy and Sell Stock with Cooldown
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 。

想法 :

DP最難的就是尋找最優子結構與轉移方程，連日來被電的飛起。

Step 1 :

首先，有三種狀態 :
buy(i) = max(rest(i - 1) - price[i] , buy(i - 1));
sell(i) = max(buy(i - 1) + price[i] , sell(i - 1));
rest(i) = max(rest(i - 1) , sell(i - 1) , buy(i - 1));

buy(i) : 第i天買，或是不買。
sell(i) : 第i天賣，或是不賣。
rest(i) : 第i天休息。

Step 2 :

觀察一下，發現可以簡化 :
rest(i) = sell(i-1);
為什麼? 因為賣掉那天肯定是最大的，就算沒賣也是sell(i-1) >= rest(i-1)。

Step 3 :

帶回原式將rest()替換掉 :
buy(i) = max(sell(i - 2) - price[i], buy(i - 1));
sell(i) = max(buy(i-1) + price[i] , sell(i - 1));

Step 4 :

注意初始設值與邊界狀態。
第一天不可能賣、可能買第一天或是買第二天、可能第二天賣掉。

時間複雜度 : O(n)。

程式碼 :

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int l = prices.size(), sell_2 ,sell_1, sell, buy_1, buy;
        
        if(l == 1) return 0;    
        if(l == 2) return max(-1 * prices[0] + prices[1], 0);
        
        sell_2 = 0;
        sell_1 = max(sell_2 , -1 * prices[0] + prices[1]);
        buy_1 = max(-1 * prices[0] , -1 * prices[1]);
        
        for(int i = 2 ; i < l ; i++){
            buy = max(sell_2 - prices[i], buy_1);
            sell = max(buy_1 + prices[i], sell_1);
            
            buy_1 = buy;
            sell_2 = sell_1;
            sell_1 = sell;
            
            //cout << buy_1 << " " << buy << " ; " << sell_2 << " " << sell_1 << " " << sell << endl; 
        }
        
        return sell;
    }
};