309. Best Time to Buy and Sell Stock with Cooldown - Day 15/31 Leetcode October Challenge

Larry solves and analyzes this Leetcode problem as both an interviewer and an interviewee. This is a live recording of a real engineer solving a problem live - no cuts or edits!

#leetcode #coding #programming

[Algorithmist]

How many green days are in your future?

[CoolCat]

I really struggled with this problem (I could see an n^2 solution but I wanted n), but your way of thinking about it makes it really clear. Thank you!

[mdazharuddin]

Nice approach! I just solved all other buy and sell stock problems with this approach.

[gsb]

What you think of this approach?


class Solution:
def maxProfit(self, prices: List[int]) -> int:
cache = {}

def dp_helper(index, is_buying):
key = (index, is_buying)

if key not in cache:

if index >= len(prices):
return 0

if is_buying:
cache[key] = max(-prices[index]+ dp_helper(index+1, False), dp_helper(index+1, True))
else:
cache[key] = max(prices[index] + dp_helper(index+2, True), dp_helper(index+1, False))
return cache[key]

return dp_helper(0, True)

[Talmiz]

You didn’t link the video in the description about DP space optimisation which you mentioned in the beginning