Problem Statement
leetcode problem link
Top-down Dynamic Programing - Memoization [Accepted]
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
N = len(prices)
@cache
def dp(i, is_holding, remain_k):
if i == N or remain_k == 0:
return 0
ans = 0
if not is_holding:
# I buy stock
ans = max(ans, dp(i + 1, True, remain_k) - prices[i])
else:
# I sell stock
ans = max(ans, dp(i + 1, False, remain_k - 1) + prices[i])
# Do nothing - neither I buy or sell stocks
ans = max(ans, dp(i + 1, is_holding, remain_k))
return ans
return dp(0, False, k)
Editorial
Top-down Approach [Accepted]
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
@cache
def dp(i, holding, remain):
if i == len(prices) or remain == 0:
return 0
ans = dp(i + 1, holding, remain)
if holding:
ans = max(ans, prices[i] + dp(i + 1, False, remain - 1))
else:
ans = max(ans, -prices[i] + dp(i + 1, True, remain))
return ans
return dp(0, False, k)
Bottom-up Approach [Accepted]
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
n = len(prices)
dp = [[[0] * (k + 1) for _ in range(2)] for __ in range(n + 1)]
for i in range(n - 1, -1, -1):
for remain in range(1, k + 1):
for holding in range(2):
ans = dp[i + 1][holding][remain]
if holding:
ans = max(ans, prices[i] + dp[i + 1][0][remain - 1])
else:
ans = max(ans, -prices[i] + dp[i + 1][1][remain])
dp[i][holding][remain] = ans
return dp[0][0][k]