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

/*********************** Method-1 (Bottom up approach, TC-O(N), SC-O(N)) ********************
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 1) return 0;
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[n-1][0] = prices[n-1];
        dp[n-1][1] = 0;
        dp[n-2][0] = max(prices[n-2], prices[n-1]);
        dp[n-2][1] = max(0, prices[n-1] - prices[n-2]);
        
        for(int i = n-3; i >= 0; i--) {
            dp[i][0] = max(prices[i] + dp[i+2][1], dp[i+1][0]);
            dp[i][1] = max(dp[i+1][1], -prices[i] + dp[i+1][0]);
        }
        return dp[0][1];
    }
};
***********************************************************************************************/

/*********************** Method-2 (Bottom up approach, TC-O(N), SC-O(1)) ********************/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 1) return 0;
        vector<vector<int>> dp(3, vector<int>(2, 0));
        dp[(n-1)%3][0] = prices[n-1];
        dp[(n-1)%3][1] = 0;
        dp[(n-2)%3][0] = max(prices[n-2], prices[n-1]);
        dp[(n-2)%3][1] = max(0, prices[n-1] - prices[n-2]);
        
        for(int i = n-3; i >= 0; i--) {
            dp[i%3][0] = max(prices[i] + dp[(i+2)%3][1], dp[(i+1)%3][0]);
            dp[i%3][1] = max(dp[(i+1)%3][1], -prices[i] + dp[(i+1)%3][0]);
        }
        return dp[0][1];
    }
};