DP 38: Best Time to Buy and Sell Stock IV | Recursion to Space Optimization

This chapter explores Best Time to Buy and Sell Stock IV, scaling up previous stock trading problems where we were limited to at most $k$ transactions. We will evolve our approach from a recursive strategy to memoization, tabulation, and finally space optimization.

1. Problem Statement & Evolution from Stock III

In Stock III, we were allowed at most two transactions. In this problem, the limit is generalized to at most $k$ transactions, where $k$ can be any positive integer.

Transaction Definition: A complete transaction consists of one buy and one sell operation (buy -> sell).
Constraint: You cannot engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Goal: Maximize total profit with at most $k$ transactions over a given array of daily stock prices.

2. Core Mental Model: The Transaction State Machine

Instead of tracking boolean flags for whether we are holding a stock or counting completed transactions, we can view the problem as a sequence of transaction states from $0$ to $2k - 1$ :

Even transaction states ( $0, 2, 4, \dots, 2k-2$ ): Buy opportunities.
Odd transaction states ( $1, 3, 5, \dots, 2k-1$ ): Sell opportunities.

CODE

Index:        0      1      2      3  ...  (2k - 1)
Action:     BUY0   SELL0   BUY1   SELL1 ...  SELL(k-1)

3. Recursive Solution Approach

With the index of the day and the current transaction number (tranNumber), our recursive function evaluates two choices at every step: take action (buy/sell) or skip.

Recursive Code Structure

C++

int f(int ind, int tranNumber, vector<int>& prices, int n, int k) {
    // Base Cases
    if (ind == n || tranNumber == 2 * k) return 0;

    // Even transaction number -> Buy state
    if (tranNumber % 2 == 0) {
        int buyProfit = -prices[ind] + f(ind + 1, tranNumber + 1, prices, n, k);
        int notBuyProfit = 0 + f(ind + 1, tranNumber, prices, n, k);
        return max(buyProfit, notBuyProfit);
    } 
    // Odd transaction number -> Sell state
    else {
        int sellProfit = prices[ind] + f(ind + 1, tranNumber + 1, prices, n, k);
        int notSellProfit = 0 + f(ind + 1, tranNumber, prices, n, k);
        return max(sellProfit, notSellProfit);
    }
}

4. Memoization (Top-Down DP)

To optimize the exponential recursive solution, we cache overlapping subproblems using a 2D memoization table of size n x (2k + 1).

Memoized Implementation

C++

int f(int ind, int tranNumber, vector<int>& prices, int n, int k, vector<vector<int>>& dp) {
    if (ind == n || tranNumber == 2 * k) return 0;
    
    if (dp[ind][tranNumber] != -1) return dp[ind][tranNumber];

    if (tranNumber % 2 == 0) {
        return dp[ind][tranNumber] = max(
            -prices[ind] + f(ind + 1, tranNumber + 1, prices, n, k, dp),
            0 + f(ind + 1, tranNumber, prices, n, k, dp)
        );
    } else {
        return dp[ind][tranNumber] = max(
            prices[ind] + f(ind + 1, tranNumber + 1, prices, n, k, dp),
            0 + f(ind + 1, tranNumber, prices, n, k, dp)
        );
    }
}

int maxProfit(int k, vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> dp(n, vector<int>(2 * k + 1, -1));
    return f(0, 0, prices, n, k, dp);
}

5. Tabulation (Bottom-Up DP)

We convert the top-down memoization approach into an iterative bottom-up table. Since base cases evaluate to 0, the table is initialized to zeros. We iterate backwards from ind = n - 1 down to 0 and tranNumber = 2k - 1 down to 0.

Tabulation Code

C++

int maxProfit(int k, vector<int>& prices) {
    int n = prices.size();
    // Size is n + 1 for indices and 2 * k + 1 for transaction states to avoid out-of-bounds
    vector<vector<int>> dp(n + 1, vector<int>(2 * k + 1, 0));

    for (int ind = n - 1; ind >= 0; ind--) {
        for (int tranNumber = 2 * k - 1; tranNumber >= 0; tranNumber--) {
            if (tranNumber % 2 == 0) {
                dp[ind][tranNumber] = max(
                    -prices[ind] + dp[ind + 1][tranNumber + 1],
                    0 + dp[ind + 1][tranNumber]
                );
            } else {
                dp[ind][tranNumber] = max(
                    prices[ind] + dp[ind + 1][tranNumber + 1],
                    0 + dp[ind + 1][tranNumber]
                );
            }
        }
    }
    return dp[0][0];
}

6. Space Optimization

Notice in the tabulation state transition that dp[ind][tranNumber] only depends on the next day (ind + 1). We can optimize our space complexity from $O(N \times K)$ down to $O(K)$ by maintaining just two 1D arrays: after and curr.

Space-Optimized Implementation

C++

int maxProfit(int k, vector<int>& prices) {
    int n = prices.size();
    vector<int> after(2 * k + 1, 0);
    vector<int> curr(2 * k + 1, 0);

    for (int ind = n - 1; ind >= 0; ind--) {
        for (int tranNumber = 2 * k - 1; tranNumber >= 0; tranNumber--) {
            if (tranNumber % 2 == 0) {
                curr[tranNumber] = max(
                    -prices[ind] + after[tranNumber + 1],
                    0 + after[tranNumber]
                );
            } else {
                curr[tranNumber] = max(
                    prices[ind] + after[tranNumber + 1],
                    0 + after[tranNumber]
                );
            }
        }
        after = curr;
    }
    return after[0];
}

7. Complexity Analysis Summary

Approach	Time Complexity	Space Complexity	Notes
Recursion	$O(2^N)$	$O(N)$	Exponential time due to overlapping subproblems.
Memoization	$O(N \times K)$	$O(N \times K) + O(N)$	Caches subproblems across `n` days and `2k` states.
Tabulation	$O(N \times K)$	$O(N \times K)$	Iterative bottom-up filling of DP table.
Space Optimized	$O(N \times K)$	$O(K)$	Reduces space by tracking only current and next day rows.

8. Summary and Key Takeaways

Generalizing Transactions: Transforming transaction limits into a linear transaction count state ( $0$ to $2k-1$ ) simplifies complex multi-buy/sell problems.
Even vs. Odd States: Even transaction states correspond to buying actions, while odd transaction states correspond to selling actions.
Base Case Safety: Always allocate table sizes with headroom (n + 1 and 2k + 1) to prevent out-of-bounds index access when referencing ind + 1 or tranNumber + 1.
Space Reduction: Because each day's decision depends exclusively on the succeeding day, space optimization successfully drops the memory footprint to $O(K)$ .
Robustness: Edge cases like very small array lengths paired with large values of $k$ are inherently managed by the base case halting condition (ind == n).