DP 40. Buy and Sell Stocks With Transaction Fee | Recursion to Space Optimisation

This chapter concludes the dynamic programming on stocks series by introducing a transaction fee for every completed buy-and-sell cycle. Building directly upon the foundation of Best Time to Buy and Sell Stock II (unlimited transactions), we explore how to account for administrative or brokerage fees without altering the core state-transition logic.

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

In standard unlimited-transaction stock problems, every profitable price delta can be captured. However, real-world brokerages charge a fee per completed transaction (buy + sell).

• The Status Quo: Without a fee, we greedily capture every positive price difference.
• The Catch: If the price increases by $2$ but the transaction fee is $2$, executing that trade yields $0$ net profit (or negative profit if multiple fees apply).
• The Objective: Maximize the total net profit by factoring in a fixed transaction fee (fee) for each completed buy-and-sell pair.

2. Core Mental Model & The Transaction Fee Analogy

Real-Life Analogy: The Brokerage Tollbooth

Imagine trading stocks on a digital platform where a tollbooth operator collects a flat fee of $2$ every time you complete a full round trip—buying a share and later selling it.

• If you buy at $10$ and sell at $17$, your gross profit is $7$. But the tollbooth operator demands a $2$ fee upon completion, leaving your net profit at $5$.
• If you make ten tiny trades that each net $1$ in gross profit, the tollbooth fee of $2$ per trade will quickly bankrupt your portfolio. Thus, the algorithm must now weigh whether a price jump is large enough to outstrip the transaction fee.

3. Revisiting the Base Problem: Buy and Sell Stock II

Recall the recurrence relation from Buy and Sell Stock II, where unlimited transactions are allowed:

• State Representation: f(index, buy)
  • index: The current day we are examining (from 0 to n-1).
  • buy: A binary flag (0 or 1) indicating whether we are allowed to buy (buy = 1) or sell (buy = 0).
• Transitions:
  • If buy == 1: We have two choices:
    1. Buy the stock: Pay -prices[index], transition to f(index + 1, 0).
    2. Skip: Do nothing, transition to f(index + 1, 1).
    • Take the maximum of both choices.
  • If buy == 0: We have two choices:
    1. Sell the stock: Receive +prices[index], transition to f(index + 1, 1).
    2. Skip: Do nothing, transition to f(index + 1, 0).
    • Take the maximum of both choices.

4. Where to Deduct the Transaction Fee?

A transaction is officially "completed" only when you finish a full Buy $\rightarrow$ Sell cycle. Because of this, the fee can be deducted at exactly one of two strategic locations in our code without changing the mathematical outcome:

1. At the Time of Sale: Deduct the fee immediately when the stock is sold and the transaction closes.
2. At the Time of Purchase: Deduct the fee upfront when the stock is bought to clear the cost immediately.

As long as the fee is subtracted once per completed cycle, the DP engine accurately computes the maximized net profit.

5. Step-by-Step Code Evolution: Space-Optimized Implementation

Below is the space-optimized iterative solution (derived from DP Buy/Sell Stock II) updated with the transaction fee applied during the sell operation.

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        if (n == 0) return 0;

        // Base vectors representing ahead/next day states
        // ahead[0]: max profit when we can sell (holding stock)
        // ahead[1]: max profit when we can buy (not holding stock)
        vector<int> ahead(2, 0), cur(2, 0);

        for (int ind = n - 1; ind >= 0; ind--) {
            // Case 1: Can Buy (buy == 1)
            cur[1] = max(-prices[ind] + ahead[0], 
                           0 + ahead[1]);

            // Case 2: Can Sell (buy == 0) - Fee deducted here upon completion
            cur[0] = max(prices[ind] - fee + ahead[1], 
                           0 + ahead[0]);

            ahead = cur;
        }

        return ahead[1]; // Starting at index 0 with ability to buy
    }
};

6. Alternative Placement: Deducting the Fee Upon Purchase

If you prefer to pay the fee upfront when initiating the trade rather than upon selling, the modification is equally valid:

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        if (n == 0) return 0;

        vector<int> ahead(2, 0), cur(2, 0);

        for (int ind = n - 1; ind >= 0; ind--) {
            // Fee deducted upfront during purchase
            cur[1] = max(-prices[ind] - fee + ahead[0], 
                           0 + ahead[1]);

            // No fee deduction during sale
            cur[0] = max(prices[ind] + ahead[1], 
                           0 + ahead[0]);

            ahead = cur;
        }

        return ahead[1];
    }
};

7. Comparative Strategy Summary

8. Summary and Key Takeaways

• Problem Extension: Buying and selling with a transaction fee is a direct extension of Buy and Sell Stock II with unlimited transactions.
• Transaction Completion: A transaction fee is incurred precisely once per completed Buy $\rightarrow$ Sell cycle.
• Flexible Placement: You can deduct the fee either when purchasing (upfront) or when selling (upon completion) with identical correctness.
• State Transition Integrity: The underlying state machine (buy = 0 vs buy = 1) remains unchanged; only a constant subtraction (-fee) is introduced into the profit calculation.
• Space Optimization: By maintaining only two state arrays (ahead and cur), space complexity is reduced from $O(N)$ to $O(1)$.
• Mastery of DP on Stocks: Completing this sixth variant concludes the Dynamic Programming on Stocks series, equipping you to solve any stock-trading variation through systematic state modeling and space optimization.