Others: Teaching and making beginners understand a bottom up approach to DP problems is really tough! Andrey Grehov : Hold my beer Probably the only lecture series which lives up-to its name of "Dynamic Programming for beginners". I wish you keep uploading such amazing content more frequently! Great work
true bhai they give the taste of recursion in every problem which is not intuitive many times but after watching andrew videos i realise bottom up can be intuitive and easy thanks andrew for this big fann of work
Hey I just want to say huge thanks. None of my coursework really touched DP, and even memoization is something I've rarely gotten to touch on in my own work. But DP has been a HUGE blindspot for me when preparing for coding interviews, and thanks to this series I feel SO CONFIDENT. You've broken it down for me in a way that just instantly clicked and I really appreciate it. Your series deserves more views and I can't recommend it enough to people. Thank-you.
I am so happy to have discovered this series!! Thanks Andrey! You have a gift for teaching!! Hope you make videos on other important and complex topics too!
I stumbled upon this channel while revising a few DP topics, this series is by far the best one as you've presented a very systematic and a clear approach in solving these problems. Kudos and I genuinely hope you get some free time to make more of these (maybe on backtracking or graphs) in general to help out folks. Thanks !
Wooooooooooooooooooooooow that's amazing, Thank you so much! The way you explain it is so easy adn understable I finally can Understand what is actually DP Thank you so much again!
Such a brilliant channel & content, today I've just watched the first 9 episodes without getting off for a sec. Every DP videos I'd had starts with the change-making problem and I've always kind of ended up with questions like 'how & why' at the end of those videos. But you taught me there were many prerequisites which should've gotten before. Can't wait for the next videos. and graph-related topics. Thx sir!.
Hey thank for this series of videos, a couple of months ago I had an interview on a FAANG company which I failed because I did not understand dynamic programming. This course has helped me a lot, I still don't master DP but this series of videos is helping me a lot. So again thanks.
This problem ended up being the daily coding challenge question on LeetCode on 6/29/2020. I hadn't even seen this video yet, but I was able to solve the problem in a matter of minutes because the the idea of deriving a recurrence relation in the k steps problem (sum the paths to the k previous solutions) applies to the 2d matrix context (sum the paths to the previous "up" and "left" solutions)!
Great series, Andrey! It would be great to see you walk through some of the most popular DP interview problems from top companies and applying your framework to them. Especially when it comes to graphs and searching, it gets really confusing. As the other comment mentioned, top-down would be helpful too and what exactly the difference is and how to spot it. Thanks again - appreciate the ELI5 explanations.
We can also do this same problem starting from the back, right? Because then the value on each dp would be the ways in which this point can lead you to the end Then dp[m-1][n-1] = 1, because there is only 1 way to get to the end from the end Then we would tun the for i = m-1; i
Thanks for the amazing content bro! your method stuck to my head. However I'm still not sure how to apply the same method to top-down questions like coin change, target sum, and largest square sub-matrix. I'm specifically struggling in finding the base case and to find a pattern to create the equation. If you have any tips that can help me I'd really appreciate it. Thanks
Hey Karim! Oh, these are interesting problems. We'll actually review all of them during the course. I don't know why, but iterative bottom-up approach is easier to me. If I'm not wrong, the plan is to review the Coin Change problem the following Sunday. Thank you so much for watching and commenting these videos. It's a huge motivation for me.
Sad to see you stopped, should have kept them coming, the way you explain with examples and categorize them and give frameworks to solve a problem rather than spoon feeding solutions is unique.
Huge fan of this series! I was wondering if the space complexity can be reduced further. As every time we update a value in the matrix, we only need the value to its left and the value above. So , we really do not need to store the other values. I was thinking of something like this: row = [1]*m # creating 1D array of size m for row in range(1, n): for col in range(1, m): row[col] = row[col-1] + row[col] # adding values to the left of the current cell (takes care f[i][j-1]) and adding itself (takes care of f[i-1][j]) to the current value to reuse the same row in the next iteration. return row[-1] Let me know what you think of this! @Andrey
Thank you, Arjun. It's totally possible. There is a high chance that my solutions are not the most optimal solutions out there. My goal is to teach you guys to conquer DP problems. Once you know how to approach it, optimization should not be a problem. As for your code, I haven't tested it, but from a first glance, I think it makes sense. Consider running it through a few test cases to make sure. Thanks for watching the course!
Loving the series so far, I was always confused about Dynamic Programming, but kudos to you, amazing content! Just a quick question, if u are trying to find the max profit, u say the path is 0 -> 3 -> 4 -> 4 -> 2 = 13, but should it not be 0 -> 2 -> 1 -> 3 -> 4 -> 4 -> 2 -> 0 = 16? The sub-problems look to be taking a greedy approach maybe?
Thank you so much! Appreciate it. As for your question, not really. We are only allowed to move either down or right at any point in time. So, in your example, 0 -> 2 -> 1 -> 3... we can't move from 1 to 3, because we would have to make a left move, which is not allowed. Also, as for the greedy approach, it wouldn't work in this problem. I wanted to mention it, but forgot. Check out this example: S 2 2 2 2 1 1 1 1 2 3 3 3 3 E The greedy approach would take you to the route of 2's, because 2 is always greater than 1, but such solution would not be correct. Does it make sense?
@@andreygrehov yeah makes sense, got it I didnt see it explicitly mentioned about not allowing a left anywhere, so i got confused! Thanks for the quick reply and explanation!
@Andrey Grehov Hey, great series so far. I am enjoying the tutorials. But I have a doubt on today's session. Let's say the matrix is :- S 1 1 1 10 2 1 1 1 1 2 1 1 2 E By the approach you just explained, it will choose the path S->2->2->1->1->2->E Which is not optimal, right?
maximum is calculated between the dp() function and not the a[i][j] ... when we say that max ( dp[i-1][j],dp[i][j-1]) we compare total weight to reach to that two elements of the matrix and not just the weight of the two elements ...
Would this problem/technique be possible if it it was allowed to go in any direction without "back tracking"? Rather than only being allowed to move right and down.
@@andreygrehov Thank you for your response. It's pretty quick. It's my bad, your function works. I did top down approach rather than bottom up. My code: jsfiddle.net/#&togetherjs=USfC5M5Q4o
can someone review my code? i tried solving it recursively: F(i,j){ if i > 0 AND j > 0{ best = F(i-1,j) + F(i,j-1) } if i > 0{ best = F(i-1,j) } if j>0{ best = F(i,j-1) else return 1 } return best
Next video: ua-cam.com/video/MSRTLzJDfag/v-deo.html
Previous video: ua-cam.com/video/3hHmUszRXjw/v-deo.html
4 years later from your initial upload and this is still helping me greatly. Thank you, Andrey!
I know you created this series 2 years ago, but it is a real gem for people who are just learning dynamic programming.
Thank you for this!
This series is so awesome that I will share it with all my friends at my university.
Hi
Others: Teaching and making beginners understand a bottom up approach to DP problems is really tough!
Andrey Grehov : Hold my beer
Probably the only lecture series which lives up-to its name of "Dynamic Programming for beginners". I wish you keep uploading such amazing content more frequently! Great work
true bhai they give the taste of recursion in every problem which is not intuitive many times but after watching andrew videos i realise bottom up can be intuitive and easy thanks andrew for this big fann of work
For the first time, I became fan of DP problems. Thanks a ton!!
Thank you very much for this wonderful course. I have struggled with DP problems. I am now clear after watching your videos.
These videos are going to see exponential growth! Love the content!
Oh, I wish, lol :) Thank you, Satyajit!
If anyone asked me about Dynamic Programming, I would just share this playlist.
Such a detailed course. Kudos, man!
Thanks, man!
Hey I just want to say huge thanks. None of my coursework really touched DP, and even memoization is something I've rarely gotten to touch on in my own work. But DP has been a HUGE blindspot for me when preparing for coding interviews, and thanks to this series I feel SO CONFIDENT.
You've broken it down for me in a way that just instantly clicked and I really appreciate it. Your series deserves more views and I can't recommend it enough to people. Thank-you.
Nice transition to grids man!
You've made it real easy to grasp. Thanks!
It is the best it can gets. Thanks Andrey.
I am so happy to have discovered this series!! Thanks Andrey! You have a gift for teaching!! Hope you make videos on other important and complex topics too!
I was able to solve the coin change and knapsack problem by watching this course. Great content. Keep it up!
This is the best tutorial i have seen until now thank you .
it is a very clear and well-organized series. Really appreciate your effort. I know how hard it is for a father to squeeze such an amount of time.
Thank you, Shen!
This series is super valuable! Thank you so much for making these videos Andrey!!!
I stumbled upon this channel while revising a few DP topics, this series is by far the best one as you've presented a very systematic and a clear approach in solving these problems. Kudos and I genuinely hope you get some free time to make more of these (maybe on backtracking or graphs) in general to help out folks. Thanks !
Wooooooooooooooooooooooow that's amazing, Thank you so much! The way you explain it is so easy adn understable I finally can Understand what is actually DP Thank you so much again!
Such a brilliant channel & content, today I've just watched the first 9 episodes without getting off for a sec. Every DP videos I'd had starts with the change-making problem and I've always kind of ended up with questions like 'how & why' at the end of those videos. But you taught me there were many prerequisites which should've gotten before. Can't wait for the next videos. and graph-related topics. Thx sir!.
Great tutorials so far , binged watched in one day :P
Hey thank for this series of videos, a couple of months ago I had an interview on a FAANG company which I failed because I did not understand dynamic programming. This course has helped me a lot, I still don't master DP but this series of videos is helping me a lot.
So again thanks.
Thanks for watching, Jose
Cool! your videos really help to understand dynamic programming more deeply!
Thanks Andrey, great explanation, useful course :) it’s hard to find such content
So lucky find this video, super useful!
Thank you, Hanna.
This problem ended up being the daily coding challenge question on LeetCode on 6/29/2020. I hadn't even seen this video yet, but I was able to solve the problem in a matter of minutes because the the idea of deriving a recurrence relation in the k steps problem (sum the paths to the k previous solutions) applies to the 2d matrix context (sum the paths to the previous "up" and "left" solutions)!
Thanks for this. This is amazing, your framework just works
such a great introduction !!!!
This is my 3rd playlist , m watching on DP ....& yes u r better than the best!!!
Tnks sir!! U r an inspiration!!
Shivam, thank you for kind words.
dude where are u now ? we need more video like this, this the best DP problem explanation in UA-cam
Hey Damar. Thank you. I wish I could go back to UA-cam. Extremely busy at work at AWS :(
Thank you very much. Very nice and thanks for your time. really appreciate it.
Subscribed. Brilliant series! Your communication, delivery and content are on point. Well done. Keep up the amazing work :-)
Thanks for the awesome content, Andrey! Can we discuss some problems with top down approach and see when we would actually use it?
Thank you, Niranjan. Great idea. I'll make a separate video in which we'll go over the top-down approach.
Appreciate your work!
Thank you for doing this. Well explained.
Thanks for the content
Great Videos. Fantastic. Thanks alot for your effort
Great series, Andrey! It would be great to see you walk through some of the most popular DP interview problems from top companies and applying your framework to them. Especially when it comes to graphs and searching, it gets really confusing. As the other comment mentioned, top-down would be helpful too and what exactly the difference is and how to spot it. Thanks again - appreciate the ELI5 explanations.
Thank you, Smit. Yeah, very good points. The top-down vs bottom-up is in the works. I'll release it soon.
Good news. DP well explained
Just amazing thanks
This amazing thank you so much for the tutorials bi
Thanks for the series!
We can also do this same problem starting from the back, right?
Because then the value on each dp would be the ways in which this point can lead you to the end
Then dp[m-1][n-1] = 1, because there is only 1 way to get to the end from the end
Then we would tun the for
i = m-1; i
Hey Andrey, Thanks a lot. Your Dynamic Programming course is really really big hit. Can you please make a series on backtracking and recursion.
Thanks for the amazing content bro! your method stuck to my head.
However I'm still not sure how to apply the same method to top-down questions like coin change, target sum, and largest square sub-matrix.
I'm specifically struggling in finding the base case and to find a pattern to create the equation. If you have any tips that can help me I'd really appreciate it. Thanks
Hey Karim! Oh, these are interesting problems. We'll actually review all of them during the course. I don't know why, but iterative bottom-up approach is easier to me. If I'm not wrong, the plan is to review the Coin Change problem the following Sunday. Thank you so much for watching and commenting these videos. It's a huge motivation for me.
Great explanations !!!
Great Work!!!
thank you sir so muchhhhh you are inspiration to me
I love it, thanks!
Thank you. Great explanation! 👌
nice work!!
Sad to see you stopped, should have kept them coming, the way you explain with examples and categorize them and give frameworks to solve a problem rather than spoon feeding solutions is unique.
Thanks, Nikhil. Yea, super busy at work. Don't really have time for UA-cam :(
Hey Andrey, that a great playlist, I haven't seen anything better. I'd like to have payment subscription on your tutorials!
Hehe, I actually thought about that.
thanks for share!
Wow! Thanks!!!
Really nice content!
Thank you so much!!!
Nice video ! Thanks a lot
Huge fan of this series!
I was wondering if the space complexity can be reduced further. As every time we update a value in the matrix, we only need the value to its left and the value above. So , we really do not need to store the other values.
I was thinking of something like this:
row = [1]*m # creating 1D array of size m
for row in range(1, n):
for col in range(1, m):
row[col] = row[col-1] + row[col] # adding values to the left of the current cell (takes care f[i][j-1]) and adding itself (takes care of f[i-1][j]) to the current value to reuse the same row in the next iteration.
return row[-1]
Let me know what you think of this! @Andrey
Thank you, Arjun. It's totally possible. There is a high chance that my solutions are not the most optimal solutions out there. My goal is to teach you guys to conquer DP problems. Once you know how to approach it, optimization should not be a problem.
As for your code, I haven't tested it, but from a first glance, I think it makes sense. Consider running it through a few test cases to make sure.
Thanks for watching the course!
Loving the series so far, I was always confused about Dynamic Programming, but kudos to you, amazing content!
Just a quick question, if u are trying to find the max profit, u say the path is 0 -> 3 -> 4 -> 4 -> 2 = 13, but should it not be 0 -> 2 -> 1 -> 3 -> 4 -> 4 -> 2 -> 0 = 16?
The sub-problems look to be taking a greedy approach maybe?
Thank you so much! Appreciate it. As for your question, not really. We are only allowed to move either down or right at any point in time. So, in your example, 0 -> 2 -> 1 -> 3... we can't move from 1 to 3, because we would have to make a left move, which is not allowed.
Also, as for the greedy approach, it wouldn't work in this problem. I wanted to mention it, but forgot. Check out this example:
S 2 2 2 2
1 1 1 1 2
3 3 3 3 E
The greedy approach would take you to the route of 2's, because 2 is always greater than 1, but such solution would not be correct. Does it make sense?
@@andreygrehov yeah makes sense, got it I didnt see it explicitly mentioned about not allowing a left anywhere, so i got confused! Thanks for the quick reply and explanation!
Very useful videos.but I don’t see videos in other topics.It would be more helpful for beginners if you make more videos on other DSA.
Thanks for your videos. your video makes to "Stop searching DP on the internet again".
@Andrey Grehov Hey, great series so far. I am enjoying the tutorials.
But I have a doubt on today's session. Let's say the matrix is
:-
S 1 1 1 10
2 1 1 1 1
2 1 1 2 E
By the approach you just explained, it will choose the path
S->2->2->1->1->2->E
Which is not optimal, right?
maximum is calculated between the dp() function and not the a[i][j] ...
when we say that max ( dp[i-1][j],dp[i][j-1]) we compare total weight to reach to that two elements of the matrix and not just the weight of the two elements ...
Would this problem/technique be possible if it it was allowed to go in any direction without "back tracking"? Rather than only being allowed to move right and down.
I think you would need to do a depth first search and keep track of each path. I'm not sure if there would be any DP improvement.
This series is so good it could become a tv show lol
Lol. Thanks, James! :)
thank you.
After watching your videos, I feel DP is no longer magic! Would you also consider making algorithms videos?
comment for the algo! great video
Transition function is recurrence relation, right?
Yes.
Awesome
we have a problem with this function.. max(f[i-1][j], f[i],[j-1]) it fails for this grid
5 1 50
4 2 1
4 4 1
Hey Martin, I just tried your matrix and it works well. Could you show me your code?
Here is mine: play.golang.org/p/scaVDyP1Fv-
@@andreygrehov Thank you for your response. It's pretty quick.
It's my bad, your function works. I did top down approach rather than bottom up.
My code: jsfiddle.net/#&togetherjs=USfC5M5Q4o
First view and like.
Haha, thank you, Jamshad!
isnt most profitable path greedy
First of all I want to thank you
then I want to tell you that I really did see good in you and you should really look into ISLAM ❤
can someone review my code? i tried solving it recursively:
F(i,j){
if i > 0 AND j > 0{
best = F(i-1,j) + F(i,j-1)
}
if i > 0{
best = F(i-1,j)
}
if j>0{
best = F(i,j-1)
else
return 1
}
return best
the only thing i left out was a look up table so that the code won't keep solving problems it already solved