Climbing Stairs - Dynamic Programming - Leetcode 70 - Python

Подписаться 764 тыс.

Просмотров 603 тыс.

50% 1

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
⭐ BLIND-75 SPREADSHEET: docs.google.com/spreadsheets/...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/climbing...
0:00 - Read the problem
3:55 - Brute Force
8:00 - Memoization
11:05 - Dynamic Programming
16:49 - Coding DP
leetcode 70
This question was identified as an amazon interview question from here: github.com/xizhengszhang/Leet...
#dynamic #programming #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

Наука

Опубликовано:

25 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 618

@NeetCode 3 года назад

🚀 neetcode.io/ - A better way to prepare for Coding Interviews

@algorithmo134 3 года назад

@NeetCode can you do binary tree cameras?

@alexandermilligan8265 2 года назад

Actually I think the brute force decision tree solution has a time complexity of Phi in the power of n, and not 2 in the power of n, seeing as it grows similarly to Fibonacci series. Great video by the way!

@monstereugene Год назад

why have a temp variable when you could write: two = one one = one + two ? Edit: Oh it's because it would change the one plus two line duh

@NitrakGaming Год назад

Instead of using a temp-variable you can make use of Python3s tuples (as you already are when you create the variables). one, two = 1,1 for i in range(n-1): one, two = one + two, one return one Behind the scenes it is effectively the same as using a temp variable, but without the ugliness of one! :)

@max3446 2 года назад

this is probably the hardest 'easy' tag question I've come across

@warguy6474 11 месяцев назад

if I didnt recognize the fibbonacci i would have been screwed lol

@freshmarcent2741 10 месяцев назад

literally, every single solution I saw besides fibbonacci I just do not understand lol@@warguy6474

@a4addel 7 месяцев назад

@@warguy6474i didn't know the fibbonacci before this video

@warguy6474 7 месяцев назад

@@a4addel I think if you take an intro computer science course in highschool or college they usually address it once but that's pretty much it

@mohd.tabishkhan4868 Месяц назад

Wait until you checkout 1002 : Find Common Characters

@cloud-vietnam 2 года назад

your videos should be in Leetcode's editorial solutions. Clear, concise, and so easy to understand.

@abaibekenov6107 2 года назад

This! Please! Once I've gone through several channels to understand dynamic programming and haven't done it ever since I found your channel. There's simply no need anymore, as not a single channel imo can beat @NeetCode 's way of explaining things! This guy is just phenomenal!

@jjayguy23 Год назад

He's a genius! His videos are such a blessing!

@kirillzlobin7135 9 месяцев назад

Definitely. Leetcode should pay him

@jst8922 6 месяцев назад

This guy is too very good in explanations www.youtube.com/@nikoo28 , only difference is he doesn't use python but Java instead. for current problem ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-UUaMrNOvSqg.html

@wrestlingscience 2 года назад

17:40 " ah Yes.. makes sense so far" 17:50 "WAIT ITS OVER?!"

@CSBAjay Год назад

Thank u very much!!! Because of your tutorials, I got interest and thinking visually for solving DSA problems.. Now I have a job in MNC too..

@demonslayer4607 Год назад

how do u visualise dsa ??

@shawcking2472 11 месяцев назад

@@demonslayer4607by closing his eyes.

@prathameshjadhav3041 10 месяцев назад

@@demonslayer4607decision tree ?

@sanketkadlag 5 часов назад

can we connect?

@techmemes3266 2 года назад

12:08 Why is the value for the base case 1? I would have thought it's 0 because if we start at 5, we only have the choice to take 1 step or 2 steps, both of which would lead to out of bounds

@vigneshv5092 2 года назад

I too have same question, it should be zero

@muthuksubramanian4143 2 года назад

Same question, Any leads ? Thanks

@Deschuttes 2 года назад

Agreed. That doesn't make sense.

@Tuyenrc 2 года назад

same question here, has anyone found out?

@DeepSheth1 2 года назад

It should be zero. This problem has 3 bases cases. 1) dp[n-1] ➜ 0 steps 2) dp[n-2] ➜ 1 step 3) dp[n-3] ➜ 2 steps Now, we can determine the remaining sub-problems. The drawn out approach is explained bottom-up, but the coded solution isn't bottom-up. Here's my bottom-up solution in javascript let currentStep = 0; let previousStep = 1; let totalSteps; // start at the end and move to index 0 for (let i = n-1; i >= 0; i--) { totalSteps = currentStep + previousStep; currentStep = previousStep; previousStep = totalSteps; } return totalSteps;

@MrFrawsty 2 года назад

Bro I don't know how you're so good at simplifying things, but it's incredible. I've watched so many videos on dynamic programming and not one of them has made as much sense as this. I sincerely thank you for all of these videos.

@marcialabrahantes3369 4 месяца назад

this is also Fibonacci

@kleadfusha8338 3 года назад

The most underrated channel on RU-vid!!

@CostaKazistov 2 года назад

💯

@floroz87 2 года назад

I am preparing for an interview and your videos are simply the best thing I found on the internet. Thank you for your hard work it's helping hundreds of us!

@xynergy645 2 года назад

OMG, thank you so much for the clear explanation. I've been struggling to understand the recursion method and why the complexity of Memoization is O(n) for a while. Your decision tree explanation is fantastic and I can finally have a good sleep tonight.

@nitiketshinde1458 2 года назад

Your explanations are really helpful! and efficient I don't know why this channel or video is very less subscribers/views , most underrated. YOU DESERVE BETTER ! keep it up

@dazai9015 2 года назад

Your explanations are so good, I'm so grateful that I get to watch your videos.

@jcoder8965 2 года назад

Beautifully explained. You really took the time to first establish what the problem was asking. I really appreciate you breaking down this problem conceptually and then proceeding to highlight how and why dynamic programming was the way to approach this problem through the use of DFS, recursion and memoization. Instead of just providing the 5 line solution after a few minutes of going through this problem, you took the time to provide an in-depth explanation and help cement the PROCESS of arriving at solution in my mind. So glad I subscribed to your channel and thank you very much!

@classicwhispers391 2 года назад

Thank you so much for taking the time to explain this. It makes a lot more sense now.

@GateSlasHendrix 2 года назад

instead of storing a temp variable, you can do this in python3+: one, two = one + two, one

@farmanguliyev 2 года назад

it also uses temp value in the background.

@AusTxMale Год назад

Or use: "one = one + two" and then "two = one - two" to do the same thing without an implicit temp variable.

@gerhitchman Месяц назад

@@farmanguliyev yes, but the code is cleaner

@f3nrir_ 2 года назад

if you consider the base cases of dp[n] = 0, dp[n-1] = 1, dp[n-2] = 2, you can complete the rest using Neet's solution and in that case there is no confusion regarding why dp[n] = 1.

@TaiChiSWAG Год назад

I was having the same doubt, Thanks

@darioarielgonzalezleegstra1741 Год назад

this makes much more sense. I still don't get why do we say there is "1" step from dp[n] if we are already in the last step and there are no steps to do.

@sapientia230 11 месяцев назад

@@darioarielgonzalezleegstra1741 because your current position is also the target position (top position) and there is only one way to go there by doing absolutely nothing

@PrafulPrasad 3 месяца назад

@@sapientia230 but then it means 0 ways, because it doesn't make any sense you have 1 way to reach 5 from 4 but you also have 1 way to reach5 from 5

@dsptchr Год назад

Literally the only person that actually explains this solution fully. It's unbelievable how badly others explain even the task.

@sankalp1391 2 года назад

Great Explanation! For others like me, who feel that the number of steps at the 'nth' step (last step) should be 0, the below solution is adapted accordingly: # computing the base case, when we are on the penultimate (n-1) step, or the one before the penultimate (n-2) step penultimate_step, one_before_penultimate = 1, 2 if n == 1: return penultimate_step if n == 2: return one_before_penultimate for i in range(n-2): one_before_penultimate, penultimate_step = penultimate_step + one_before_penultimate, one_before_penultimate return one_before_penultimate

@yizhang7027 Год назад

I love that you always start with a brute force solution, making the dp solution really natual in contrast.

@joycewambui824 2 года назад

You have a talent of explaining hard concepts easily. Thank you.

@itsZybn 2 года назад

The decision tree makes it so clear. Absolutely brilliant my friend!

@fairozahmed6888 2 года назад

I have watched it from many other RU-vidrs, no one even comes near you... Crisp and clear... Very good explanation

@festooned 2 года назад

great explanation and so helpful for getting me more confident in DP problems!

@adityaparab797 2 года назад

Great Explanation seriously. They way you break down the problem and optimise it step by step is just great! Thank you so much for making these videos.

@nicholascamarena6983 Год назад

FYI there is a O(1) solution because there is a closed form expression for Fibonacci numbers. As in, there is an equation for Fn (the nth fibonacci number) that is only a function of n, instead of a function of Fn-1 and Fn-2

@spirosgalanopoulos2560 Год назад

Indeed, although I am not sure it is that easy to calculate the nth fibonacci number in constant time, because exponentiation takes O(logn). It is also worth mentioning that one would have to use the known matrix exponentiation algorithm for fibonacci numbers, to avoid precision problems that arise from exponentiation of irrational numbers. Either way, though, it is indeed true that this observation leads to a faster solution, nice.

@sb_dunk Год назад

@@spirosgalanopoulos2560 When you say exponentiation, do you mean calculation of √5 and of the golden ratio constants?

@spirosgalanopoulos2560 Год назад

@@sb_dunk I was referring to ((1+sqrt(5))/2)^n.

@sb_dunk Год назад

@@spirosgalanopoulos2560 Oh yes, of course!

@mensaswede4028 Год назад

Yes exactly. In fact the original problem as stated, before any analysis is done, smacks of a problem that probably has a closed solution.

@nameno7032 10 месяцев назад

Been learning DP since for ever, only watch your videos can make me wrap my head around, big thanks

@tomasoon 2 года назад

to me, this is literally mind blowing, your explanation is perfect. thank you

@prafulparashar9849 2 года назад

Great video as always !! here is the recursion based DP approach in Python if anyone requires. class Solution: def climbStairs(self, n: int) -> int: # dfs appraoch def helper(n, index, memo={}): # base case if index > n: return 0 if index == n: memo[index] = 1 return 1 if index in memo: return memo[index] # recursion case memo[index] = (helper(n, index+1, memo) + helper(n, index+2, memo)) return memo[index] return helper(n, 0)

@alimbekmaksytov 3 года назад

'just five lines' of but neat code. I appreciate your tutorials for easy-to-understand explanations

@davidn7026 2 года назад

you explain like I'm a dumbass and this is why I like it

@TanakaNdove 2 месяца назад

two years later, we are still learning! Brilliant. Thank you!

@srikika 2 года назад

this was so clean! love it! thanks for making the vid.

@AseshShrestha 2 года назад

Love this channel. Thanks for so many great videos

@gopalchavan306 2 года назад

wow this is pretty awesome, really liked the way you break the problem

@ma-la 2 года назад

Thank you! Great explanation. A slightly more compact code: one, two = 1, 1 for i in range(n-1): one, two = one + two, one return one

@mayankbhola7325 2 года назад

you don't even need "i" you can replace it with "_"

@Alex-mf3vo 9 месяцев назад

your example of the loop works and gives 8 with n=5, thanks! But I don't get why code in video for i in range(n-1): temp = one one = 1 + two two = temp with n=5 gives result 3 and not 8? As for me it should be the same 🤔

@TheExcellentVideoChannel 2 года назад

12:20 Regarding base case, how many ways to get from 5 to 5 being equal to 1. Shouldn't it be zero? If you take either 1 or 2 steps from 5 you go beyond 5. Addendum: Have just done a bit of research on graph theory and apparently if self-loops are allowed then any node is allowed to be self-referencing and therefore to go from X to X is 1. If they're not allowed then X to X is 0. How do we know whether self-loops should or shouldn't be used in this specific case?

@richardfeynman707 2 года назад

Ya u could assume that as zero since it doesn't matter _5___ _4__| __3_| __2_| __1_| | | 5 3 2 1 NULL 8 At 3 and 4 u have first assign values as 2 and 1 From 3 we have 2 ways From 4 we have 1 way And from others we can follow the above method

@asifkamal166 Год назад

Thanks ... It was helpful

@asifkamal166 Год назад

@@richardfeynman707 Thanks ... It was helpful

@miguelescalantemilke7204 Год назад

Nice way to look at problems. I started using some kind of combinatorics and modular arithmetic, and I was like "why is this a Fibonacci sequence?" And then I thought that it kinda made sense as the case n+1 was something like the solution for n plus the solutions to go from the n step to n+1 (sort of, I took a little time to better catch the pattern). But looking at it as a top to bottom problem made waaaay easier. And I'm not really used to the notions of storing results and looking at solutions as an algorithm instead of an equation really help me ace my future interviews. Thanks for the video. You just earned a subscriber :)

@siruxsolutions 2 года назад

Honestly the best video about introduction to dynamic programming.

@mohammedfahadnyc1385 2 года назад

Oh my god. You are a Gem. So clear and concise. Thank you neetcode.

@tiendatnguyen6758 Год назад

This is crazy simple, man. Just love it 100%

@aicancode5676 2 года назад

For anyone who is confused why the base value is 1. I think we can try to understand better with this code, as we know that dp[2] = 2 and dp[3] = 3, we can just work our way up there. Hope this helps. class Solution(object): def climbStairs(self, n): """ :type n: int :rtype: int """ if n

@michaelfraley9442 3 года назад

Awesome videos man, Im watching the playlist rn, when do you think you will get to the last 6 problems on the 75 blind?

@hemavarthini8112 Год назад

The best ever explanation one could ever give. Thanks a lot!

@snowcycle7 Год назад

Dude you’re a beast, you’ve been helping me so much thank you 🙏

@emmanuelcbenson Год назад

Where have you been all my life? Thank you and thank you again. Words have failed. Thank you.

@toooes 2 года назад

> always start with a brute-force recursive solution- the best way to start solving any DP problem, *then* apply memoization/tabulation techniques

@andresnet1827 2 месяца назад

Both, the way you explain and the animations you provide, are truly awesome!

@samarthgodase1011 2 года назад

Amazing! Pls keep going your videos helps a lot Thanks :)

@saran703 3 года назад

man, you just made it eazzzz. Great explanation btw

@debbiechang1831 2 года назад

Thanks for the super clear explanation!!

@akhma102 Год назад

Thank you, Neet. You make our lives easier!

@suryaprakashm1886 2 года назад

Such an amazing walkthrough dude !

@seza1231 Год назад

I love how intense the liner gets

@-seoulair Год назад

Incredible incredible explaining. I really understood everything you said.

@daemperador123 2 года назад

Thanks mate! You're the best!

@vedangsardessai1854 2 года назад

Great explanation...Finally understood this problem...Thank you!!

@vindhyahegde7574 2 года назад

Thank You so much :) Amazing explanation!!

@zifanhe8753 2 года назад

best ever ! i saw at least five explanation and this is the best one!

@andrewzakordonets Год назад

What an awesome explanation. Thanks a lot!

@jarjarbinks8954 2 года назад

THAT IS ONE FANTASTIC SOLUTION. THANKS FOR THIS

@vladyslavkotov7570 Год назад

jesus, that array in the end was really the top anime plot twist of all time. fantastic explanation, my man, that's a sub right there

@amanrai5285 2 года назад

I'm getting OCD when I see you solved this without calling the orignal function back!.. Great work. Thank You.

@tongyu211 2 года назад

Great Video! Best Explanation! Thanks So much!

@vaibhavchawla7353 2 года назад

Your channel is a gem. Also, thanks for sharing the link to sheet. Now, i know how to make good notes. 😅😅

@AlexdeAbreu13 Год назад

Incredibly well explained. Thanks!

@dineshchandgr 2 года назад

Amazing explanation. super simple. thank u

@udubnate 2 года назад

Great solution, thanks for the learning

@machoman8940 2 года назад

Thanks neetcode! I'm a better person now because of your videos!

@andreasandres 2 года назад

Dude, i love that punch line in final 10 secs on this videos !!!!

@lch99310 2 года назад

I cannot express how clever you are. Genius.

@rahulsbhatt Год назад

Thank you so much for making this so easy!

@CFATrainer 8 месяцев назад

Neetcode will go down as a legend in programming circles.

@BaktyiarTentimishov Год назад

Thank you for your brilliant videos !

@augusto2581 2 месяца назад

Ok, hats off to you. The problem can be 'easy', but with your explanation of Memoization and bottom-up approach, you make this a 'must understand' problem. Thank you very much for all your efforts to explain it to us.

@PrabowoMurti 2 года назад

Great explanation. What software do you use to make the handwriting and draw (just like the whiteboard used in Khan Academy)? Thank you!

@dipankarpurecha5564 2 года назад

This video was so helpful, I was feeling kind of stupid not being able to realize why the fibonacci works. Thank you!

@Ryan-xb1ry Год назад

Thank you so much. This is the best solution I ever saw.

@anabildebnath2590 Месяц назад

One of the best explanations I have ever heard.

@chatbot2.0 2 года назад

A much better and clearer explanation of DP than my algorithm course…

@free-palestine000 2 года назад

wow, ive struggled with dp for a while and this cleared up a lot. i really like how you covered brute force

@Beelobong Год назад

Great video - learnt so many concepts

@Eda-gm7oy 2 года назад

Thank you, great video!

@sucraloss 2 месяца назад

Great video! I still will need to rewatch this a few times I think, but eventually this will make sense. I get the memoization solution at least. For anyone looking for the memoization code, I copied this from the solution section but this will save you a few clicks: class Solution: def climbStairs(self, n: int) -> int: memo = {} memo[1] = 1 memo[2] = 2 def climb(n): if n in memo: return memo[n] else: memo[n] = climb(n-1) + climb(n-2) return memo[n] return climb(n)

@gokulnaathbaskar9808 Год назад

Beautiful explanation, thank you so much

@sunilshah300 Год назад

Thank you man, explained the solution very clearly.

@victoriatfarrell 9 месяцев назад

That was a great explanation!

@karthik829 3 года назад

Amazing explanation!!

@eleias.singer 2 года назад

Thank you very much, man!!

@sinbad2597 Год назад

Amazing! Started doing leetcode easy problems but got stuck at this one . This is just beautiful. Amazing explanation. Am falling in love with analysing the problem . I didn't know about the decision tree thing . Any idea where I can learn similar concepts/methods that can help me or should I just try my best to think up such stuff myself? Am so lost

@algorithmnueng4349 Год назад

thank you so much :) you explain clearly.

@galactic_4k 2 года назад

Thank you so much, very helpful!

@quicksketch1617 5 месяцев назад

Thank you, I watched another vídeos about the problem and it's the first explanation I saw about decision tree. Made me think different

@cpaulicka 2 года назад

Thanks for the videos. Just wanted to remind you that you don't need temp variables if you do tuple assignment (ie one, two = one + two, one)

@smt210samsung2 Год назад

I wait for this in video, bcause its very pythonic way

@mytj228 Год назад

Wow! Really nice explanation. Thanks!! Subscribed 😀

@kapildharao8321 3 года назад

Very nice explanation, I understood the whole concept of Dynamic Programming in one video. Thank you!

@jakedickson697 2 года назад

The beauty of this solution is that the question being asked is how many different routes, not what are ALL the different routes, hence the optimisation shown here. Fantastic work.