Solution Explanation for Best Time to Buy and Sell Stock with Transaction Fee

This problem asks to find the maximum profit achievable from buying and selling a stock multiple times, considering a transaction fee for each trade. We'll explore three approaches: Memoization (top-down dynamic programming), Dynamic Programming (bottom-up), and an optimized Dynamic Programming solution.

Approach 1: Memoization (Top-Down Dynamic Programming)

This approach uses recursion with memoization to avoid redundant calculations. We define a recursive function dfs(i, j):

• i: The current day (index in the prices array).
• j: The current state (0: not holding stock, 1: holding stock).

The base case is when i reaches the end of the prices array; the maximum profit is 0. Otherwise, we explore two possibilities for each day:

1. No transaction: We recursively call dfs(i + 1, j) to explore the next day with the same state.
2. Transaction:
   • If j == 1 (holding stock), we sell the stock: dfs(i + 1, 0) + prices[i] - fee.
   • If j == 0 (not holding stock), we buy the stock: dfs(i + 1, 1) - prices[i].

We take the maximum of these possibilities. Memoization stores the results of dfs(i, j) to avoid recalculating the same subproblems.

Time Complexity: O(N), where N is the length of prices. Each state (i, j) is visited at most once. Space Complexity: O(N), due to the memoization table (in addition to the recursion stack).

Approach 2: Dynamic Programming (Bottom-Up)

This approach iteratively builds a DP table f[i][j] with the same meaning as in the memoization approach.

We initialize f[0][0] = 0 and f[0][1] = -prices[0]. Then, we iterate through the days and states, updating f[i][j] based on the recursive relations from Approach 1:

• f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i] - fee)
• f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i])

The final answer is f[n - 1][0].

Time Complexity: O(N) Space Complexity: O(N)

Approach 3: Optimized Dynamic Programming (Bottom-Up)

We can optimize the space complexity of Approach 2 to O(1) by observing that f[i][j] only depends on f[i - 1][j] and f[i - 1][1-j]. Thus, we only need two variables to track the current and previous day's states: f0 (not holding stock) and f1 (holding stock).

We initialize f0 = 0 and f1 = -prices[0]. Then, we iterate through the prices array, updating f0 and f1 using the same transition relations as in Approach 2. The final answer is f0.

Time Complexity: O(N) Space Complexity: O(1)

Code Examples (Optimized DP - Approach 3)

The optimized DP approach is generally preferred due to its efficiency. Here are examples in several languages:

Python:

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        f0, f1 = 0, -prices[0]
        for price in prices[1:]:
            f0, f1 = max(f0, f1 + price - fee), max(f1, f0 - price)
        return f0
 

Java:

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int f0 = 0, f1 = -prices[0];
        for (int i = 1; i < prices.length; ++i) {
            int temp = f0;
            f0 = Math.max(f0, f1 + prices[i] - fee);
            f1 = Math.max(f1, temp - prices[i]);
        }
        return f0;
    }
}

C++:

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int f0 = 0, f1 = -prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            int temp = f0;
            f0 = max(f0, f1 + prices[i] - fee);
            f1 = max(f1, temp - prices[i]);
        }
        return f0;
    }
};

Go:

func maxProfit(prices []int, fee int) int {
	f0, f1 := 0, -prices[0]
	for _, p := range prices[1:] {
		f0, f1 = max(f0, f1+p-fee), max(f1, f0-p)
	}
	return f0
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

JavaScript:

var maxProfit = function(prices, fee) {
    let f0 = 0, f1 = -prices[0];
    for (let i = 1; i < prices.length; ++i) {
        let temp = f0;
        f0 = Math.max(f0, f1 + prices[i] - fee);
        f1 = Math.max(f1, temp - prices[i]);
    }
    return f0;
};

These optimized DP solutions provide the most efficient way to solve the problem. Remember to choose the language and approach that best suits your needs and understanding.