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

 

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

 

https://youtu.be/cUsPoH5DG1Q?si=vWqiiqYgUO8o6U1N

 

Code

 

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)

        # buy[i]: i번째 날에 주식을 구매한 상태에서의 최대 이익
        # sell[i]: i번째 날에 주식을 판매한 상태에서의 최대 이익
        buy = [0] * n
        sell = [0] * n

        # 초기값:
        # 첫 번째 날에 주식을 구매한 경우: -prices[0]
        buy[0] = -prices[0]
        # 첫 번째 날에 주식을 판매하지 않으면 이익은 0
        sell[0] = 0

        for i in range(1, n):
            # 오늘 새로 주식을 구매:
            # 1. 이전날에 이미 주식을 구매한 상태 유지: buy[i-1]
            # 2. 이전날에 주식을 판매한 상태에서 오늘 주식을 새로 구매: sell[i-1] - prices[i]
            buy[i] = max(buy[i-1], sell[i-1] - prices[i])

            # 오늘 새로 주식을 판매:
            # 1. 이전날에 이미 주식을 판매한 상태 유지: sell[i-1]
            # 2. 이전날에 주식을 구매한 상태에서 오늘 주식을 새로 판매: buy[i-1] + prices[i] - fee
            sell[i] = max(sell[i-1], buy[i-1] + prices[i] - fee)

        return sell[-1]  # 마지막 날에 주식을 판매한 상태에서의 최대 이익 반환

 

두번째

 

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:        
        n = len(prices)
        cash, hold = [0] * n, [0] * n
        cash[0] = 0  # 주식을 보유하지 않은 상태에서의 이익
        hold[0] = -prices[0]  # 첫날 주식을 구매한 상태에서의 이익

        for i in range(1, n):
            # 주식을 판매하거나, 아무것도 하지 않음
            cash[i] = max(cash[i-1], hold[i-1]+prices[i]-fee)  
            # 주식을 구매하거나, 보유 상태 유지
            hold[i] = max(hold[i-1], cash[i-1]-prices[i])  

        return cash[-1]  # 최종적으로 주식을 보유하지 않은 상태에서의 최대 이익 반환

 

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        cash = 0  # 주식을 보유하지 않은 상태에서의 이익
        hold = -prices[0]  # 첫날 주식을 구매한 상태에서의 이익

        for price in prices[1:]:
        	# 주식을 판매하거나, 아무것도 하지 않음
            cash = max(hold+price-fee, cash)
            # 주식을 구매하거나, 보유 상태 유지
            hold = max(hold, cash-price)
        return cash  # 최종적으로 주식을 보유하지 않은 상태에서의 최대 이익 반환

 

 

캐슁으로.. 

 

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        dp = {} # 캐싱을 위한 해시맵 (날짜, 상태) -> 최대 이익

        def dfs(i, buying):
            if i >= len(prices):
                return 0
            
            if (i, buying) in dp:
                return dp[(i, buying)]
            
            cooldown = dfs(i+1, buying) # 아무것도 안함, 가만히 있음
            if buying: # 사거나 or 가만히 있거나 
                buy = dfs(i+1, not buying) - prices[i]
                dp[(i, buying)] = max(cooldown, buy)            
            else: # 팔거나 or 가만히 있거나
                sell = dfs(i+1, not buying) + prices[i] - fee
                dp[(i, buying)] = max(cooldown, sell)

            return dp[(i, buying)]

        return dfs(0, True) #  # 첫 번째 날부터 시작하며, 처음에는 주식을 구매할 수 있음