714. Best Time to Buy and Sell Stock with Transaction Fee

main.py

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        # top-down solution
#         holding_a_stock = 'HOLDING'
#         not_holding_any_stock = 'NOT_HOLDING'
        
#         @lru_cache(None)
#         def dp(i, holding_status):
#             if i == len(prices):
#                 return 0
                
#             if holding_status == not_holding_any_stock:
#                 return max(-prices[i] + dp(i+1, holding_a_stock), dp(i+1, not_holding_any_stock))
#             elif holding_status == holding_a_stock:
#                 return max(prices[i] + dp(i+1, not_holding_any_stock)  - fee , dp(i+1, holding_a_stock))

        # return dp(0, not_holding_any_stock)
        
        # bottom up 
        n = len(prices)
        dp = [[0] * 2 for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for holding in range(2):
                doing_nothing = dp[i + 1][holding]
                i_bought, i_sold = 0, 0 
                if holding:
                    i_sold = prices[i] + dp[i + 1][0] - fee
                else:
                    i_bought = -prices[i] + dp[i + 1][1]

                dp[i][holding] = max(doing_nothing, i_bought, i_sold)        

        return dp[0][0]