[Problem] Best Time to Buy and Sell Stock with Transaction Fee

Problem Description

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction 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 transaction fee is only charged once for each stock purchase and sale.

Examples

Example 1:
Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:

• Buying at prices[0] = 1
• Selling at prices[3] = 8
• Buying at prices[4] = 4
• Selling at prices[5] = 9
  The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Example 2:
Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6

Approach

Due to the given constraints in the problem: we can have two states:

1. We are holding stock, where we can only sell
2. We are not holding stock, where we can only buy

Hence, through a boolean value, we must consider the holding status while iterating through the table through dynamic programming.

Our dynamic programming array dp[i] should also have two states:

• The maximum profit when free of stock.
• The maximum profit when holding the stock.

This can be represented like below:

dp(i, holding) = max(skip, buy, sell) where

skip = dp(i + 1, holding),

buy = -prices[i] + dp(i + 1, true) and only considered if holding = false,

sell = prices[i] + dp(i + 1, false) - fee and only considered if holding = true.

To approach the problem from a top-down approach, we must start from the base case where i == len(list), and iterate through the reverse direction.

Solution

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        dp = [([0] * 2) for _ in range(n + 1)]
        
        for i in reversed(range(n)):
            for hold in range(2):
                ans = dp[i + 1][hold]
                if hold:
                    ans = max(ans, prices[i] + dp[i + 1][0] - fee)
                else:
                    ans = max(ans, -prices[i] + dp[i + 1][1])
                
                dp[i][hold] = ans

        return dp[0][0]