Best Time to Buy and Sell Stock with Cooldown

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

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)

Thoughts

max问题，且每天的状态是从前面一(因为有cool down，两)天跳转过来的，用DP。action分别为buy和sell。难点在于能想到要针对action分别维持两个不同类型的状态。buy[i] = max(sell[i - 2] - price, buy(i - 1)), 表示前i天的任意序列中以buy为结尾的最大利润，可以分别是前面i-1天中买的，也可以是在第i天买的(由于有cooldown，只能是sell[i-2])。sell[i] = max(buy(i - 1) + price, sell(i - 1)), 表示前i天的任意序列中以sell为结尾的最大利润。同理可以是当天卖出，也可以是前面卖出。全局最优肯定不能以持有结束，只会是sell[N-1]。

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        const int N = prices.size();
        if (N <= 1) return 0;
        vector<int> buy(N), sell(N);
        buy[0] = -prices[0];
        buy[1] = max(buy[0], -prices[1]);
        sell[1] = max(0, prices[1] - prices[0]);
        for (int i = 2; i < N; ++i) {
            buy[i] = max(sell[i - 2] - prices[i], buy[i - 1]);
            sell[i] = max(buy[i - 1] + prices[i], sell[i - 1]);
        }
        return sell[N - 1];
    }
};

Analysis

时间复杂度O(n).