Buy and Sell Stocks With Cooldown (Recursion to Space Optimisation)

1. Problem Statement & Context

This chapter covers the fifth problem in the Dynamic Programming on Stocks series. Building upon previous variations—such as single transactions (Stock 1), unlimited transactions (Stock 2), at most 2 transactions (Stock 3), and at most $k$ transactions (Stock 4)—this problem introduces a strict operational rule: Cooldown.

• Unlimited Transactions: You are permitted to complete as many buy-and-sell transactions as you like.
• The Cooldown Constraint: After you sell a stock on day $i$, you cannot buy a stock on day $i + 1$. You must skip a day (cooldown), meaning the earliest day you are allowed to buy again is day $i + 2$.
• Goal: Maximize total profit while strictly obeying the cooldown constraint.

2. Core Mental Model & Analogy

Real-Life Analogy: The Market Rest Period

Imagine trading high-volatility cryptocurrency or commodities. Whenever you close a profitable position (sell), exchange regulations or platform rules mandate a 24-hour mandatory lock-out period before you can open a new position.

If you sell on Tuesday, Wednesday is your mandatory cooldown day. You cannot re-enter the market until Thursday. This simple mechanical delay changes your future state transitions from index + 1 (normal next day) to index + 2 (jumping past the cooldown day).

3. Naive Approach: Unlimited Stocks Transition Breakdown

In Stock 2 (unlimited transactions without cooldown), the decision tree at any given index with a binary buy flag ($1$ for allowed to buy, $0$ for must sell) was:

• If buy == 1 (Can Buy):

  • Option A (Buy): Pay -price[index], move to index + 1 with buy = 0.
  • Option B (Skip / Don't Buy): Pay $0, move to index + 1 with buy = 1.
  • Transition Formula: $\max(-\text{price}[i] + f(i+1, 0), \ 0 + f(i+1, 1))$

• If buy == 0 (Can Sell):

  • Option A (Sell): Gain +price[index], move to index + 1 with buy = 1.
  • Option B (Skip / Don't Sell): Gain $0, move to index + 1 with buy = 0.
  • Transition Formula: $\max(\text{price}[i] + f(i+1, 1), \ 0 + f(i+1, 0))$

4. Step-by-Step Evolution: Introducing Cooldown

The only difference in the recurrence relation occurs during the Sell operation. When you sell a stock, instead of moving to the immediately adjacent day (index + 1), the cooldown constraint forces you to skip a day.

Modified Recurrence Relation

• When Buying (buy == 1): Unchanged.

• When Selling (buy == 0): Jump to index + 2.

5. Recursive & Memoized Implementation

Because we jump to index + 2 on a sell action, our base cases must safely handle out-of-bound indices when $i \ge n$.

class Solution {
private:
    int solve(int index, int buy, vector<int>& prices, vector<vector<int>>& dp) {
        // Base Case: If index goes out of bounds, no profit can be made
        if (index >= prices.size()) return 0;

        // Return memoized result if already computed
        if (dp[index][buy] != -1) return dp[index][buy];

        long long profit = 0;
        if (buy) {
            // Choice 1: Buy the stock (-prices[i]) and move to index+1 with buy=0
            // Choice 2: Skip buying and move to index+1 with buy=1
            profit = max(-prices[index] + solve(index + 1, 0, prices, dp),
                         0 + solve(index + 1, 1, prices, dp));
        } else {
            // Choice 1: Sell the stock (+prices[i]) and jump to index+2 with buy=1 (Cooldown applied)
            // Choice 2: Skip selling and move to index+1 with buy=0
            profit = max(prices[index] + solve(index + 2, 1, prices, dp),
                         0 + solve(index + 1, 0, prices, dp));
        }

        return dp[index][buy] = profit;
    }

public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // dp table of size [n][2] initialized with -1
        vector<vector<int>> dp(n, vector<int>(2, -1));
        return solve(0, 1, prices, dp);
    }
};

6. Bottom-Up Tabulation (Dynamic Programming)

To convert the memoized solution to a bottom-up tabular format, we reverse the direction of loops. Because we access index + 2, we size our DP table with extra padding (n + 2) to prevent segmentation faults.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // Table size n + 2 to safely handle index + 2 lookups without bounds check
        vector<vector<int>> dp(n + 2, vector<int>(2, 0));

        // Base cases are implicitly 0, so we iterate backwards from n-1 down to 0
        for (int index = n - 1; index >= 0; index--) {
            for (int buy = 0; buy <= 1; buy++) {
                long long profit = 0;
                if (buy == 1) {
                    profit = max(-prices[index] + dp[index + 1][0],
                                 0 + dp[index + 1][1]);
                } else {
                    // Cooldown rule: Selling jumps to index + 2
                    profit = max(prices[index] + dp[index + 2][1],
                                 0 + dp[index + 1][0]);
                }
                dp[index][buy] = profit;
            }
        }

        // Starting point: index 0, buy allowed (1)
        return dp[0][1];
    }
};

7. Space Optimization Challenge: Why Standard 1D Optimization Fails

In simpler DP problems (like Stock 2), space can be optimized from $O(n \times 2)$ to $O(1 \times 2)$ using two rows: front and current.

However, in Stock With Cooldown, calculating the state at index requires data from both index + 1 and index + 2.

Therefore, maintaining a rolling window requires storing three distinct rows simultaneously rather than two.

8. Space-Optimized Implementation (Constant Space $O(6) \approx O(1)$)

To achieve true constant space complexity, we can track three states representing:

1. front2 $\rightarrow$ represents dp[index + 2]
2. front1 $\rightarrow$ represents dp[index + 1]
3. curr $\rightarrow$ represents dp[index]

Space-Optimized Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // We need 3 rows: front2 (index + 2), front1 (index + 1), and curr (index)
        // Each row stores 2 values: [buy=0, buy=1]
        vector<int> front2(2, 0);
        vector<int> front1(2, 0);
        vector<int> curr(2, 0);

        for (int index = n - 1; index >= 0; index--) {
            // 1. Compute Buy state (buy = 1)
            curr[1] = max(-prices[index] + front1[0], 0 + front1[1]);

            // 2. Compute Sell state (buy = 0), noting the index + 2 jump stored in front2
            curr[0] = max(prices[index] + front2[1], 0 + front1[0]);

            // Shift pointers forward for the next iteration
            front2 = front1;
            front1 = curr;
        }

        return curr[1]; // Result for index 0 with buy = 1
    }
};

9. Complexity Analysis Summary

10. Summary and Key Takeaways

• The Cooldown Rule Modification: Whenever you sell a stock (buy = 0), you must skip the immediate next day, altering your transition index from index + 1 to index + 2.
• Out-of-Bounds Protection: Because of the index + 2 jump, your tabulation table and base cases must safely accommodate indices up to $n+1$ or $n+2$ to prevent segmentation faults.
• Transition State Expansion: Unlike standard stock problems that require only a 2-row rolling optimization (front and curr), the cooldown constraint requires a 3-state rolling window (front2, front1, curr).
• State Decoupling: Splitting the recurrence logic into explicit buy = 1 and buy = 0 calculations simplifies debugging and vector state updates.
• Optimal Efficiency: The final space-optimized solution successfully compresses dynamic programming memory down to $O(1)$ constant auxiliary space while preserving linear $O(n)$ time performance.