Climbing Stairs - Dynamic Programming - Leetcode 70 - Python

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

[@trh786fed]

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

[@warguy6474]

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

[@Huytn-12]

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

[@wrestlingscience]

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]

​@@demonslayer4607by closing his eyes.

[@prathameshjadhav3041]

@@demonslayer4607decision tree ?

[@sanketkadlag]

can we connect?

[@ehm-wg8pd]

@@demonslayer4607 i suppose, this entire channel visualizing DSA

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

💯

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

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

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

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

[@toooes]

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

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

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

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

[@dsptchr]

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

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

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

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

[@dazai9015]

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

[@TanakaNdove]

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

[@fairozahmed6888]

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

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

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

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

[@amanrai5285]

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

[@yizhang7027]

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

[@nameno7032]

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

[@alimbekmaksytov]

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

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

[@CFATrainer]

Neetcode will go down as a legend in programming circles.

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

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

[@andresnet1827]

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

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

[@nickolaskraus]

nit: you can use tuple packing and unpacking for simultaneous state updates. Example: def fibonacci(n): x, y = 0, 1 for i in range(n): print x x, y = y, x+y This removes the need for a temporary variable. Just a nit, thank you for all that you do.

[@NeetCode]

Good point!

[@mojo9Y7OsXKT]

solution for fast count given 'n', number of stairs in python. No DP needed: from math import comb n = 6; sum([comb(n-r, r) for r in range(n//2+1 if n%2 == 0 else (n-1)//2+1)])

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

[@itsZybn]

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

[@kasamadhu3509]

first time listening about dynamic programming completely understood.

[@jordiburgos]

This solution is very tied to the 1 and 2 steps. I would expect a more generic solution with different step sizes i.e. n=10, steps=1,2,5

[@emmanuelcbenson]

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

[@wery333]

Looking at it for me this was an extremely complicated way to describe Fibonacci sequence. Here how I think about it (it is pretty much the same, just a different perspective, might be easier for some people to understand it. Thinking backwards what is the last "move" we did. We either Jumped 1 step or we jumped two steps. This means that if f(n) is the function that calculates how many steps it takes to get to the n-th step f(n) = f(n-1) + f(n-2). Then if you continue the logic you can see how this is the same as your decision tree diagram: f(n) = f(n-1) + f(n-2) = (f(n-2) + f(n-3)) + f(n-2) and so on. We can easily recognize this is Fibonacci sequence, we can even see it with some examples: To get to 1 step (f(1)) you only have 1 way. 2 steps (f(2)) - 2 ways (2 or 1+1) Then to get to three f(3) we just sum the previous two f(3)= f(2)+f(1) = 2+1 = 3, f(4)=f(3)+f(2) = 3+2=5, f(5)=f(4)+f(3)=5+3=8 and so on. Then depending on how we want to solve it programmatically we can choose an approach.

[@MafiaXII]

I found it easier just looking at the three base cases and then deriving dp array/slice; one stair, two stair or three stairs. // 1 stair = 1 way // 2 stairs = 2 ways // 3 stairs = (take 1 step + sum of 2 stairs) + take 2 steps + sum of 1 stairs) // 3 stairs = (take 1 step + sum of 3-1 stairs) + take 2 steps + sum of 3-2 stairs // n stairs = (take 1 step + sum of n-1 stairs)+ take 2 steps + sum of n-2 stairs // n stairs = n-1 + n-2 //golang // o(n) space and time func climbStairs(n int) int { if n == 1 { return 1 } if n == 2 { return 2 } dp := make([]int, n) dp[0] = 1 dp[1] = 2 for i := 2; i < n; i++ { dp[i] = dp[i-1] + dp[i-2] } return two } From here, you can optimize space to be O(1) instead of O(n) by realizing that you only need two-three variables to store dp[i-1] and dp[i-2], and d[i] //O(1) space and O(n) time func climbStairs(n int) int { if n == 1 { return 1 } if n == 2 { return 2 } previousStairSum, currentStairSum:= 1, 2 for i := 2; i < n; i++ { previousStairSum, currentStairSum= currentStairSum, previousStairSum + currentStairSum } return currentStairSum }

[@namoan1216]

same as my idea, I think it is easier to come up with this solution

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

[@huleboermannhule44]

If you looked a bit closer at it you would see that the numbers you get are the fibonnaci numbers. There is a closed form way to calculate any, without calculating previous terms. That uses the golden ratio, and is relatively expensive for small numbers, but dominates for large numbers

[@justindion4394]

Coming from an industry that relies heavily on number series, this was my first intuition as well

[@lch99310]

I cannot express how clever you are. Genius.

[@DarkWolfes]

whilst storing the initial value of "one" totally works, setting two = one - two does not require the temporary variable.

[@justwanjiku]

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

[@classicwhispers391]

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

[@deville295]

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

[@prabinlamsal74]

When we are at stair 5 , we don't have 1 way to reach the goal, we are already at the goal. But we should put 1 as the value there anyways so that the problem gets solved. For eg: if we are at 3 , 3 ---> 4--->5 \ \ 5 Here, whenever we get to 5, we should vallidate the path that bought us there i.e. 1 . 3 to 5 is a valid path , so we give it 1. 4 to 5 is also one valid path , so we should vallidate that, so, putting 1 in place of 5 works. As, it is similar to having a single path from there to the goal.

[@vladislavsobolev5548]

Awesome solution, you doont need a temp var, use python power: one, two = 1, 1 for _ in range(n - 1): one, two = one + two, one

[@anabildebnath2590]

One of the best explanations I have ever heard.

[@perelium-x]

Here is the Top Down approach for anybody curious class Solution: def climbStairs(self, n: int) -> int: memo = {} def climb(m): if m in memo: return memo[m] if m == n: return 1 if m > n: return 0 memo[m] = climb(m+1) + climb(m+2) return memo[m] return climb(0)

[@moregspace8315]

class Solution: def climbStairs(self, n: int) -> int: if n

[@scpcomm1215]

I couldnt stop thinking who came up with this algorithm. You go from a long manner of counting by ones and twos, to creating a decision tree, to finding patterns and see how can you simplify the code, to ultimately realizing that counting backwards can simplify the counting, to ultimately recognizing the solution is simply the fibornacci series of numbers. TOo easy, becuase some genius paved the way... amazing

[@LsEagle18]

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

[@tomasoon]

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

[@seza1231]

I love how intense the liner gets

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

[@rajwanahmed935]

This is the best explanation I have seen. Thanks

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

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

[@chatbot2.0]

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

[@kapildharao8321]

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

[@ifatreefalse]

once you see the tree for n=5, you can just count how many 0's there are. how many 1's, etc. at this point you already have the answer is fib(n) and don't need to actually program anything.

[@madanielmadaniel]

First of all, thanks once again for comprehensive and well done explanation about this problem 🥇 ! Second, I had difficulties to comprehend the movement into the solution code it was just too fast for me. In addition I didn't understand why dp[n] == 1 and not 0 - since logically it's the target number, so we won't need to do more steps... As a suggestion, in case others will struggle like me, I think it's better to start with the recursive solution and to see how it's similar to Fibonacci solution. Then, trying to print solutions for n= 0, 1, 2, 3, 4, 5 and to see the pattern -> this explain why dp[n] == 1 - it's because we wrote the function to return 1 in case number == 0 and when we translate this to a loop, we want to init the first value into 1. Second value will also be 1 - run the recursive function (with debug prints) and see why. After you see the Fib pattern, all you need to do is to implement a fib loop to return the number as shown in the video.

[@amandaflood]

Thanks, that helped

[@vedaantrath2946]

Your Decision Tree explained memoisation succinctly. Thanks !!!

[@_ipsissimus_]

this one was hard for me because I could easily do UNIQUE combinations, but thats not what the question asked for. It counts 122 along with 212 and 221 (for 5 steps) as valid combinations, even though they arent unique.

[@bennbeckman7793]

I actually figured out a way to do it w/combinations. All you have to do is divide the number of steps you took, N, by the product of the factorial of each repeated number. So if you want to climb 7 steps, if you only take a 2-step once, it would look like 111112. Since 1 repeats 5 times and 2 only once, you get 6!/(5!*1!). Do this for the amount of times that you can take 2 out of 7 evenly and add them together. So 7/2 = 3.5 you would repeat that 3 times adding adding another two and removing the ones respectively.

[@LowLevelLemmy]

The ending was the biggest plot twist of my life. Thought it was going to be super complex. It's just 5 lines of cute code 🤣🤣🤣🤣

[@keyone415]

There is also a O( log n ) time O( 1 ) space solution to this using the Fibanocci Formula :) One line of Python: return int((((1+math.sqrt(5))/2)**(n+1)-((1-math.sqrt(5))/2)**(n+1))/math.sqrt(5)) It's log n because the power ** operation takes log n time.

[@PippyPappyPatterson]

epic

[@blank3525]

During Bottom up, why did you take "" n = 5 "" as "" 1 "" because shouldn't no.of ways to reach "" n = 5 "" from "" n = 5 "" be ""0"" ?

[@andreipoehlmann913]

@Mohammed Why is taking "no step" (= 0 steps) an option here given the constraints of the problem (i.e. taking 1 or 2 steps)? When we looked at the earlier visualizations how to reach "n", we stopped once we actually reached "n" by previously taking either 1 or 2 steps. We didn't get at stair "n" and then at "n" said: "Ok there's is one last option which basically is taking no step, so we also have to count this last option". During bottom-up at 4 we also say there is only 1 way to get to 5: take 1 step. We don't consider the case "take 0 steps followed by 1 step".

[@widmur]

@@andreipoehlmann913 I find it easier to reason about this way as well. - The number of ways to reach stair `n` starting from stair `n` is 0. - The number of ways to reach stair `n` starting from stair `n - 1` is 1. - The number of ways to reach stair `n` starting from stair `n - 2` is 2. And so forth. Granted, my code is icky compared to Neet's. Neet's code effectively _seeds_ the value of stair `n - 2`. ``` class Solution: def climbStairs(self, n: int) -> int: n_minus_one = 1 n_minus_two = 2 if n == 1: return n_minus_one if n == 2: return n_minus_two # i begins at n - 3 i_plus_one, i_plus_two = n_minus_two, n_minus_one i = i_plus_one + i_plus_two for _ in range(n - 4, -1, -1): i_plus_one, i_plus_two = i, i_plus_one i = i_plus_one + i_plus_two return i ```

[@kunalmandil3882]

def climbStairs(n): # if you are at n-2 a = 2 # if you are at n-1 b = 1 if n == 1: return 1 if n == 2: return 2 for _ in range(n-2): a, b = a+b, a return a

[@mytj228]

Also curious to know the answer…

[@amandaflood]

It looks like this covers the edge case of being on the last step. I agree it doesn't make sense. You could do it by covering the edge cases of n = 1 and n = 2 then starting with the nth-1 step. There's a comment below that shows this, by @sankalp.

[@-seoulair]

Incredible incredible explaining. I really understood everything you said.

[@hemavarthini8112]

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

[@dipeshjadhav1546]

Loved it man !! I am falling in love these problems .. I wish I had teacher like you!

[@Charles-tq9tc]

This problem has a better solution than O(n). You can conceptualize it as a fibonaccis suite of numbers (clearly visible at 15:27). the solution becomes: steps(n) = fib(n+1) and computing fib numbers is O(log(n)). cheers :)

[@tiendatnguyen6758]

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

[@vyshnavijetti]

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

[@arshdhanani8936]

HOW CAN ONE BE THIS GENIUS OMGGGGGG WONDERFUL APPROACH

[@festooned]

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

[@MichaelShingo]

such a good explanation of a fundamental problem

[@K4RD050]

Nothing easy about this 😅 except for the miraculous explanations of this channel as always! 🙏

[@chihchang1139]

a slight optimization for the swap without temp is to set two = one - two

[@darktemplar32489ify]

You do not need a temp for any language. just do: one = one + two two = one - two

[@spiffylogic]

You can use python tuple syntax to avoid the need for a temporary variable: one, two = one + two, one Also use _ instead of i.

[@dwaynefett6234]

Great video, but was just confused on one part: if you can only move either 1 or 2 steps, how is there 1 way to get to 5 from 5. 'Cause to get from 5 to 5, wouldn't you have to take 0 steps? And only 1 and 2 steps are options, right?

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

[@UsamaAziz-lb7ky]

This one was confusing, because explanation was for bottom-up approach, but you coded up top-down approach. this one would be solution for bottom-up def climbStairs(self, n: int) -> int: prevSteps, curSteps = 0, 1 for i in range(n, 0, -1): curCache = curSteps curSteps = curSteps + prevSteps prevSteps = curCache return curSteps

[@siruxsolutions]

Honestly the best video about introduction to dynamic programming.

[@FF-ct5dr]

You can get the solution by adding binomial coefficients. If x is the number of single steps and y the number of double steps, then: x = 5, y = 0 -> (5c0) x = 3, y = 1 -> (4c1) x = 1, y = 2 -> (3c2) and the sum is 1 + 4 + 3 = 8. The closed form solution is sum (n-j c j), j goes from 0 to int(n/2).

[@maku_chan3997]

Amazing. This is the best explanation I have seen for dynamic programming.

[@NeetCode]

Happy it's helpful 😊

[@chuckhancock4551]

Example 2 has two ways. 1 step + 1 step + 1 step or 1 step + 2 steps. The order doesn't mean anything thanks to the commutative property of addition.

[@namelesslamp12]

lol, i am currently completing the spreadsheet and I was surprised u didn't have a video of this problem so i google it and here it is. thanks bro really nice content

[@rakeshakkannagari7559]

Which spread sheet??

[@singletmat5172]

@@rakeshakkannagari7559 this one docs.google.com/spreadsheets/...

[@redeye1267]

This is basically just Fibonacci sequence lmao. nice tutorial nonetheless and you did a great job explaining how to use DP. Here's a solution: int climbStairs(int n) { long long prev =1; long long curr =0; for(long i = 0; i

[@edungdivinefavour6977]

Awesome videos. Been binge watching your channel. Thank you so much..... My only concern was i didn't understand how at staircase 5, there was 1 way to get to 5. When in reality we didn't need to make any move from 5.

[@_SoundByte_]

The question is, how many different ways can you reach the top from where you're standing? The answer is simply one - you're already there! You don't need to do anything or take any extra steps. But I understand it's confusing.

[@shawcking2472]

​@@_SoundByte_his doubt makes sense. There's one way to go from 4 to 5 and there's one way again to go from 5 to 5. How is this making sense. From the surface it is looking like the value 1 was assumed for the base step.

[@castorseasworth8423]

​@@shawcking2472 Agreed. This explanation doesn't suffice me either. For me it makes more sense for the base case to be staircase 3 and 4: How many steps from 3 to 5? 2 How many steps from 4 to 5? 1. Then: def climbStairs(self, n: int) -> int: if n

[@Ved3sten]

This is one of those questions where the solution is so simple when you look at it when you look at the recurrence, but then you're in disbelief so you try to enumerate all the combinations

[@the_dark_jumper2211]

I can't tell if I think this problem is frustrating or beautiful. My intuition was: "okay, it's a combinatorics math problem". Eventually arriving at "result = sum(k in range [0, n/2] | nCk(n - k, k))" ... that's when I printed the sequence to the console. I just spent the best part of an hour creating an optimized nCk function, just to rediscover the fibonacci sequence.

[@PippyPappyPatterson]

IMO, most ideas that nerds call "beautiful" are simply ideas that require a thinker to hold ≥5 concepts (i.e. more than our four working memory slots) concurrently to grok.

[@dishasuthar5508]

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

[@AlexdeAbreu13]

Incredibly well explained. Thanks!