DP 37. Buy and Sell Stocks III | Recursion to Space Optimization

This chapter explores the third variation of the classic "Buy and Sell Stock" dynamic programming problem. Building upon the foundations of unlimited transactions (Stock II), this problem introduces a strict constraint: at most two transactions are allowed. We will evolve our solution systematically from pure recursion to memoization, tabulation, and finally, extreme space optimization.

1. Why Do We Need This? (Problem Statement & Status Quo)

Evolution of the Stock Problems

• Stock I (Part 1): You are allowed to complete at most one transaction (one buy, one sell).
• Stock II (Part 2): You are allowed unlimited transactions, with the constraint that you cannot engage in multiple overlapping transactions (you must sell before you buy again).
• Stock III (Part 3): You are allowed at most two transactions. You can do 0, 1, or 2 transactions, but never more than 2.

Understanding the Transaction Constraint

Consider the following array of stock prices:

Prices: [3, 3, 5, 0, 0, 3, 1, 4]

• If we followed Stock II (unlimited transactions), we could make multiple profitable trades, netting a total sum of transactions.
• With Stock III, we are capped at at most 2 transactions.
  • Transaction 1: Buy at 0 and sell at 3 (Profit = 3 - 0 = 3).
  • Transaction 2: Buy at 1 and sell at 4 (Profit = 4 - 1 = 3).
  • Maximum Total Profit: 3 + 3 = 6.

Our goal is to write an optimal algorithm that determines this maximum achievable profit under the 2-transaction limit.

2. Core Mental Model: Bounded Knapsack Analogy

In Stock II, our recursive state only needed two parameters: index (current day) and buy (boolean indicating whether we are allowed to buy or must sell).

Stock II State: f(index, buy)

To limit the number of transactions to a maximum cap, we can relate this to a bounded knapsack problem. We introduce a third state parameter: cap, which represents the remaining number of transactions we are allowed to make.

Stock III State: f(index, buy, cap)

When is a Transaction Completed?

A single transaction is only counted as "complete" when a Buy is followed by a Sell. Therefore, we decrement our transaction cap only when we successfully sell a stock, rather than when we buy it.

3. Naive Recursive Approach & State Transition

From Stock II, we already know how to handle the buy and sell choices:

1. If buy == 1 (Allowed to Buy):
   • Choice 1 (Buy): Subtract prices[index] from our profit, move to index + 1, set buy = 0 (now we must sell).
   • Choice 2 (Skip/Not Buy): Add 0, move to index + 1, keep buy = 1.
2. If buy == 0 (Allowed to Sell):
   • Choice 1 (Sell): Add prices[index] to our profit, move to index + 1, set buy = 1 (now we can buy again), and decrement cap by 1 because a full transaction (buy + sell) is now complete.
   • Choice 2 (Skip/Not Sell): Add 0, move to index + 1, keep buy = 0.

Base Cases

Recursion terminates under two conditions:

1. We exhaust all days: index == n.
2. We exhaust all allowed transactions: cap == 0.

In both cases, we can no longer make profit from the market, so we return 0.

4. Step-1: Pure Recursive Code

Here is the complete recursive function reflecting the state transitions:

int f(int index, int buy, int cap, vector<int>& prices, int n) {
    // Base cases
    if (index == n || cap == 0) return 0;
    
    long long profit = 0;
    if (buy) {
        // Option 1: Buy the stock (-prices[index])
        // Option 2: Skip buying (0)
        long long buyProfit = -prices[index] + f(index + 1, 0, cap, prices, n);
        long long skipProfit = 0 + f(index + 1, 1, cap, prices, n);
        profit = max(buyProfit, skipProfit);
    } else {
        // Option 1: Sell the stock (+prices[index]), decrement cap
        // Option 2: Skip selling (0)
        long long sellProfit = prices[index] + f(index + 1, 1, cap - 1, prices, n);
        long long skipProfit = 0 + f(index + 1, 0, cap, prices, n);
        profit = max(sellProfit, skipProfit);
    }
    return profit;
}

• Time Complexity: $O(2^n)$ (Exponential due to overlapping branches, leading to Time Limit Exceeded).
• Space Complexity: $O(n)$ auxiliary stack space for the recursion depth.

5. Step-2: Memoization (Top-Down Dynamic Programming)

Because the same states (index, buy, cap) are revisited multiple times across different recursive branches, we can optimize the solution using Memoization.

State Space Analysis

• index: Ranges from 0 to n - 1 ($n$ states).
• buy: Ranges from 0 to 1 ($2$ states).
• cap: Ranges from 0 to 2 ($3$ states).

Thus, we need a 3D DP table of size n x 2 x 3.

int f(int index, int buy, int cap, vector<int>& prices, int n, vector<vector<vector<int>>>& dp) {
    if (index == n || cap == 0) return 0;
    
    if (dp[index][buy][cap] != -1) return dp[index][buy][cap];
    
    long long profit = 0;
    if (buy) {
        long long buyProfit = -prices[index] + f(index + 1, 0, cap, prices, n, dp);
        long long skipProfit = 0 + f(index + 1, 1, cap, prices, n, dp);
        profit = max(buyProfit, skipProfit);
    } else {
        long long sellProfit = prices[index] + f(index + 1, 1, cap - 1, prices, n, dp);
        long long skipProfit = 0 + f(index + 1, 0, cap, prices, n, dp);
        profit = max(sellProfit, skipProfit);
    }
    return dp[index][buy][cap] = profit;
}

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    // dp[n][2][3] initialized to -1
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(2, vector<int>(3, -1)));
    return f(0, 1, 2, prices, n, dp);
}

• Time Complexity: $O(n \times 2 \times 3) = O(6n) \approx O(n)$
• Space Complexity: $O(n \times 2 \times 3)$ for the 3D DP table + $O(n)$ recursion stack space. (Note: This may still cause TLE or high memory usage in strict environments due to recursive stack overhead).

6. Step-3: Tabulation (Bottom-Up Dynamic Programming)

To eliminate recursion stack overhead and avoid TLE, we convert the memoized solution into an iterative Tabulation approach.

Tabulation Mapping

• index goes from n - 1 down to 0.
• buy goes from 0 to 1.
• cap goes from 1 to 2 (since cap = 0 always yields 0, which is our default initialized state).

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    // 3D DP table: dp[n + 1][2][3] initialized to 0
    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(3, 0)));
    
    // Fill the table bottom-up
    for (int index = n - 1; index >= 0; index--) {
        for (int buy = 0; buy <= 1; buy++) {
            for (int cap = 1; cap <= 2; cap++) {
                long long profit = 0;
                if (buy) {
                    long long buyProfit = -prices[index] + dp[index + 1][0][cap];
                    long long skipProfit = 0 + dp[index + 1][1][cap];
                    profit = max(buyProfit, skipProfit);
                } else {
                    long long sellProfit = prices[index] + dp[index + 1][1][cap - 1];
                    long long skipProfit = 0 + dp[index + 1][0][cap];
                    profit = max(sellProfit, skipProfit);
                }
                dp[index][buy][cap] = profit;
            }
        }
    }
    
    // Initial call was f(0, 1, 2)
    return dp[0][1][2];
}

• Time Complexity: $O(n \times 2 \times 3) = O(n)$
• Space Complexity: $O(n \times 2 \times 3)$ for the 3D DP table.

7. Step-4: Space Optimization (Two 2D Matrices)

Notice in our tabulation code that dp[index][buy][cap] only ever depends on values from the next day (dp[index + 1][...]). We do not need to store the entire $n$ days in memory; we only need two layers:

1. after: Represents dp[index + 1]
2. current: Represents dp[index]

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    
    // after represents dp[index + 1]
    vector<vector<int>> after(2, vector<int>(3, 0));
    // current represents dp[index]
    vector<vector<int>> current(2, vector<int>(3, 0));
    
    for (int index = n - 1; index >= 0; index--) {
        for (int buy = 0; buy <= 1; buy++) {
            for (int cap = 1; cap <= 2; cap++) {
                long long profit = 0;
                if (buy) {
                    long long buyProfit = -prices[index] + after[0][cap];
                    long long skipProfit = 0 + after[1][cap];
                    profit = max(buyProfit, skipProfit);
                } else {
                    long long sellProfit = prices[index] + after[1][cap - 1];
                    long long skipProfit = 0 + after[0][cap];
                    profit = max(sellProfit, skipProfit);
                }
                current[buy][cap] = profit;
            }
        }
        // Shift current to after for the next iteration
        after = current;
    }
    
    return after[1][2];
}

• Time Complexity: $O(n)$
• Space Complexity: $O(2 \times 3) = O(6) \approx O(1)$ constant space!

8. Alternative Approach: Transaction Numbering ($O(n \times 4)$ DP)

An alternative perspective often seen in discussion forums replaces the boolean buy state and cap counter with a single transaction number ranging from 0 to 3 (total of 4 states):

• Even Transaction States (0, 2): Represent Buy operations.
• Odd Transaction States (1, 3): Represent Sell operations.

While this reduces the dimensions to an n x 4 2D DP table, the 3D state approach (index, buy, cap) taught in this chapter is much more intuitive and directly extensible to problems with $k$ transactions (Stock IV).

Summary and Key Takeaways

• Problem Extension: Stock III extends Stock II by enforcing a strict cap of at most 2 transactions.
• State Representation: We introduced a 3-parameter state: f(index, buy, cap).
• Transaction Completion: The transaction cap is decremented only when a sale occurs (since a full transaction requires both a buy and a sell).
• Complexity Progression:
  • Recursion: Exponential time $O(2^n)$, $O(n)$ space.
  • Memoization: $O(n)$ time, $O(n)$ space.
  • Tabulation: $O(n)$ time, $O(n)$ space without recursion overhead.
  • Space Optimization: $O(n)$ time, $O(1)$ constant space using two 2D matrices of fixed size ($2 \times 3$).
• Interview Strategy: The 3D state approach (index, buy, cap) is clean, highly intuitive, and easily generalizable for $k$ transactions.