Amazon Coding Interview Question - Recursive Staircase Problem

Amazon coding interview question and answer - recursive staircase problem!
For daily coding problems like this one, I’d recommend this website called Daily Coding Problem. You can find it here: csdojo.io/daily
(That’s a referral link, and you can get a 10% discount through that link. Their free option and blog articles are good, too, though.)
Outline (check my comment for the clickable outline):
0:07: Problem description
1:14: A variation of the problem
2:15: Thinking about simple cases
4:18: Finding a pattern
5:24: Relabeling the steps
6:41: Revisiting the pattern with the new labels
7:53: The pattern we’ve found - recap.
8:11: The recursive relationship we’ve found
8:50: What about when N = 0?
9:40: Writing a naive recursive solution
10:39: Why this solution is not efficient
11:24: How to fix it with dynamic programming (bottom-up)
12:27: The bottom-up solution in code
13:34: How to make it more efficient in terms of space
14:19: Solution to the variation of the problem
14:49: The recursive relationship for this problem (the variation)
15:08: A naive, INCORRECT recursive solution to this problem
15:50: A naive, CORRECT recursive solution to this problem
16:17: A naive, correct recursive solution in code
17:11: A dynamic programming / bottom-up approach
19:17: How to get daily coding problems like this one (go to csdojo.io/daily)
Also, keep in touch on Facebook: / entercsdojo

[@CSDojo]

Below is an outline of this video with timestamps. Btw as I mentioned in the video, for daily coding problems, I’d recommend this website called Daily Coding Problem. It’s actually made by a friend of mine who I used to work with at Google. You can use this referral link to get a discount, but their free option and blog articles are great, too: csdojo.io/daily 0:07: Problem description 1:14: A variation of the problem 2:15: Thinking about simple cases 4:18: Finding a pattern 5:24: Relabeling the steps 6:41: Revisiting the pattern with the new labels 7:53: The pattern we’ve found - recap. 8:11: The recursive relationship we’ve found 8:50: What about when N = 0? 9:40: Writing a naive recursive solution 10:39: Why this solution is not efficient 11:24: How to fix it with dynamic programming (bottom-up) 12:27: The bottom-up solution in code 13:34: How to make it more efficient in terms of space 14:19: Solution to the variation of the problem 14:49: The recursive relationship for this problem (the variation) 15:08: A naive, INCORRECT recursive solution 15:50: A naive, CORRECT recursive solution 16:17: A naive, correct recursive solution in code 17:11: A dynamic programming / bottom-up approach 19:17: How to get daily coding problems like this one (go to csdojo.io/daily)

[@vaibhavaren3217]

very nice video,learnt new things :D Thankyou so much :D :)

[@vaynegod2273]

Once I saw the pattern i realized it was Fibonacci immediately, really cool to see other real world fibonacci patterns, thanks cs dojo! :D

[@mayankagarwal4545]

dailycodingproblem.com is just gonna send one problem-solution every morning. Which means around 30 questions /month or 366 questions/year for which they are asking a fee of around $8/month or $80/year (considering your 10% discount) which is around 5400 INR/year . How on earth does that even makes sense. Who is gonna pay that amount for just one question daily !!!!!

[@rahulpandey6478]

CS Dojo can i contact you

[@kevinjad4506]

CS Dojo will the interview questions b such easy?

[@codinginflow]

Me: Just take the elevator Amazon: You're hired

[@preddy09]

Yup, hired for the warehouse job

[@codinginflow]

EasilyFallsForClickbait 😂

[@architadesai7876]

What if there's cut off 😂

[@danyeun01]

EasilyFallsForClickbait im pretty sure all of the warehouse work in amazon is handled by robots

[@christianjamesguevarra6257]

@@preddy09 yep but then they whine about people not "thinking outside the box" lol

[@MrBartolomeo22]

It's funny that all those IT companies bombard the candidate with algorithmic questions during the interview, but in the actual job you just glue some libraries together and hope for the best

[@_VeritasVosLiberabit_]

With algorithmic questions they can evaluate how good is your logic and your programming logic (these are different). These things are the most important when you're building a software, if you don't have good logic and programming logic you could find a lot of obstacles when solving a problem (which means time lost = money lost), and if you get it solved your software could have a lot of bugs, couldn't run for all the cases, and its efficiency could be wicked (which means hardware badly used = more money lost), that's why it's important to improve your logic and your programming logic, the only way to do this is practicing. Finally, your logic and your programming logic are more important that your knowledge in using frameworks, libraries, etc... Even a child can learn how to use a framework or a library watching a KZbin tutorial or a Stack Overflow post.

[@MuffinMan0521]

+ Nicolas You have no fucking clue what you're talking about.

[@christianjamesguevarra6257]

@@_VeritasVosLiberabit_ moronic sheeple

[@_VeritasVosLiberabit_]

@MuffinMan0521 If I have not clue of what I'm talking about, then why do not you enlighten me? Get away with your comments without arguments.

[@thespicycabbage]

@@_VeritasVosLiberabit_ Your logic seems to be very high level. These so called special frameworks/libraries you mention can be very powerful tools that have a lot of capabilities that companies expect their employees to know as hired software developers/engineers. IE React

[@SeanIsCrispy]

*Amazon:* Write a function that solves this problem *Me:* Goes to Stack Overflow *Amazon:* You're hired

[@ankitmathur4u]

Is this really true? :)

[@adityapawar4937]

@@ankitmathur4u Nope. Companies like Amazon, Google, Microsoft want their candidates to think and figure out the logic of the problem by themselves.

[@technbyond8144]

I got the same exact question for my McGrow Hill interview. They gave me 10 min to solve. I got it in 2 hours :D

[@ytg6663]

Why

[@technbyond8144]

@@ytg6663 Because I didn't figure out that was a fibonacci sequence. Once you find out the pattern, it's easy to code.

[@ytg6663]

@@technbyond8144 so, are you placed now ?

[@technbyond8144]

@@ytg6663 Nope 👎

[@ytg6663]

@@technbyond8144 why, what now

[@uthoshantm]

I conducted several interviews from a technical point of view. What I care about is consistency, attention to details, responding to questions in an intelligent way, saying I do not know instead of playing around, previous projects even as an undergrad that shows that the candidate is passionate about the field, details on how he solved a problem in a clever way maybe after a bit of struggling. I hate bulshit, show-off and overconfidence or the other way around excessive timidity, no determination. I do not mind getting a fresh graduate willing to learn and being mentored as long as he sticks around after gaining experience and becoming productive.

[@hungvunguyen8929]

thank you for giving us some hope!

[@utari90]

i needed to hear this for various reson xD

[@jeyaramt9066]

How to apply for ur company?

[@AnythingBros]

Please do more coding interview Questions!! Your awesome btw

[@fleisch1992]

*you're

[@mohmreski46yh32]

Really, do you understand the optimal way in the last minute? Or u just said that bcos u don't understand

[@jeremiahtassinari1743]

"For God so loved the world, that he gave his only begotten Son, that whosoever believeth in him should not perish, but have everlasting life." John 3:16 Only Jesus Christ is the way to Heaven and be saved from hell. "But God commendeth his love toward us, in that, while we were yet sinners, Christ died for us." Romans 5:8 "Jesus saith unto him, I am the way, the truth, and the life: no man cometh unto the Father, but by me." John 14:6 Have you believed in your heart that Jesus Christ died on the cross for your sins, was buried, and rose from the grave? You must believe that Jesus is the one who paid for your sins and rose again to be saved from eternal damnation and instead go to heaven "That if thou shalt confess with thy mouth the Lord Jesus, and shalt believe in thine heart that God hath raised him from the dead, thou shalt be saved." Romans 10:9 "For there are three that bear record in heaven, the Father, the Word, and the Holy Ghost: and these three are one." 1 John 5:7

[@jeremiahtassinari1743]

@Karan do you know if you'll go to heaven when you die

[@VishalPatel_imvishal]

@@mohmreski46yh32 hahaha was thinking the same. Good point

[@martinszauer4414]

Thanks to your DP explanation something finally clicked in my head and I understand the "Making change with coins" problem as well! The two are practically identical

[@ninjanerdstudent6937]

This is also what they ask their delivery men at the interview to find out which step of porches they will drop off packages.

[@DarshanSenTheComposer]

Wow, I really like your approach. I didn't know that if an algorithm works backwards, it might become efficient! This blew my mind. Thanks for the post!😊👍👍👍

[@antonyvilson8973]

You taught me a lot CS dojo, I have always been grateful to you. Specially knapsack problem. Hats off

[@kylemacarthur9863]

Great video. You are amazing. I love the hard coding questions that hint at how they make sure they maintain the quality minds that are part of the real secret sauce driving their success and phenomenal growth! I cannot even imagine the difficulty level of their questions about some of the intricacies of tax avoidanceand wage to work ratios! Anyone seen these?

Most important part of this question is that it is giving a well known problem in different presentation and expecting you to figure it out. Remaining part is just coding.

[@Kyrelel]

Dynamic Programming or, as we used to call it back in the 80's ... Programming.

[@reggiefrank]

Actually this technique was originally named dynamic programming, and it's programming means tabular math instead of programming a computer.

[@netbotcl586]

Dynamic programming was invented by Bellman before the invention of the first electronics computer.

[@TheHighborn]

Oh boy did I fucking hate dynamic programming in a class. They explained it bad, and didn't really show useful cases when one would need it. Turns out, it's pretty good. PS: fuck that teacher in particular.

[@shaikzillani6106]

Man, you are so awesome in explaining things, hats off to your patience in creating this! You're better than paid services!

[@ianweber7671]

This was actually a very well done explanation, thank you. Had not seen the bottom up approaches before.

[@alirezabeitari2821]

Again, a perfect video. Thank you so much for making this helpful videos. Please make a video about "Largest Rectangular Area in a Histogram" problem! Thanks!

[@ujjvalkapoor6067]

For that question you can refer to geeksforgeeks article..

[@cbuster7]

I remember learning similar problems like this in my discrete math and algorithms class.

[@user-jo2eu3wu1g]

love this channel. Will spend my time reading these valuable tutorials

[@sarahb8147]

Dude, WHERE WERE YOU when I was trying to understand recursion in school? This is the most clear explanation ever. Thank you!

[@ljdelight]

Great video! Having the perfect solution isn't possible without knowing different ways to approach a problem, and even rephrasing the problem as you did takes a lot of skill so I give you props. You're a good teacher. But... I wanted to point out things that would cause difficulty if the interviewer is having a bad day and knows a lot about the algorithm asked. 1: Big-oh was skipped, for space and time, so this would be a tough sell. 2: The problem "count the number of ways to go up stairs" given the step types, which is identical to "ways to count change" given denominations, results in a "Wrong Answer" if the step denominations aren't feasible with the steps (example: stepping {3,5} at a time cannot solve a stair height of 4, but this is not considered). 3: Extended interviewer question because it's fun to wreck the solution: Now provide the steps taken for the solution with the minimum number of movements.

[@haval00]

Can we appreciate this guys , how amazing he is ♥️♥️♥️♥️

[@qwarlockz8017]

This is still one of the best explanations I have seen online.

[@anandt8362]

Best ever explanation for this problem.. Thanks .. Please do more such interview problems.. You are really getting into the depth of it..

[@antonyndungu5514]

You're certainly an industry leader and a genius well done!!

[@440s]

Ok, but it didnt print "hello world"

[@OrenjiMochi]

T Fierro lol

[@tenshix1649]

XDDDD best comment

[@navarivkapais1943]

Lol lol lol

[@khan2850]

Ha ha ha

[@nguyenhoanglong420]

:)

[@abeyjoseph6381]

I am a non programming guy.and I understood this!! You are awesomeee!!!!

[@shubhamgupta5141]

Thanks a lot for all the hard work you put in to make these videos. It's really helping me a lot.

[@hihey229]

We did this in semester one of CS, on "Fundamentals of programming". Amazon, here I come

[@RaitisGrandovskis]

you wold be surprised how many cs mayors have forgoten or never understood this. However, it doesn't mean they are unproductive at work.

[@jf3518]

I have never encountered those kind of interview questions in my career. Instead it is more common to give an interviewee a task as a homework, like a mini project, that he can solve at home. This should not take more than 2 to 4 hours of his time. This usually gives a better overview of different skills the interviewee has. E.g. which prog lang, techs and libs he preferred. are there tests written. is he using versioning tools. how is his build chain... the next interview is then usually based on evaluating the results of the assignment and why the interviewee made the choices, he did.

[@all88899]

ur channel like heaven for me ... i studting software engennering i u help me a lot for some challage with this problem like gymnastics ... God bless u from tunisia

[@ShanmugamChinnappaiyan]

Detail level of explanation and optimisation. Very easy to understand . Thanks a lot !

[@ricardofranco7419]

Labeling the steps the way you did makes the problems incredibly easy! My first approach was a combinatorics one: given N steps and a set of rules--the number of steps you can take at at time, how many different ways can you make the sum of N. The way you labeled the steps, I went ahead and made a tree and was able to derive a recursive formula (forgive me, I'm a mathematician), which I then implemented into quite simple code. Thank you for the practice problem! I have the coding test tomorrow!

[@ochism1]

The solution to the easier problem is just the Fbonacci sequence, and therefore be written num_ways(N){return floor(((1/sqrt(5))(1+sqrt(5))/2)^n))}

[@mond2440]

Alex Vitkov this way cost constant time. Also There’s another way to compute the fibonacci number without dealing with floating point in constant time.

[@mond2440]

@Alex Vitkov ah yeah, my bad. But sill the best case is log(n) time for computing the n-th fibonacci number because the question is a special case where there's only 2 ways to jump.

[@Tips4Tat]

Well I wrote a function to do this, but something seems off about these solutions. His solution at 13:26 does seem to account for just walking up 5 steps 1 by 1

[@rousseau327]

This thread is a pretty clear demonstration of theory vs. experience lmao

[@ashirog1622]

Can do with a bit dp+matrix

[@royplays9218]

Thank you for this video. I was stuck in a similar problem. This helped me!

[@Shubham_Singh_India]

Congratulations bro on completing 1 successful year on KZbin. Love from India :)

[@dibyankamahto6238]

Amazing teaching style and love the way you go through the thought process while writing them down so seamlessly. Thanks for creating this content.

[@Monotoss]

Thank you Dojo, unlike anybody else who just brags and doesn't know how to easily explain the problem, you are truly qualified to make a teaching video. Easy to understand, brilliant man. respect.

[@farazahmed7]

Keep solving problems like this. I learn a lot

[@vishalchauhan9832]

Thank you so much sir ! You are great !

[@ts4gv]

I did it in 8 lines of code and felt so proud of myself. The fibonacci sequence didn't cross my mind even after testing the first 20 values of N. Well I guess I've developed a unique way of calculating the fibonacci sequence.

[@raynanwuyep4102]

Its been 2 years but, Can you show me how you did it?

[@IlyaGazman]

If you notice that the first part of the question is just Fibonacci numbers then you can approximate the solution with a golden ration in O(1) or provide an exact answer by computing the multiplication of N matrices in O(log(N)), however the last method is a bit trickier as it's performance depends on your multiplication algorithm

[@grindlewald47392]

love the way you presented...im totally new to programming and i can easily understand this video...expecting more videos from you..

[@sibusisocnhlumayo8841]

you are too good. I'm new in your channel and I see I'll learn all principles of programming from you. keep posting. I want to be a good programmer.

[@hemantupadhyay1554]

Same question was asked to me and in exam, i was trying to remember permutation & combination formulas.

[@harshith3062]

which exam

[@hemantupadhyay1554]

@@harshith3062 one of the IT company written test

[@abduallahmustafa1029]

it is fiboonacii series?? brillient way to solve problem...

[@sanjarcode]

It is coincidentally fibonacci, i.e only in the case when allowed steps are 1 and 2. Because f(n) = 1*f(n-1) + 1*f(n-2) = f(n-1) + f(n-2) which happens to be fibonacci. For any other value(s). It is not fibonacci. e.g {1,3,5} steps allowed. f(n) = f(n-1) + f(n-3) + f(n-5). Yes this can be called custom(number of values and the values) fibonacci.

[@955565265]

@@sanjarcode I guess you're saying that if we're allowed to take k1, k2, .. kn steps, then the solution is f(n-k1) + f(n-k2) +.... + f(n-kn).. Why do you think that's true?

[@teamkilla4313]

The base case is different. fib(n) is 1 for fib(1) and fib(2), fib(0) is zero

[@Amirkolo]

literally the best explanation on the internet

[@zaidaldhahi8895]

What a fancy explanation! You made a difficult problem looks like a very easy problem. Thanks a lot

[@aashay1709]

I'm so happy I did it myself. I actually recognised that it is fibonacci series XD

[@pietart3596]

Hey Joseph! Awesome tutorial here! Isn't the variation problem Bottom Up Approach a space efficient way of the first bottom up approach without the X = {1,3,5} constraints?

[@kelvinlopez5445]

You are amazing man, Thanks for yours videos.

[@StevenChen-kg8wd]

great vid YK. keep the tutorials going

[@cepi24]

It is simply amazing how you can explain algorithm problem + recursion + dynamic programming + complexity to one wideo which 10 years old can understand. Please make more. Subscribed

[@qwarlockz8017]

Thanks for the great presentation. I watched this a while ago and was mystified. I did a lot of reading and watched again and it was very clear and a great presentation. Thanks. It would be great if you could put your code on github. I love watching the videos but I learn a lot by transcription. Doing that FROM a vid sort of sucks.

[@machavaramakhil6656]

@CS Dojo I think we can even break the inner "for" loop if the condition (i-j)>=0 fails so it reduces checking other values in X(In the last problem)

[@SameerSrinivas]

Best explanation. Great job! Thanks for the effort.

[@india1727]

My youtube search says " Horror Movies 2019 " but somehow I landed over here watching algorithms ... sigh.

[@tongwu8467]

They are the same thing.

[@zhkq]

I hope I'm not too late but don't watch vvitch or hereditary, they're overrated

[@starquake7061]

Have you ever made a video about Developing solving problem skills? If you haven't, could you make it? How to practice it, best books to read about it, best resources.

[@CSDojo]

Not yet. I'll put it in my list :)

[@ThePhoenix107]

@JuxChannel Wow That is some motivation. Of course you can learn problem solving. You can learn how to approach things and see key elements you have to look for. You can always improve on that and learn new tricks you can use for different problems.

[@NicolaiRathjen]

Read CLRS.

[@Rupi_Kat]

Yes please!!!

[@Rupi_Kat]

Nicolai Rathjen will look into it. Thanks,😃

[@mir_ask]

Thank you for the video and all efforts!

[@DrunkGeko]

This concept was the first thing our professor in the programming class thought us in computer science uni

[@arkprince9413]

i felt lost after first 5 mins

[@mryup6100]

Same, I understood after watching the video three times. It takes time understanding these new concepts.

[@brondchux]

I'm still feeling lost, pls call 911

[@MuffinMan0521]

Amazon hires a guy to build a scalable rest based web api and he can't do it because they hired a guy that was really good at solving recursion algorithms which ended up only being used in 5% of his job. "Hey since you are a god at computer science theory surely you can pick up full stack development skills instantly".

[@emmanueloverrated]

Guys who can solve this without cheating and checking the solution before the interview, are usualy better. If I have to hire a guy who cannot solve this kind of problems and a guy who can solve, assuming I have the budget, I'll hire the guy who can do it.

[@PabloEdvardo]

What does the guy who solves it off the cuff look like when he can't and has to do research and learn something new? Being good at finding solutions and learning to implement them is a skill. I've met tons of people who don't "know how to Google". I'd take the person who is better at researching, learning, and adapting over the person who knows a solution offhand, because the limit to the one who can learn is endless.

[@dilutedexcitement]

Full stack development is a cake walk compared to advanced algorithm and CS theory. I've never met a person who understands advanced CS topics that can't pick up full stack in a few weeks but I've met plenty of so-called full stack developers that can't understand algorithms and write inefficient code because of it.

[@a-j.2002]

Well, it takes time, but these companies hire based on talent and are willing to develop people. Some companies ask applicants to know Haskell. Some of these companies don't even use Haskell, but they know it's a filter. If you know Haskell, you are more likely a better coder than those who don't. That doesn't mean you can't be good at coding if you don't know Haskell, just that the probability is inferior. The same way stronger people tend to be above a certain stature and weight, but it doesn't necessarily mean shorter/leaner people can't be stronger. Yes, it has some relation, but not an implication.

[@jeanmuyuela8112]

ughhh i hate people who do not even know basic data structure... waterfall of loops and ifs...... also they usually do not understand principles such as OOP or FunctionalP as well. they just shove code from stack overflow :P

[@CrazyzzzDudezzz]

I love coding and I love your videos

[@mryup6100]

Very nice explanation! It took me awhile to understand.

[@devithuotkeo]

Ahhh sooo smart!!! xD it's a fibonacci with a different way.

[@nahianalhasan5151]

Hi @CS Dojo, I really love your interactive videos! I've got a question regarding a similar problem. Say instead of stairs, we had coins. C is the amount of money we need, and V is a set of coins which have positive integer values, e.g. V = {1, 3, 5}. Using your solution (which I thought of as well when I first encountered this problem), we could effectively calculate the number of ways to reach C, i.e. the permutations. What would be the DP solution if we wanted the combination of coins instead? Would really love your input or anyone else's input on this. Thanks!

[@therishabhdhiman]

This is exactly what i thought that n should be the sum and we should compute that sum from the given numbers in n possible ways.

[@meliodas2804]

Luv u CS dojo

[@vijaysahani1515]

now i understands how dp works thanx cs dojo

[@pilpelbarkan]

The function num_ways_X_bottom_up is memory inefficient for very large n's. You could instead use a queue to store only the most recent values necessary (or an int array and shift it on every iteration): [1,3,5] means you only need a queue of 5 numbers, not n. And generalizing this, the queue size should be (Largest element) - (Smallest element) + 1 The concept is the same as what you showed in the first variation of the problem, when you stored only the last two numbers instead of the entire series.

[@TngMutantNinjaTroll]

Indeed. I did a variation of a shifting list from the get go, not really in an effort to save memory, it just seemed like an easier way to code step patterns I worked out on 'paper' beforehand. len() of the new list is the largest value integer in X list, values with indexes corresponding to steps in X are added up and appended to it, followed by a removal of the lowest value first element. Final result is simply the last element in that list after n iterations.

[@GurdeepSabarwal]

14:19:( Solution to the variation of the problem )

[@JackHeTech]

beautifully explained!

[@Shingorani]

the way he iterated through so many versions of the function and reached the last one was sick

[@jayanthsai400]

A small modification for above bottom-up approach which solves all the edge cases (in Python): def recursive_staircase(n, jumps): ways = [0] * (n + 1) ways[0] = 1 jumps.sort() # you can comment this line if the given jumps were in sorted order for i in range(1, n + 1): tot = 0 for j in jumps: if i - j >= 0: tot += ways[i - j] else: # By keeping break, we can deduce many iterations if once larger j has hit than i break ways[i] = tot return ways[n]

[@mayankgupta2543]

Before looking at the solution: Here is my solution: A tree where number of children a node can have is the number of possible steps a person can take A stack with total number of stairs n.

[@chris7056]

Beast

[@sameerali8293]

Genius!

[@AaronBrand]

Now explain to a novice!

[@leozilla]

very good description, thanks

[@sheshadrin7248]

You are doing tremendous job 👏

[@beatalert123]

That was actually pretty easy.. how do we figure this out in an interview ?

[@TheZiZaZo]

Hmmm looks oddly familiar to a recursive function I know.... Fibowhat? :]

[@ryannathaniel8060]

fibonacci prob.. #cmiiw

[@NamNguyen-rt7hn]

this is really easy to understand. Thank you

[@manojt4723]

Thanks for your valuable support

[@uberkarthik]

We can do this in prolog with a naive implementation that checks all possible permutations of 1 and 2 that add up to the total number of stairs, then returns the total number of those results. It is a lot simpler that way. Takes less time than this to solve.

[@habibullah-ki7ok]

uberkarthik Bro, i thought the same, you just need to know how many positive solutions has an equation type ax+by+cz=d (in case of N=3)

[@ABaumstumpf]

Coding that is a bit simpler - but SOLVING for a given number would take reeaaaallly long times once you increase the size of N.

[@danhorus]

I'm late to the party, but I'm proud of this solution: ideone.com/DYVO3g

[@sridharbelide]

Make videos of algorithms like sortings and searching algorithms

[@CSDojo]

Okay, I'll put this in my list.

[@tkdevlop]

sridhar belide check out mycodeschool for that sorting and searching

[@mastersabo7751]

thanks for the video, I had not found a comment in the comment section that states there is a bug in your code, for the X set of possible jumps (I confess I did not look through too many comments :)) The bug is that you assume that all steps are reachable to begin with and that is true if you assume that 1 is always part of the set X, but in the general case, where X can be any int array (not containing 1 for example) you need to skip those unreachable steps in the for loop, you can either do that with another reachable bool array (that you init only the first step with true) or init your nums array to -1 to all the values apart from nums[0] and in the for loop verify the value you are about to update is not negative.

[@ilanaizelman3993]

It's not for i from 2 upto n, but you have to include n . (for i = 0, i

[@Arkngthunchsturdumz]

You missed the most important part, that is proving that your hypothesis is correct (i.e. that f(n)=f(n-1)+f(n-2) is the solution to the problem). It's just not enough to try out a few sample cases and derive the solution from those, because there could be cases where the solution you think is correct actually is not.

[@MrHenryG123]

If the set of allowed steps is {1,2} then by definition, the number of ways to get to step n, or f(n), *must* be the sum of f(n-1) and f(n-2), since you can only transition to the f(n) state if you were previously at f(n-1) or f(n-2). This combined with the base case f(1) = 1 and f(2) = 2 will solve for any n from a bottom up DP approach.

[@prernasharma6308]

We can't thank you enough! 🙏 -your_indian_student

[@vishalchauhan9832]

Prerna Sharma you are from.which collage ?

[@prernasharma6308]

Vishal Chauhan MDU, Haryana

[@vishalchauhan9832]

Prerna Sharma ohhhk 😊!

[@prernasharma6308]

Vishal Chauhan and you?

[@vishalchauhan9832]

Prerna Sharma GNDEC Ludhiana,Punjab ..

[@karunesh26march]

you contents is better than most of paid online course ..Super duper like ....Thums up ..God bless you

[@tvpoppop]

thank you, it's very clever explaining.

[@dressr3270]

I can now recall why I didn't study this.

[@souradeeppaul6467]

Graph theory pliz...make video and trick problem..:)

[@deanroddey2881]

Another obvious optimization is that the list of legal ways is likely to be relatively small. So sort it first. Then, in the inner loop, once i-j < 0, you can break out and not do any more, since the rest are going to be invalid.

[@bedantabhaumik6888]

Hi csdojo. Very useful video

[@shubharora2172]

You can drop my package at 0 steps

[@workonline8831]

Awesome. I have a doubt at 3:50, case n=3. Does the case [0,3] possible??

[@JaySiggz]

He didn't explain the problem properly, you can only take at most 2 steps.

[@YourComicc]

yes he did not mention that you can take at most 2 steps at a time

[@8ballpoollivestream369]

he mentioned either you can take a single or a double (2 steps)

[@modusponens1094]

There's usually one more step, which is to work out the closed-form solution using the golden mean for the number of paths, making the dynamic program entirely unnecessary (for the Fibonacci sequence, it's on the Wikipedia page). Similar forms are possible for other linear recurrences. Hard to beat an O(1) solution. Math FTW.

[@HenrikRuep]

With fast exponentiation one can push the complexity further down to O(k^3log(n)) where k is maximum allowed stepsize and n is the number of stairs. Just note that [numways(n+k+1),...,numways(n)]=A[numways(n+k),...,numways(n-1)] for some matrix A. Thus the real goal is to compute A^n which can be done in logarithmic time with FastExpon.

[@kitko2652]

Seems some edge cases wasn't handled well, e.g. N = 4, X={3}, we should expect 0 way will be returned, but it returned 1 way from the above solution.

[@nndd8585]

Nope.. it does return 0.

[@justashushi]

7:47 my mind stop functioning after this

[@cheng6523]

Very good extended example 👍

[@BigHud83]

Great tutorial your explanation was easy to follow.