309. Best Time to Buy and Sell Stock with Cooldown ---M !!!!!!!!!!!!!!!!!!!!!!!!!

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

A:

每当新添加一个的时候，如果不动，就是dp[end-1] 否则就往前找买的那一天。

再加上前前的dp值

class Solution {

public:

int maxProfit(vector<int>& prices) {

int n = prices.size();

vector<int> dp(n, 0);

// only when we sell on the new day (i_th), we have profit

for (int end = 1; end < n; end++) {

dp[end] = dp[end - 1]; // we can: do nothing, so, dp[i] = 0

// profit only increase if we sell on the end day.

for (int start = 0; start < end; start++) {

auto profit = prices[end] - prices[start];

if (profit > 0) {

dp[end] = max(

dp[end], profit + (start - 2 >= 0 ? dp[start - 2] : 0));

}

}

}

return dp[n - 1];

}

};

---------------状态转移  。  只不过，我们之前的都是2个状态，现在是3个了-----------------

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int lastBuy = INT_MIN/2, lastCool = 0, lastSell = 0; // status-wise maximum profit 
        for(int v : prices)
        {
            int newBuy = max(lastCool - v, lastBuy);// either use previous buy, and buy this time
            int newCool = max(lastCool, lastSell);
            int newSell = lastBuy + v;
            
            lastSell = newSell;
            lastCool = newCool;
            lastBuy = newBuy;
        }
        return max(lastSell, lastCool);
    }
};

--------------利用状态图------------------------

// Author: Huahua
// Running time: 12 ms
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sold = 0;
        int rest = 0;
        int hold = INT_MIN;
        for (const int price : prices) {
            int prev_sold = sold;
            sold = hold + price;
            hold = max(hold, rest - price);
            rest = max(rest, prev_sold);
        }
        return max(rest, sold);
    }
};

Mistakes: