[leetcode] 714. Best Time to Buy and Sell Stock with Transaction Fee (python)

문제: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

난이도: Medium

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).

 

풀이

class Solution:  #dp
    def maxProfit(self, prices: List[int], fee: int) -> int:
      
        sell_stock = [0 for _ in range(len(prices))]      # i번째 날에 팔았을 때
        not_sell_stock = [0 for _ in range(len(prices))]  # i번째 날에 사거나 넘어갔을 때(fee 지불)
        
        # 주식은 buy부터 시작
        sell_stock[0] = 0
        not_sell_stock[0] = -prices[0] - fee
        
        for i in range(1, len(prices)):
            sell_stock[i] = max(sell_stock[i - 1], not_sell_stock[i - 1] + prices[i])
            not_sell_stock[i] = max(sell_stock[i - 1] - prices[i] - fee, not_sell_stock[i - 1])
        
        return sell_stock[-1]

 

• sell_stock[i] : i번째 날 stock을 팔거나 가지고 있지 않을 때 최대 이익
• not_sell_stock[i] : i번째 날 stock을 사거나 계속 가지고 있을 때 최대 이익. 이 때 거래 수수료를 고려해야 한다.
• 주식은 처음에 사야지 매도할 수 있기 때문에 사는 것부터 시작한다.
• 보자마자 dp로 풀었는데 다양한 알고리즘으로도 풀 수 있다.
• 자고로 주식은 저점에서 사고 고점에서 파는게 진리이며 여기선 이것을 보장해준다.(현실에서도 부탁드려요,,)
  또한, 추가 매수가 불가하기 때문에(사면 무조건 팔아야 한다.) greedy 알고리즘으로도 충분히 풀 수 있다.