09 - Unique Paths (Dynamic Programming for Beginners)

[@andreygrehov]

Next video: kzbin.info/www/bejne/g4S1hX-wf6mZl8k Previous video: kzbin.info/www/bejne/aZmrnoipr7eLoNk

[@denver-reed]

4 years later from your initial upload and this is still helping me greatly. Thank you, Andrey!

[@LinkyLess]

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!

[@raghavddps2]

This series is so awesome that I will share it with all my friends at my university.

[@ytg6663]

Hi

[@shatadruroy3926]

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

[@AkkumBakkum-m5h]

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

[@33galactus]

For the first time, I became fan of DP problems. Thanks a ton!!

[@satyajitkamble1646]

These videos are going to see exponential growth! Love the content!

[@andreygrehov]

Oh, I wish, lol :) Thank you, Satyajit!

[@swathi.139]

Thank you very much for this wonderful course. I have struggled with DP problems. I am now clear after watching your videos.

[@MukilShelby]

If anyone asked me about Dynamic Programming, I would just share this playlist. Such a detailed course. Kudos, man!

[@andreygrehov]

Thanks, man!

[@shaurya478]

It is the best it can gets. Thanks Andrey.

[@sgtduckduck]

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.

[@kshitijb9416]

Nice transition to grids man! You've made it real easy to grasp. Thanks!

[@sammyj29]

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!

[@damaroro]

dude where are u now ? we need more video like this, this the best DP problem explanation in KZbin

[@andreygrehov]

Hey Damar. Thank you. I wish I could go back to KZbin. Extremely busy at work at AWS :(

[@JPN-bx3yd]

I was able to solve the coin change and knapsack problem by watching this course. Great content. Keep it up!

[@Ub3rmike]

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)!

[@Empilor]

Thanks Andrey, great explanation, useful course :) it’s hard to find such content

[@abhinavpandey6261]

Great tutorials so far , binged watched in one day :P

[@eh3276]

This is the best tutorial i have seen until now thank you .

[@dailyviralpodcastss]

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!

[@josecorral9645]

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.

[@andreygrehov]

Thanks for watching, Jose

[@shensean1784]

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.

[@andreygrehov]

Thank you, Shen!

[@user-zy3jg8ox7s]

This series is super valuable! Thank you so much for making these videos Andrey!!!

[@shubhampathak1080]

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 !

[@abdujabbormirxoliqov9676]

Cool! your videos really help to understand dynamic programming more deeply!

[@munkhbayar3940]

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!.

[@hannnah689]

So lucky find this video, super useful!

[@andreygrehov]

Thank you, Hanna.

[@張宗旻]

such a great introduction !!!!

[@sairamaj]

Thank you very much. Very nice and thanks for your time. really appreciate it.

[@NiranjanChandarraj1990]

Thanks for the awesome content, Andrey! Can we discuss some problems with top down approach and see when we would actually use it?

[@andreygrehov]

Thank you, Niranjan. Great idea. I'll make a separate video in which we'll go over the top-down approach.

[@ashokkumarkrishnamsetty6533]

Thanks for this. This is amazing, your framework just works

[@shivamtyagi9936]

This is my 3rd playlist , m watching on DP ....& yes u r better than the best!!! Tnks sir!! U r an inspiration!!

[@andreygrehov]

Shivam, thank you for kind words.

[@goshapoopkin]

Everybody: DP is so hard to explain to begginers- Andrey Grehov: Hold my beer *proceeds to explain DP in the most simple way possible*

[@smitdavey4834]

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.

[@andreygrehov]

Thank you, Smit. Yeah, very good points. The top-down vs bottom-up is in the works. I'll release it soon.

[@abdulrahmankhalid4634]

Thanks for the content

[@ananthganiga425]

Great Videos. Fantastic. Thanks alot for your effort

[@vissper1]

Appreciate your work!

[@marcousosewelle5501]

Subscribed. Brilliant series! Your communication, delivery and content are on point. Well done. Keep up the amazing work :-)

[@BhargavSolankisolankibhargav]

Thank you for doing this. Well explained.

[@myrachoantonio8832]

This amazing thank you so much for the tutorials bi

[@jameskanyi7376]

Good news. DP well explained

[@ashvanijaiswal9207]

Hey Andrey, Thanks a lot. Your Dynamic Programming course is really really big hit. Can you please make a series on backtracking and recursion.

[@AkkumBakkum-m5h]

thank you sir so muchhhhh you are inspiration to me

[@竹千代-n4c]

Thanks for the series!

[@Enzoerb]

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

[@siljapoulose4688]

Great explanations !!!

[@fayezmaria8688]

Just amazing thanks

[@daham94]

Great Work!!!

[@nikhilthapa9300]

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.

[@andreygrehov]

Thanks, Nikhil. Yea, super busy at work. Don't really have time for KZbin :(

[@coreytodtaylor]

Hey Andrey, that a great playlist, I haven't seen anything better. I'd like to have payment subscription on your tutorials!

[@andreygrehov]

Hehe, I actually thought about that.

[@karimkhattaby]

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

[@andreygrehov]

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.

[@enmanuelcruzdejesus765]

nice work!!

[@sumodbadchhape9823]

Thank you. Great explanation! 👌

[@glensee7506]

I love it, thanks!

[@acidroot7126]

Wow! Thanks!!!

[@glennpavel4800]

thanks for share!

[@koh8614]

Really nice content!

[@RedionXhepa]

Nice video ! Thanks a lot

[@princem8779]

Thank you so much!!!

[@tmkalyan8157]

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?

[@andreygrehov]

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?

[@tmkalyan8157]

@@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!

[@rrrrandall]

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.

[@rrrrandall]

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.

[@arjunprashanth]

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

[@andreygrehov]

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!

[@vedaanish2015]

Thanks for your videos. your video makes to "Stop searching DP on the internet again".

[@ranjith1102]

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.

[@Yaya-fu2wk]

After watching your videos, I feel DP is no longer magic! Would you also consider making algorithms videos?

[@RajSingh-dl2lk]

thank you.

[@abhishekthakur7675]

​ @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?

[@kshitijsabale1857]

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 ...

[@jamesvick8066]

This series is so good it could become a tv show lol

[@andreygrehov]

Lol. Thanks, James! :)

[@theshreyansjain]

comment for the algo! great video

[@eittorres]

Awesome

[@yizhang7027]

Transition function is recurrence relation, right?

[@andreygrehov]

Yes.

[@martinjoseph1398]

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

[@andreygrehov]

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-

[@martinjoseph1398]

@@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

[@JamshadAhmad]

First view and like.

[@andreygrehov]

Haha, thank you, Jamshad!

[@II_xD_II]

isnt most profitable path greedy

[@starbloods0013]

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

[@starbloods0013]

the only thing i left out was a look up table so that the code won't keep solving problems it already solved

[@ahmadbodayr7203]

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 ❤