Leetcode 309: Best Time to Buy and Sell Stock with Cooldown

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

Notes:

This question belongs to a classic series of Stocks Problems on Leetcode, which be solved either by greedy or dp. The optimal time and space complexity are usually in O(N), or O(k*N) if there is another parameter of at most k transactions.

This question can be solved by dp. There are a lot of ways found online. Here are two of them.

The first one:

dp[i]: the maximum profit upto the i-th day;

dp[i] = max(dp[i-1], prices[i] - prices[j] + dp[j-2]); j<=i;

so it will be a O(N^2) solution. But we can do better, let's some change of the above equation,

dp[i] = max(dp[i-1], prices[i] + dp[j-2] - prices[j]); j<=i;

define diffMax = max(diffMax, dp[j-2] - dp[j]);

then,

dp[i] = max(dp[i-1], prices[i] + diffMax);

See the code below:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //dp[i]: the maximum profit upto the ith day;
        //dp[i] = max(dp[i-1], prices[i] - prices[j] + dp[j-2]); j<=i;
        //diffMax = max(diffMax, dp[j-2] - dp[j]);
        //dp[i] = max(dp[i-1], prices[i] + diffMax);
        int len = prices.size();
        if(len<2) return 0;
        int diffMax = INT_MIN;
        vector<int> dp(len+1, 0);
        for(int i=1; i<=len; ++i) {
            diffMax = max(diffMax, i - 2 >= 0 ? dp[i-2] - prices[i-1] : -prices[i-1]);
            dp[i] = max(dp[i-1], diffMax + prices[i-1]);
        }
        return dp[len];
    }
};

The following is another popular dp method, which is called two-state dp.

See the code below:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //dp[i][0]: the maximum profit up to the ith day without stock;
        //dp[i][1]: the maximum profit up to the ith day with a stock;
        //dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
        //dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i]);
        int len = prices.size();
        if(len<2) return 0;
        vector<vector<int>> dp(len+1, vector<int>(2, 0));
        dp[0][1] = -prices[0];//must initialized
        for(int i=1; i<=len; ++i) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]);
            dp[i][1] = max(dp[i-1][1], i - 2 >= 0 ? dp[i-2][0] - prices[i-1] : -prices[i-1]);
        }
        return dp[len][0];
    }
};