thats literally a template for almost all of the "Buy and Sell Stock" Problems on Leetcode. So much more easy to understand and come up with during an interview then the state-machine approach. Thank you Sir!
I think it would be helpful if you think of the buying state as "looking to buy" state. When it is negative, it means that we have already bought or are calculating what happens if we wait. After we sell, we want to "look to buy" two indexes in the future.
The gods have listened! I was looking your solution to this problem and you helped incredibly. Thank you! The answers posted on LC aren’t very well explained to poor wording
Thank you so much, I think you are the best on youtube explaining these. I especially like the fact that you explain the solution without the code first. For this problem I think calling the parameter "buying" is not exact, it's more like "canbuy" in my understanding.
you can make it a bit faster if you consider the fact that you should only buy at local mins, but the overall time complexity is still the same. def maxProfit(self, prices: List[int]) -> int:
DP = {}
def stock(i, buy): if i >= len(prices): return 0
if (i, buy) in DP: return DP[(i, buy)]
if buy: j = i while j < len(prices)-1 and prices[j] > prices[j+1]: #look for local min j += 1 b = stock(j+1, not buy) - prices[j] #buy at local min c = stock(j+1, buy) DP[(i, buy)] = max(b, c)
else: s = stock(i+2, not buy) + prices[i] c = stock(i+1, buy) DP[(i, buy)] = max(s, c)
Great explanation. The verbosity of the problem is intimidating but your explanation makes it much simpler, it makes sense as a DP problem. Amazing job as always :)
A great explanation again. My dilemma is if one hasn't seen the solution before or solved it on one's own, it would really, really hard to come up with a solution in an actual interview of 45 minutes (unless one is brilliant like you!) The other thing is one rarely needs to solve such a problem in real life. The problems that are encountered are more mundane and easy to resolve. If one does encounter such a problem, one would definitely have more than 45 minutes to solve (perhaps several days)
I had the same mindset as you for these types of problems in general. What I have realized however that this approach is simply incorrect. Whether or not you may or may not encounter such or similar problems in the wild doesn't matter at all. Your ability to solve novel problems with time or other constraints does. And this skill can only be trained by problem solving. Think of your brains ability to solve random problems as a muscle. Keeping with the analogy, to have a good performing brain, you have to train it in ways it isn't used to.
@Neetcode, Thanks for the simple explanation. Pasting the exact solution in java, just in case someone is looking for it. public int maxProfit(int[] prices) { return maxProfit(prices,0,true,new HashMap()); } public int maxProfit(int[] prices,int i,boolean buying,Map map){ if(i>=prices.length) return 0; if(map.containsKey(i+"-"+buying)) return map.get(i+"-"+buying); if(buying){ int buy = maxProfit(prices,i+1,!buying,map)-prices[i]; int cd = maxProfit(prices,i+1,buying,map); map.put(i+"-"+buying, Math.max(buy,cd)); }else{ int sell = maxProfit(prices,i+2,!buying,map)+prices[i]; int cd = maxProfit(prices,i+1,buying,map); map.put(i+"-"+buying, Math.max(sell,cd)); } return map.get(i+"-"+buying); }
"I'm going to make this problem look like a joke today, not because I'm smart, but only because I know how to draw a picture" My man went from 🤓to😎real quick
the use of the word cooldown confused me a lot, but for anyone reading this, he uses it to refer a day when you CHOOSE to not do anything, while the problem uses it to refer to the day after you sell when you are FORCED to not do anything, which in his code is handled by the i+2 in the else statement.
Is there a way to do this bottom-up? When you're solving these problems how do you decide whether to just implement top-down (after figuring out brute force) or continue and try to implement bottom-up? Thanks so much!
buy_prof, sell_prof, sell_prof2 = -1e5, 0, 0 for p in prices: buy_prof = max(buy_prof, sell_prof2-p) sell_prof2 = sell_prof sell_prof = max(sell_prof, buy_prof+p) return sell_prof beats 99.8% buy_prof = maximum profit if last or current action is buying sell_prof = maximum profit if last or current action is selling sell_prof2 = previous sell_prof
14:55 for line 21, shouldn't cooldown be equals to dfs(i + 1, not buying) instead of dfs(i + 1, buying)? Since you have chosen to not sell and to have a cooldown instead, then as the index increments you CANNOT buy until you sell. dfs(i + 1, buying) would mean that you can choose to not sell, and then buy more stock before selling, which isn't allowed per the description rules.
@@jerrychan3055 you add this line to the buy if check: cooldown := dfs(i+1, 0) and this line to the sell if check. cooldown := dfs(i+1, 1) , In my solution, 0 == buying, selling == 1. The point is the cooldown dfs is different for buying and selling state
I managed to do this with in a slightly simpler way such that dfs only takes the index of the array (and dp is just a 1d list): ``` class Solution: def maxProfit(self, prices: List[int]) -> int: dp = {} def dfs(i): # base case: out of bounds if i >= len(prices): return 0 # base case: dp if i in dp: return dp[i] # inductive case buycost = prices[i] maxprof = 0 for j in range(i + 1, len(prices)): # sell at this position sellcost = prices[j] prof = sellcost + dfs(j + 2) - buycost if prof > maxprof: maxprof = prof dp[i] = maxprof return dp[i] return max([dfs(n) for n in range(len(prices))]) ```
Damn, that's a nice way of thinking about it. I was trying to and able to solve it, but my solution wasn't as efficient and was only better than 10% of the solutions (O(n^2) complexity). Looked at this video and realized my way of caching/memoizing was the issue. Thinking about it in terms of just two decisions is so clever!
He explained the optimal solution, which requires dp since the complexity of recursive solution is 2^n. The use case of dp in general is to reuse existing solutions to significantly reduce time complexity, in this case reducing time complexity to O(n) since each node in memory is computed exactly once.
Will not pass all the test cases as of now, one failed case is [2,1,2,1,0,1,2] and max profit should be 3. Instead, we can consider has stock or not: def maxProfit(self, prices: List[int]) -> int: n = len(prices) dp = {} def dfs(i, has_stock): if i >= n: return 0 if (i, has_stock) in dp: return dp[(i, has_stock)] if not has_stock: buy = dfs(i + 1, True) - prices[i] cooldown = dfs(i + 1, False) dp[(i, has_stock)] = max(buy, cooldown) else: sell = dfs(i + 2, False) + prices[i] cooldown = dfs(i + 1, True) dp[(i, has_stock)] = max(sell, cooldown) return dp[(i, has_stock)] return dfs(0, False)
I'm a little embarassed, i didn't understand the coding solution. Don't you have to put a loop on the "i" and how can you call a function within it like def dfs(i, buying): and then buy = dfs(i + 1, not buying) in the function. I feel like there's a lot of background theory and code that i don't know yet.
Thanks for the amazing video, made it very simple to understand. Can you please add a video for "Best Time to Buy and Sell Stocks with Transaction Fee" also, and explain how different it is from the cooldown version? Thanks in advance.
good website and good explanation, but not-ideal naming, took me forever to figure out; should've just asked GPT to write a dfs memo version for me. also I would think learning only-recursion solution is dangerous for anyone who want a good understanding. think for more.
I have already implemented the top-down(memoization) method and then wasted 4 hours in thinking for a tabulation method. I came here for tabulation method, why didn't he implemented it in tabulation method?
Why do we have a cooldown state for buying? I thought cooldown only applies after we sell? Is the cooldown here more like a "skip buying or selling this stock" ?
Once you have bought a share you can either Sell it or you not sell it. Not selling can be thought of as Cooldown where you are not involved in any transaction. Eitherway of thinking will result in unchanged profit.
13:30 I still don't get it why sell = dfs(i+2, not buying) + price but not dfs(i+2, buying) + price, since after the cooldown, it's allowed to buy again right?
@@happymind6908 but dfs(i + 1, not buying) will also be ''true" for buying right? but we cannot buy again right? i don't get why both buy and sell go with ''not buying"
@@ziyangji9485 not buying=False for the buying if statement block. The if statement block for buying executes if buying=True. So buy=dfs(idx+1, not buying) is equivalent to dfs(idx+1, not True), i.e. False The else block for selling executes if buying=False. So sell=dfs(idx+2, not buying) is equivalent to dfs(idx+2, not False), i.e. True here is the code using True/False instead of buying/not buying: class Solution: def maxProfit(self, prices): dp = {} def dfs(idx, buying): if idx >= len(prices): return 0 if (idx, buying) in dp: return dp[(idx, buying)] if buying: buy = dfs(idx+1, False) - prices[idx] cooldown = dfs(idx+1, True) dp[(idx, buying)] = max(buy, cooldown) else: sell = dfs(idx+2, True) + prices[idx] cooldown = dfs(idx+1, False) dp[(idx, buying)] = max(sell, cooldown) return dp[(idx, buying)] return dfs(0, True)
cooldown could better be called 'do nothing' because thats what is really happening. The actual cooldown after selling is skipped over because there is no point in calculating (thats why we do i+2 when selling, we jump over the index because we would have just skipped it anyways). If you look at the decision tree, there is only 1 option after selling and that is to skip the next position, so why not just jump over it? Basically, we arent forced to sell, so we need to choose to either sell at this position or do nothing at this position. Thats why cooldown for selling is i+1, think of it as 'do nothing' instead.
i dont understand the caching .... we are going to save the dp[i,buying] but i,buying can be same for the multiple positions like if our 1st example suggest that for: buy->sell->cooldown->buy->sell dp[4,sell]=+3, but for : cooldown ->cooldown->cooldown-> buy->sell it will again have dp[4,sell]=+2 same dp position have different values?? how is the caching working here?? can anyone explain and help me ...????
I managed to solve this problem with just a 1-D DP memo. However, it seems to run much slower than your solution. Could someone explain the differences and why this is? Code: class Solution: def maxProfit(self, prices: List[int]) -> int:
memo = [None for _ in range(len(prices))]
def dp(i): # func assumes we are ready to buy! if i >= len(prices): return 0 if memo[i] is not None: return memo[i]
maxProfit = dp(i + 1) # represents not buying for j in range(i + 1, len(prices)): # j is a location we can sell at maxProfit = max( maxProfit, prices[j] - prices[i] + dp(j + 2) # j + 2 is a location we can think abt buying again ) memo[i] = maxProfit return maxProfit
Your time cmoplexity is O(n^2) because you're iterating over the range while inside the `dp` function you've written! It's technically more like O(n * n / 2) but still exponential
Simpler solution : # dp[i][j] -> max profit with stock bought on i and sold on j # dp[i][j] -> prices[j] - prices[i] + max profits until i - 2 class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) < 2: return 0 maxes = [0] * len(prices) for i in range(len(prices)): for j in range(i + 1, len(prices)): adder = 0 if i >=2: adder = maxes[i-2] maxes[j] = max(maxes[j], prices[j] - prices[i] + adder, maxes[j-1]) return maxes[-1] Space complexity : O(n) Time complexity: O(n^2)
thats literally a template for almost all of the "Buy and Sell Stock" Problems on Leetcode. So much more easy to understand and come up with during an interview then the state-machine approach. Thank you Sir!
Yeah, with this approach you can solve 714. Best Time to Buy and Sell Stock with Transaction Fee.
I think it would be helpful if you think of the buying state as "looking to buy" state. When it is negative, it means that we have already bought or are calculating what happens if we wait. After we sell, we want to "look to buy" two indexes in the future.
The gods have listened! I was looking your solution to this problem and you helped incredibly. Thank you! The answers posted on LC aren’t very well explained to poor wording
Thank you so much, I think you are the best on youtube explaining these. I especially like the fact that you explain the solution without the code first.
For this problem I think calling the parameter "buying" is not exact, it's more like "canbuy" in my understanding.
That's a good point, I think "canbuy" is definitely a better name for it.
you can make it a bit faster if you consider the fact that you should only buy at local mins, but the overall time complexity is still the same.
def maxProfit(self, prices: List[int]) -> int:
DP = {}
def stock(i, buy):
if i >= len(prices):
return 0
if (i, buy) in DP:
return DP[(i, buy)]
if buy:
j = i
while j < len(prices)-1 and prices[j] > prices[j+1]: #look for local min
j += 1
b = stock(j+1, not buy) - prices[j] #buy at local min
c = stock(j+1, buy)
DP[(i, buy)] = max(b, c)
else:
s = stock(i+2, not buy) + prices[i]
c = stock(i+1, buy)
DP[(i, buy)] = max(s, c)
return DP[(i, buy)]
return stock(0, True)
Thank you so much. I was struggling with this problem earlier in the day! Love your explanations
Great explanation. The verbosity of the problem is intimidating but your explanation makes it much simpler, it makes sense as a DP problem.
Amazing job as always :)
I struggled with this one a whole afternoon and your video just saved my day!
A great explanation again. My dilemma is if one hasn't seen the solution before or solved it on one's own, it would really, really hard to come up with a solution in an actual interview of 45 minutes (unless one is brilliant like you!)
The other thing is one rarely needs to solve such a problem in real life. The problems that are encountered are more mundane and easy to resolve. If one does encounter such a problem, one would definitely have more than 45 minutes to solve (perhaps several days)
I had the same mindset as you for these types of problems in general. What I have realized however that this approach is simply incorrect.
Whether or not you may or may not encounter such or similar problems in the wild doesn't matter at all. Your ability to solve novel problems with time or other constraints does.
And this skill can only be trained by problem solving. Think of your brains ability to solve random problems as a muscle. Keeping with the analogy, to have a good performing brain, you have to train it in ways it isn't used to.
@@Qwantopides These are fairly standard problems after doing around 10-15 dp problem you would see the same patterns
Your lazy ass, looking for excuse not to do the problems
I'm amazed by the neetness of your code and clarity for this problem!
@Neetcode, Thanks for the simple explanation. Pasting the exact solution in java, just in case someone is looking for it.
public int maxProfit(int[] prices) {
return maxProfit(prices,0,true,new HashMap());
}
public int maxProfit(int[] prices,int i,boolean buying,Map map){
if(i>=prices.length)
return 0;
if(map.containsKey(i+"-"+buying))
return map.get(i+"-"+buying);
if(buying){
int buy = maxProfit(prices,i+1,!buying,map)-prices[i];
int cd = maxProfit(prices,i+1,buying,map);
map.put(i+"-"+buying, Math.max(buy,cd));
}else{
int sell = maxProfit(prices,i+2,!buying,map)+prices[i];
int cd = maxProfit(prices,i+1,buying,map);
map.put(i+"-"+buying, Math.max(sell,cd));
}
return map.get(i+"-"+buying);
}
I love the idea of deducting the price from profit when you buy the stock, simple trick but make it a lot easier
I really wish you went over the state machine DP solution. Would have loved to see your explanation of it.
Dude just found your channel and its amazing!!! Keep up the great work.
"I'm going to make this problem look like a joke today, not because I'm smart, but only because I know how to draw a picture" My man went from 🤓to😎real quick
the use of the word cooldown confused me a lot, but for anyone reading this, he uses it to refer a day when you CHOOSE to not do anything, while the problem uses it to refer to the day after you sell when you are FORCED to not do anything, which in his code is handled by the i+2 in the else statement.
Is there a way to do this bottom-up? When you're solving these problems how do you decide whether to just implement top-down (after figuring out brute force) or continue and try to implement bottom-up? Thanks so much!
This is bottom up he returns a zero and then keeps adding as he keeps going up the recursion tree.
buy_prof, sell_prof, sell_prof2 = -1e5, 0, 0
for p in prices:
buy_prof = max(buy_prof, sell_prof2-p)
sell_prof2 = sell_prof
sell_prof = max(sell_prof, buy_prof+p)
return sell_prof
beats 99.8%
buy_prof = maximum profit if last or current action is buying
sell_prof = maximum profit if last or current action is selling
sell_prof2 = previous sell_prof
@@roshansaundankar4893 No, this is top-down DP. Bottom-up DP doesn't use recursion.
Hash for cache -> top down
dp = [[0] * 2 for _ in range(len(prices) + 2)]
for cur in range(len(prices) - 1, -1, -1):
for canBuy in [0, 1]:
skip = dp[cur + 1][canBuy]
if canBuy:
do = dp[cur + 1][0] - prices[cur]
else:
do = dp[cur + 2][1] + prices[cur]
dp[cur][canBuy] = max(skip, do)
return dp[0][1]
Thank you so much for the smooth explanation. Your videos always help. Cheers!
14:55 for line 21, shouldn't cooldown be equals to dfs(i + 1, not buying) instead of dfs(i + 1, buying)?
Since you have chosen to not sell and to have a cooldown instead, then as the index increments you CANNOT buy until you sell. dfs(i + 1, buying) would mean that you can choose to not sell, and then buy more stock before selling, which isn't allowed per the description rules.
Yes, I agree. It looks to me like someone added a test case where the code he posted does not work, because as you stated line 21 is incorrect.
@@dj1984x so how could we modify the code?
@@jerrychan3055 you add this line to the buy if check: cooldown := dfs(i+1, 0) and this line to the sell if check. cooldown := dfs(i+1, 1) , In my solution, 0 == buying, selling == 1. The point is the cooldown dfs is different for buying and selling state
Super cool that you included the code in the description! Keep it up!
I managed to do this with in a slightly simpler way such that dfs only takes the index of the array (and dp is just a 1d list):
```
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp = {}
def dfs(i):
# base case: out of bounds
if i >= len(prices):
return 0
# base case: dp
if i in dp:
return dp[i]
# inductive case
buycost = prices[i]
maxprof = 0
for j in range(i + 1, len(prices)):
# sell at this position
sellcost = prices[j]
prof = sellcost + dfs(j + 2) - buycost
if prof > maxprof:
maxprof = prof
dp[i] = maxprof
return dp[i]
return max([dfs(n) for n in range(len(prices))])
```
Can you do the other variations also?
1 transaction
2 transactions
at most k transactions
Thank you so much! I've been waiting for this
No problem, happy to help
Damn, that's a nice way of thinking about it. I was trying to and able to solve it, but my solution wasn't as efficient and was only better than 10% of the solutions (O(n^2) complexity). Looked at this video and realized my way of caching/memoizing was the issue. Thinking about it in terms of just two decisions is so clever!
Really appreciate your video. It's easy to understand, rather than some kinda state machine
Great explanation!!! True, you are good at drawing, I was able to solve puzzle iii and iv with the same drawing technique you used :)
Thanks for your great video! It would be better if you call "buying" state "buyingOrCooldown" and call "sell" state "sellOrColldown".
was able to do buy and sell stock with transaction fee with the same approach. Thanks
I don't think DFS was needed in this case. It's making it more complicated. But anyways I follow your tutorials for the explanation which are amazing.
i agree
He explained the optimal solution, which requires dp since the complexity of recursive solution is 2^n. The use case of dp in general is to reuse existing solutions to significantly reduce time complexity, in this case reducing time complexity to O(n) since each node in memory is computed exactly once.
my js solution:
var maxProfit = function (prices) {
const states = ['B', 'S', 'C'];
const memo = new Map();
function backtrack(step, index) {
if (index === prices.length) return 0;
const currState = states[step % 3];
const k = `${index}-${currState}`;
if (memo.has(k)) return memo.get(k);
let res = 0;
for (let i = index; i < prices.length; i++) {
let price = prices[i];
if (currState === 'B') {
price *= -1;
}
if (currState === 'C') {
price = 0;
}
const btr = backtrack(step + 1, i + 1) + price;
memo.set(k, Math.max(memo.get(k) || 0, btr))
res = Math.max(res, btr);
}
return res;
}
return backtrack(0, 0);
};
Will not pass all the test cases as of now, one failed case is [2,1,2,1,0,1,2] and max profit should be 3.
Instead, we can consider has stock or not:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = {}
def dfs(i, has_stock):
if i >= n: return 0
if (i, has_stock) in dp: return dp[(i, has_stock)]
if not has_stock:
buy = dfs(i + 1, True) - prices[i]
cooldown = dfs(i + 1, False)
dp[(i, has_stock)] = max(buy, cooldown)
else:
sell = dfs(i + 2, False) + prices[i]
cooldown = dfs(i + 1, True)
dp[(i, has_stock)] = max(sell, cooldown)
return dp[(i, has_stock)]
return dfs(0, False)
@jerrychan3055 Can you please explain why the Neetcode solution doesn't work for this test case and yours does?
This explanation is very clear and on point. Thanks !!!!!
dfs with cache is much slower than the optimal solution. would love to see a series where you go back over these old videos and revise the solution
What’s the optimal?
Beautiful, man. I appreciate your videos.
I'm a little embarassed, i didn't understand the coding solution. Don't you have to put a loop on the "i" and how can you call a function within it like def dfs(i, buying): and then buy = dfs(i + 1, not buying) in the function. I feel like there's a lot of background theory and code that i don't know yet.
You should probably watch some videos on recursion
Great job! What tool Are you using for drawing?
Great Explanation, Thanks!
Thanks for the amazing video, made it very simple to understand.
Can you please add a video for "Best Time to Buy and Sell Stocks with Transaction Fee" also, and explain how different it is from the cooldown version? Thanks in advance.
Great solution. Thank You
can u please do best time to buy and sell stock iv? cant find good explanation video for that one
yeah the variable here is confusing, replace buying to canbuy
How did you come up with caching key?
This is the greatest channel
Something which I dont understand, there are multiple nodes with (i, buying), how does memoization work correctly in this case?
So clean so precise 😍
good website and good explanation, but not-ideal naming, took me forever to figure out; should've just asked GPT to write a dfs memo version for me.
also I would think learning only-recursion solution is dangerous for anyone who want a good understanding. think for more.
Great solution, thanks!
I have already implemented the top-down(memoization) method and then wasted 4 hours in thinking for a tabulation method. I came here for tabulation method, why didn't he implemented it in tabulation method?
This is an insanely hard question imo . Shouldnt give it a "medium" at all!
dude, thanks for the great work
The way you wrote buy with red and sell with green reminded me of crypto.. Great solution!! Keep it up.
thx for ur video again. you saved me a lot of time!
Awesome explanation. Thanks
There is also a DP solution for this problem.
I know im late but can I have an iterative solution from any of y’all?
def maxProfit(self, prices: List[int]) -> int:
buy_cache = (len(prices)+2) * [0]
sell_cache = (len(prices)+2) * [0]
for i in range(len(prices)-1,-1,-1):
buy_cache[i]=max(-prices[i]+sell_cache[i+1],buy_cache[i+1])
sell_cache[i]=max(prices[i]+buy_cache[i+2],sell_cache[i+1])
return buy_cache[0]
This was SO helpful
great explanation
You should add a donate button! Every time I get a question that you have a video on, I will donate 5 bucks!
Why do we have a cooldown state for buying? I thought cooldown only applies after we sell? Is the cooldown here more like a "skip buying or selling this stock" ?
Once you have bought a share you can either Sell it or you not sell it. Not selling can be thought of as Cooldown where you are not involved in any transaction. Eitherway of thinking will result in unchanged profit.
cooldown is choice not an enforced decision in case when we buy
I did an assignment similar to this on Java it was an electronic trading platform
The base case in dfs is so hard to come up with, esp the second base case, almost impossible for me.
does including the cooldown in if else instead of before if else result in fewer function calls?
I had solve this problem only after seeing your diagram.
Where is Buy or sell III video? We miss it
Its very helpful
13:30 I still don't get it why sell = dfs(i+2, not buying) + price but not dfs(i+2, buying) + price, since after the cooldown, it's allowed to buy again right?
because "buying" is in false state and you want to make it "true" for buying, so "not buying(false)" will make it true
@@happymind6908 Thank you so much!
@@happymind6908 but dfs(i + 1, not buying) will also be ''true" for buying right? but we cannot buy again right? i don't get why both buy and sell go with ''not buying"
This part got me so confused as well. Would have been a lot clearer if True/False passed in instead of buying/not buying
@@ziyangji9485 not buying=False for the buying if statement block.
The if statement block for buying executes if buying=True. So buy=dfs(idx+1, not buying) is equivalent to dfs(idx+1, not True), i.e. False
The else block for selling executes if buying=False. So sell=dfs(idx+2, not buying) is equivalent to dfs(idx+2, not False), i.e. True
here is the code using True/False instead of buying/not buying:
class Solution:
def maxProfit(self, prices):
dp = {}
def dfs(idx, buying):
if idx >= len(prices):
return 0
if (idx, buying) in dp:
return dp[(idx, buying)]
if buying:
buy = dfs(idx+1, False) - prices[idx]
cooldown = dfs(idx+1, True)
dp[(idx, buying)] = max(buy, cooldown)
else:
sell = dfs(idx+2, True) + prices[idx]
cooldown = dfs(idx+1, False)
dp[(idx, buying)] = max(sell, cooldown)
return dp[(idx, buying)]
return dfs(0, True)
I don't get why the cooldown for selling is not `cooldown = dfs(i+2,buying)'
cooldown could better be called 'do nothing' because thats what is really happening. The actual cooldown after selling is skipped over because there is no point in calculating (thats why we do i+2 when selling, we jump over the index because we would have just skipped it anyways). If you look at the decision tree, there is only 1 option after selling and that is to skip the next position, so why not just jump over it?
Basically, we arent forced to sell, so we need to choose to either sell at this position or do nothing at this position. Thats why cooldown for selling is i+1, think of it as 'do nothing' instead.
Damn it I almost got this one, I missed i+2 for sell. I still think it is i+1.
i dont understand the caching ....
we are going to save the dp[i,buying] but i,buying can be same for the multiple positions like if
our 1st example suggest that
for: buy->sell->cooldown->buy->sell
dp[4,sell]=+3,
but for : cooldown ->cooldown->cooldown-> buy->sell
it will again have dp[4,sell]=+2
same dp position have different values??
how is the caching working here??
can anyone explain and help me ...????
Why is it included in 2d dp problems in neetcode?
prices : List[int]) -> int:
What semantic is this in Py?
Just type hints I think, they are not enforced tho
very good video
I dont know if I you could ever come up with this solution on my own
I managed to solve this problem with just a 1-D DP memo. However, it seems to run much slower than your solution. Could someone explain the differences and why this is?
Code:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
memo = [None for _ in range(len(prices))]
def dp(i): # func assumes we are ready to buy!
if i >= len(prices):
return 0
if memo[i] is not None:
return memo[i]
maxProfit = dp(i + 1) # represents not buying
for j in range(i + 1, len(prices)): # j is a location we can sell at
maxProfit = max(
maxProfit,
prices[j] - prices[i] + dp(j + 2) # j + 2 is a location we can think abt buying again
)
memo[i] = maxProfit
return maxProfit
return dp(0)
Your time cmoplexity is O(n^2) because you're iterating over the range while inside the `dp` function you've written! It's technically more like O(n * n / 2) but still exponential
@@mattmendez8860 I see, thank you!
This is top-down DP right?
yes recursion + memoization
memo = {}
def buy_sell_cooldown(prices, buy, i=0, profit=0):
if i >= len(prices):
return profit
key = (i, buy)
if key in memo:
return memo[key]
cooldown = buy_sell_cooldown(prices, buy, i+1, profit)
if buy:
bought = buy_sell_cooldown(prices, False, i+1, profit - prices[i])
memo[key] = max(bought, cooldown)
else:
sell = buy_sell_cooldown(prices, True, i+2, profit + prices[i])
memo[key] = max(sell, cooldown)
return memo[key]
Why is this not working? Recursion without memo is giving correct output but as soon as I introduce memo it messes the output up.
there is an O(n) greedy solution i guess, no dp, no table, no memo
there is also a O(1) space solution can you please explain it (like a follow up on this video)...
You put dp, caching ,dfs, recursion into one and make a blend out of it after drewing it, not much efficient but still insanely genius man!!!
what would be the space complexity for this?
also O(n)
Hello can you tell me what ide you use??
I use the leetcode ide with the theme changed to 'monokai'
Thnxx man...
fast than 35.40% is pretty efficient ? why don't you turn the DFS into 3D-finite state machine to reduce the time and space cost ?
Not all heroes wear a Cape...thanks a lot
Me who shorts in the stock market....WHY CAN'T I SELL BEFORE BUYING!!!
"I will make this question a joke today, just cause I can draw a picture" - Neetcode
Neet: I came up with a genius solution and here is how it works
Parents 15:02: Why not 100% faster?
THIS DOES NOT WORK FOR [1,2,4]
I just checked: it does work for [1,2,4]
Simpler solution :
# dp[i][j] -> max profit with stock bought on i and sold on j
# dp[i][j] -> prices[j] - prices[i] + max profits until i - 2
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) < 2:
return 0
maxes = [0] * len(prices)
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
adder = 0
if i >=2:
adder = maxes[i-2]
maxes[j] = max(maxes[j], prices[j] - prices[i] + adder, maxes[j-1])
return maxes[-1]
Space complexity : O(n)
Time complexity: O(n^2)
giving TLE in c++ with same code
14:56, can initial buying state also be false? e.g. return Math.max(dfs(0, true), dfs(0, false))
No, if you set it to false that means you would be selling on the 0th day, which is not possible since you don't own any stock on the 0th day