Chapter 15: Modifying Transitions - Best Time to Buy and Sell Stock with Transaction Fee

In the previous chapter, we introduced a state-machine approach to handle complex decision-making over time. The "cooldown" was a rule that affected which state transitions were possible (e.g., you couldn't buy immediately after selling).

Now, we'll solve a similar problem where the constraint isn't on the transition itself, but on the cost of the transition. This is a common variation in DP problems. LeetCode's "Best Time to Buy and Sell Stock with Transaction Fee" (Problem #714) is the perfect example. The underlying state machine (holding vs. not holding) remains the same, but the profit calculation for the "sell" action is altered.

The Problem:

You are given an array prices where prices[i] is the price of a given stock on the i-th day, and an integer fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). The fee is only paid once per transaction (i.e., when you sell).

For example:

• prices = [1, 3, 2, 8, 4, 9], fee = 2

• Output: 8

• Explanation:

  • Buy on day 0 (price=1)

  • Sell on day 3 (price=8) -> profit = 8 - 1 - 2 = 5

  • Buy on day 4 (price=4)

  • Sell on day 5 (price=9) -> profit = 9 - 4 - 2 = 3

  • Total profit = 5 + 3 = 8

Approach 1: The Recursive Solution with State

Just like in the cooldown problem, our state is defined by (i, holding). The function solve(i, holding) will return the maximum profit from day i onwards.

The logic is nearly identical, with one key change in the "sell" action:

1. If holding is False (we can buy):

   • Option A: Buy. Profit = prices[i] + solve(i + 1, True).

   • Option B: Rest. Profit = solve(i + 1, False).

2. If holding is True (we can sell):

   • Option A: Sell. Profit = prices[i] - fee + solve(i + 1, False). We subtract the fee upon selling. There is no cooldown, so we proceed to i+1.

   • Option B: Hold. Profit = solve(i + 1, True).

The base case remains the same: when i >= len(prices), we return 0.

from typing import List

def maxProfit_recursive(prices: List[int], fee: int) -> int:

    def solve(i, holding):
        if i >= len(prices):
            return 0

        if holding:
            # Option A: Sell today (and pay the fee)
            sell_today = prices[i] - fee + solve(i + 1, False)
            # Option B: Hold and check tomorrow
            hold = solve(i + 1, True)
            return max(sell_today, hold)
        else:
            # Option A: Buy today
            buy_today = -prices[i] + solve(i + 1, True)
            # Option B: Rest and check tomorrow
            rest = solve(i + 1, False)
            return max(buy_today, rest)

    return solve(0, False)

# Trying it out
# print(maxProfit_recursive([1, 3, 2, 8, 4, 9], 2)) # 8
# As expected, this is too slow for large inputs.

Approach 2: Memoization with a Decorator (Top-Down DP)

The state (i, holding) is perfectly cacheable. We apply our lru_cache decorator to the recursive solution to eliminate redundant computations.

import functools
from typing import List

class Solution:
    def maxProfit_memoized(self, prices: List[int], fee: int) -> int:

        @functools.lru_cache(maxsize=None)
        def solve(i, holding):
            if i >= len(prices):
                return 0

            if holding:
                sell_today = prices[i] - fee + solve(i + 1, False)
                hold = solve(i + 1, True)
                return max(sell_today, hold)
            else:
                buy_today = -prices[i] + solve(i + 1, True)
                rest = solve(i + 1, False)
                return max(buy_today, rest)

        return solve(0, False)

# Trying it out
# solver = Solution()
# print(solver.maxProfit_memoized([1, 3, 7, 5, 10, 3], 3)) # 6

The memoized solution has a time complexity of O(n) because there are n * 2 states, and each is computed once.

Approach 3: Iteration (Bottom-Up DP)

The most efficient approach is to use O(1) space by tracking the maximum profit for two states at the end of each day:

• hold: The maximum profit if we end the day holding a stock.

• free: The maximum profit if we end the day not holding a stock (we are "free" to buy).

We iterate through the prices and update these two variables based on the previous day's values:

• new_hold = max(hold, free - price): To be holding today, we either continued holding from yesterday, OR we were free yesterday and bought today.

• new_free = max(free, hold + price - fee): To be free today, we either continued being free from yesterday, OR we were holding yesterday and sold today (paying the fee).

We initialize hold to -infinity and free to 0.

def maxProfit_iterative(prices: List[int], fee: int) -> int:
    # Max profit if we end the day holding a stock
    hold = -float('inf')
    # Max profit if we end the day not holding a stock
    free = 0

    for price in prices:
        # Store the previous day's `hold` value before we overwrite it
        prev_hold = hold

        # Update states for the current day
        hold = max(prev_hold, free - price)
        free = max(free, prev_hold + price - fee)

    # Final max profit must be when we are not holding any stock.
    return free

# Trying it out
# print(maxProfit_iterative([1, 3, 2, 8, 4, 9], 2)) # 8

This iterative approach is the optimal solution, with O(n) time complexity and O(1) space complexity.

Conclusion

This chapter reinforced the power of the state-machine DP model. By comparing this problem to the "cooldown" version, you can see how different business rules translate into small, precise changes in the DP transition logic. The core states (hold, free) remained the same, but the calculation for free was modified to include the - fee. This ability to adapt a core DP structure to handle varying constraints is a hallmark of a skilled problem solver.