Problem Description

You are given an array prices where prices[i] represents the price of a stock on day i. You also have a transaction fee fee that must be paid for each complete transaction (buying and selling counts as one transaction).

Your goal is to find the maximum profit you can achieve by buying and selling the stock multiple times. However, there are two important constraints:

1. No simultaneous transactions: You cannot hold multiple stocks at the same time. This means you must sell your current stock before you can buy another one.

2. Transaction fee: Each time you complete a transaction (buy and then sell), you must pay the fee exactly once.

The problem asks you to determine the optimal trading strategy to maximize your total profit after accounting for transaction fees.

For example, if prices = [1, 3, 2, 8, 4, 9] and fee = 2:

• You could buy on day 1 (price = 1) and sell on day 4 (price = 8), making a profit of 8 - 1 - 2 = 5
• Then buy on day 5 (price = 4) and sell on day 6 (price = 9), making a profit of 9 - 4 - 2 = 3
• Total profit would be 5 + 3 = 8

The solution uses dynamic programming with memoization, where dfs(i, j) represents the maximum profit starting from day i with state j (where j = 0 means not holding stock and j = 1 means holding stock). At each day, you have the choice to either do nothing or make a transaction (buy if not holding, sell if holding), and the algorithm finds the optimal sequence of decisions.

Intuition

The key insight is that at any given day, we can be in one of two states: either we're holding a stock or we're not holding a stock. This naturally leads us to think about the problem in terms of state transitions.

At each day i, we need to make a decision based on our current state:

• If we're not holding a stock (state 0), we can either:

  • Do nothing and remain in the same state
  • Buy a stock and transition to the holding state (state 1)

• If we're holding a stock (state 1), we can either:

  • Do nothing and keep holding
  • Sell the stock, pay the fee, and transition back to not holding (state 0)

This decision-making process suggests a recursive approach where we explore both options at each step and choose the one that gives us maximum profit.

The recursive structure becomes clear when we think about it this way: the maximum profit from day i onwards depends on:

1. What state we're currently in (holding or not holding)
2. The maximum profit we can get from day i+1 onwards after making our decision

For the base case, when we've gone through all days (i >= n), the profit is 0 since there are no more trading opportunities.

The reason we use memoization is that we might reach the same state (same day and same holding status) through different paths of buying and selling. For instance, we could reach day 5 without holding stock by either never buying before, or by buying and selling earlier. In both cases, the maximum profit from day 5 onwards with no stock held would be the same, so we can cache this result to avoid recalculating it.

The function dfs(i, j) elegantly captures this logic: it computes the maximum profit starting from day i with holding state j, considering all possible future decisions. By starting with dfs(0, 0) (day 0, not holding stock), we get the maximum profit for the entire period.

Learn more about Greedy and Dynamic Programming patterns.

Solution Approach

The solution implements a top-down dynamic programming approach with memoization using a recursive function dfs(i, j).

Function Definition:

• dfs(i, j) represents the maximum profit achievable starting from day i with state j
• j = 0: currently not holding any stock
• j = 1: currently holding a stock

Base Case: When i >= len(prices), we've processed all days, so we return 0 as there are no more trading opportunities.

Recursive Cases:

1. Option 1 - Do Nothing:

   • We can always choose not to trade on day i
   • This gives us profit: ans = dfs(i + 1, j)
   • We move to the next day while maintaining the same holding state

2. Option 2 - Make a Transaction:

   • If j = 1 (holding stock): We can sell the stock
     • Gain: prices[i] from selling
     • Pay the transaction fee: -fee
     • Move to next day without stock: dfs(i + 1, 0)
     • Total: ans = max(ans, prices[i] + dfs(i + 1, 0) - fee)
   • If j = 0 (not holding stock): We can buy a stock
     • Cost: -prices[i] for buying
     • Move to next day with stock: dfs(i + 1, 1)
     • Total: ans = max(ans, -prices[i] + dfs(i + 1, 1))

Memoization: The @cache decorator automatically memoizes the function results. This prevents recalculation of dfs(i, j) for the same parameters, reducing time complexity from exponential to O(n) where n is the number of days.

Starting Point: The solution begins with dfs(0, 0), meaning we start at day 0 without holding any stock, and the function returns the maximum profit achievable from this initial state.

Time Complexity: O(n) where n is the length of the prices array, as each state (i, j) is computed at most once.

Space Complexity: O(n) for the memoization cache and the recursion call stack.

Example Walkthrough

Let's walk through a small example with prices = [1, 3, 7, 5, 10, 3] and fee = 3.

We'll trace through the recursive calls starting from dfs(0, 0) (day 0, not holding stock).

Day 0 (price = 1), Not holding:

• Option 1: Do nothing → dfs(1, 0)
• Option 2: Buy stock → -1 + dfs(1, 1)

Let's explore buying first:

Day 1 (price = 3), Holding stock:

• Option 1: Keep holding → dfs(2, 1)
• Option 2: Sell → 3 - 3 + dfs(2, 0) = 0 + dfs(2, 0)

The profit from selling (3 - 1 - 3 = -1) is negative, so let's keep holding:

Day 2 (price = 7), Holding stock:

• Option 1: Keep holding → dfs(3, 1)
• Option 2: Sell → 7 - 3 + dfs(3, 0) = 4 + dfs(3, 0)

Selling gives us profit of 7 - 1 - 3 = 3. Let's take this path:

Day 3 (price = 5), Not holding:

• Option 1: Do nothing → dfs(4, 0)
• Option 2: Buy → -5 + dfs(4, 1)

Let's buy:

Day 4 (price = 10), Holding stock:

• Option 1: Keep holding → dfs(5, 1)
• Option 2: Sell → 10 - 3 + dfs(5, 0) = 7 + dfs(5, 0)

Selling gives profit of 10 - 5 - 3 = 2. We sell:

Day 5 (price = 3), Not holding:

• Option 1: Do nothing → dfs(6, 0) = 0 (base case)
• Option 2: Buy → -3 + dfs(6, 1) = -3 + 0 = -3

We choose to do nothing.

Backtracking the optimal path:

• Buy at day 0 (price = 1)
• Sell at day 2 (price = 7): profit = 7 - 1 - 3 = 3
• Buy at day 3 (price = 5)
• Sell at day 4 (price = 10): profit = 10 - 5 - 3 = 2
• Total profit = 3 + 2 = 5

The memoization ensures that if we reach the same state (like day 3 without holding stock) through different paths, we only compute it once. The algorithm explores all possibilities and returns the maximum profit of 5.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array prices. This is because the recursive function dfs(i, j) has two parameters: i ranges from 0 to n-1 (representing the current day/index in prices), and j can only be 0 or 1 (representing whether we currently hold a stock or not). Therefore, there are at most n × 2 = 2n unique states. Due to the @cache decorator, each state is computed only once, and each computation takes O(1) time (excluding recursive calls). Thus, the overall time complexity is O(2n) = O(n).

The space complexity is O(n). This comes from two sources:

1. The memoization cache stores at most 2n states, which requires O(n) space.
2. The recursion call stack can go as deep as n levels in the worst case (when we traverse through all days), contributing another O(n) space.

Therefore, the total space complexity is O(n) + O(n) = O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Transaction Fee Application

Pitfall: A common mistake is applying the transaction fee at the wrong time or applying it twice. Some implementations incorrectly subtract the fee when buying OR add it when selling, rather than applying it once per complete transaction.

Incorrect Example:

if holding_stock:
    # Wrong: applying fee when selling
    max_profit = max(max_profit, prices[day] - fee + dp(day + 1, 0))
else:
    # Wrong: also applying fee when buying
    max_profit = max(max_profit, -prices[day] - fee + dp(day + 1, 1))

Solution: Apply the transaction fee exactly once per complete transaction. The standard approach is to subtract it when selling (as shown in the correct solution), but you could also subtract it when buying - just be consistent and do it only once.

2. State Representation Confusion

Pitfall: Using unclear or inconsistent state representations can lead to logic errors. For example, mixing up what 0 and 1 represent, or using boolean values inconsistently.

Problematic Code:

def dp(day, has_stock):  # Using boolean
    if has_stock:
        # But then accidentally using it as integer
        max_profit = max(max_profit, prices[day] - fee + dp(day + 1, not has_stock))

Solution: Be consistent with state representation. If using integers (0 and 1), stick with them throughout. If using booleans, ensure all transitions use boolean logic correctly.

3. Missing Base Case for Holding Stock at End

Pitfall: Not considering what happens if you're still holding stock when you've processed all days. While the current solution handles this correctly by returning 0, some might think they need special handling.

Overcomplicated Approach:

if day >= len(prices):
    if holding_stock:
        return -float('inf')  # Penalizing holding stock at end
    return 0

Solution: The simple return 0 base case is correct because if you're holding stock at the end with no more days to sell, that path simply won't contribute to the maximum profit. The algorithm naturally avoids this scenario.

4. Bottom-Up DP Array Initialization Error

Pitfall: When converting to bottom-up DP, incorrectly initializing the DP arrays or handling the boundary conditions.

Incorrect Bottom-Up:

def maxProfit(prices, fee):
    n = len(prices)
    dp = [[0] * 2 for _ in range(n)]
  
    # Wrong initialization - should handle day 0 specially
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
  
    return dp[n-1][0]

Solution: Properly initialize the first day's states:

dp[0][0] = 0  # Not holding stock on day 0
dp[0][1] = -prices[0]  # Bought stock on day 0

5. Integer Overflow in Other Languages

Pitfall: While not an issue in Python, implementing this in languages like C++ or Java without considering integer overflow can cause problems with large profit values.

Solution: Use appropriate data types (like long long in C++ or long in Java) when dealing with potentially large cumulative profits.