Problem Statement
leetcode problem link
My Solution [Accepted]
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
memo = {}
def dp(i, is_buy):
if i == len(prices):
return 0
if (i, is_buy) in memo:
return memo[(i, is_buy)]
buy = sell = skip = 0
if is_buy:
buy = dp(i + 1, False) - prices[i]
else:
sell = dp(i + 1, True) + prices[i] - fee
skip = dp(i + 1, is_buy)
memo[(i, is_buy)] = max(buy, sell, skip)
return memo[(i, is_buy)]
return dp(0, True)
Editorial
Approach 1: Dynamic Programming
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
hold, free = [0] * n, [0] * n
# In order to hold a stock on day 0, we have no other choice but to buy it for prices[0].
hold[0] = -prices[0]
for i in range(1, n):
hold[i] = max(hold[i - 1], free[i - 1] - prices[i])
free[i] = max(free[i - 1], hold[i - 1] + prices[i] - fee)
return free[-1]
Approach 2: Space-Optimized Dynamic Programming
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
hold, free = -prices[0], 0
for i in range(1, n):
tmp = hold
hold = max(hold, free - prices[i])
free = max(free, tmp + prices[i] - fee)
return free