Climbing Stairs - Dynamic Programming - Leetcode 70 - Python

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

[@NeetCode]

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

[@algorithmo134]

@NeetCode can you do binary tree cameras?

[@alexandermilligan8265]

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

[@praffulkumarsingh1346]

Using base condition, when at 5(n=5 problem), why there is 1 way to reach 5, as you already stand there, why Not Zero(0) ?? Can anyone tell ?

[@max3446]

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

[@warguy6474]

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

[@freshmarcent2741]

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

[@a4addel]

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

[@warguy6474]

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

[@wrestlingscience]

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

[@cloud-vietnam]

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

[@abaibekenov6107]

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]

Definitely. Leetcode should pay him

[@jst8922]

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 kzbin.info/www/bejne/i4bEfqWEhNuGp8k

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

​@@demonslayer4607by closing his eyes.

[@prathameshjadhav3041]

@@demonslayer4607decision tree ?

[@sanketkadlag]

can we connect?

[@floroz87]

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!

[@MrFrawsty]

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]

this is also Fibonacci

[@xynergy645]

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.

[@techmemes3266]

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]

I too have same question, it should be zero

[@muthuksubramanian4143]

Same question, Any leads ? Thanks

[@Deschuttes]

Agreed. That doesn't make sense.

[@Tuyenrc]

same question here, has anyone found out?

[@DeepSheth1]

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;

[@kleadfusha8338]

The most underrated channel on KZbin!!

[@CostaKazistov]

💯

[@dazai9015]

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

[@nitiketshinde1458]

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

[@jcoder8965]

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!

[@sankalp1391]

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

[@dsptchr]

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

[@classicwhispers391]

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

[@fairozahmed6888]

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

[@joycewambui824]

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

[@prafulparashar9849]

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)

[@f3nrir_]

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]

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

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

[@yizhang7027]

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

[@adityaparab797]

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.

[@festooned]

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

[@itsZybn]

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

[@GateSlasHendrix]

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

[@farmanguliyev]

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

[@alimbekmaksytov]

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

[@tomasoon]

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

[@nameno7032]

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

[@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 :)

[@aicancode5676]

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

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

[@ma-la]

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]

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

[@Alex-mf3vo]

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]

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]

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

[@toooes]

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

[@gopalchavan306]

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

[@mohammedfahadnyc1385]

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

[@srikika]

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

[@AseshShrestha]

Love this channel. Thanks for so many great videos

[@TanakaNdove]

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

[@andresnet1827]

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

[@siruxsolutions]

Honestly the best video about introduction to dynamic programming.

[@sucraloss]

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)

[@hemavarthini8112]

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

[@tiendatnguyen6758]

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

[@michaelfraley9442]

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

[@snowcycle7]

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

[@augusto2581]

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.

[@emmanuelcbenson]

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

[@akhma102]

Thank you, Neet. You make our lives easier!

[@samarthgodase1011]

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

[@saran703]

man, you just made it eazzzz. Great explanation btw

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

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

[@machoman8940]

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

[@licokr]

Wow, awesome. When I see how Neetcode solve a problem, I feel it is really important to figure out a way to solve a problem. First try, I used bruceforce, and I watched this video 30% and I solved a problem using DP but still used recursive calls, I finished watching the explanation and it was A-ha moment and I solved the problem using an array, and I thought I did it well then I saw the code he doesn't even need an array. Awesome.....awesome...

[@debbiechang1831]

Thanks for the super clear explanation!!

[@vaibhavchawla7353]

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

[@CFATrainer]

Neetcode will go down as a legend in programming circles.

[@zifanhe8753]

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

[@jarjarbinks8954]

THAT IS ONE FANTASTIC SOLUTION. THANKS FOR THIS

[@-seoulair]

Incredible incredible explaining. I really understood everything you said.

[@chatbot2.0]

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

[@suryaprakashm1886]

Such an amazing walkthrough dude !

[@lch99310]

I cannot express how clever you are. Genius.

[@dipankarpurecha5564]

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

[@lphillis1]

Hey Neetcode, I want to know what software you are using to draw up your visuals. Can you share that? I think I would find it helpful to have a nice "whiteboard" for solving problems. Thanks.

[@anabildebnath2590]

One of the best explanations I have ever heard.

[@davidn7026]

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

[@quicksketch1617]

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

[@Ryan-xb1ry]

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

[@PrabowoMurti]

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

[@vedangsardessai1854]

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

[@er0s14]

Wow...🤯 Thank you for the amazing explanation and experience, feels like Im back in college. Now im going to sit down for an hour and process it all

[@vanitaladkat1491]

What an explanation, I am by default follower now ;) Thanks for such a great explanation.

[@jakedickson697]

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.

[@cpaulicka]

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

[@dineshchandgr]

Amazing explanation. super simple. thank u

[@AlexdeAbreu13]

Incredibly well explained. Thanks!

[@kasamadhu3509]

first time listening about dynamic programming completely understood.

[@daemperador123]

Thanks mate! You're the best!

[@andrewzakordonets]

What an awesome explanation. Thanks a lot!

[@vindhyahegde7574]

Thank You so much :) Amazing explanation!!

[@tabassumkhan7498]

To better visualise it, take a top down approach. For example, If it's 3, you have 2 decisions to make at every step to reach the bottom stair. Either you could take 1 step or 2 steps. So, the decision tree will look like this. The left edge represents 1 step and the right edge represents 2 steps. 3 / \ 2 1 / \ / \ 1 0 0 -1 / \ 0 -1 So, when you reach 0 return 1 and when you n < 0 return 0 Also, if you notice it is like the Fibonacci sequence 1 1 2 3 5 8 13.... And then the memoisation is easy t reduce the time complexity

[@2689742]

In short this one video was sufficient to subscribe this channel..Great work 🙏🏻

[@vyshnavijetti]

this is a very interesting solution . it makes lot of sense now how programming make life simple

[@kapildharao8321]

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

[@sunilshah300]

Thank you man, explained the solution very clearly.

[@rahulsbhatt]

Thank you so much for making this so easy!

[@s8x.]

Wow this was a great explanation. I love you ❤

[@tongyu211]

Great Video! Best Explanation! Thanks So much!

[@seza1231]

I love how intense the liner gets

[@andreasandres]

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

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

[@udubnate]

Great solution, thanks for the learning

[@Beelobong]

Great video - learnt so many concepts

[@LsEagle18]

My interest in programming after watching this video 📈📈 Amazing explanation. Loved it

[@arshdhanani8936]

HOW CAN ONE BE THIS GENIUS OMGGGGGG WONDERFUL APPROACH

[@benjem4911]

Nice solution and explanation as always! Would be cool if you could run your code in the end of the video as well.

[@BaktyiarTentimishov]

Thank you for your brilliant videos !

[@dishasuthar5508]

Sir Your Explanation is very Amazing.I Love DP bcz of this way of explaination.Thank You Sir.💕💕💕💕