Problem Statement
leetcode problem link
Memoization [Accepted]
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
@cache
def dp(i, is_holding):
if i == len(prices):
return 0
ans = 0
# can substract the fee in either buy or sell
if not is_holding:
# buy stock
ans = max(ans, dp(i + 1, True) - prices[i]) - fee
else:
# sell stock
ans = max(ans, dp(i + 1, False) + prices[i])
# do nothing
ans = max(ans, dp(i + 1, is_holding))
return ans
return dp(0, False)
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