It's a question that's being asked by Amazon, among other companies, and in this problem, you're given a staircase with and steps.

So if the given and is four, your staircase will have four steps, and that means that you can go from the bottom to the top in four steps.

So that's 123 on four steps and suppose that you can only take one or two steps at a time.

So if you start at the bottom, you can only go from the bottom to here or here.

And if you decide to go here, you can only go from here to here or to hear on.

The problem.

Here is writing a function called Nam Ways, which takes the positive integer n on returns, the number of ways you can go from the bottom to the top.

So if the given and is too instead of four, there's only two ways off going from the bottom to the top.

The first way would be taking one step at a time.

On the second way would be taking two steps from bottom to the top, so your function numb ways should return to if the given and is too.

And once you're done with this problem, think about this variation.

What if in addition to end your also given X, which is a set off positive integers and this is gonna be the set of numbers of steps you're allowed to take instead of just one or two steps.

So in this particular case, you can go from the bottom two over here by taking one step at a time, Or you can go from the bottom two over here by taking 123 steps.

But you're not allowed to take two steps year because two is not in the set.

You're not allowed to take five steps either here because we don't have enough steps for five steps.

So maybe pause the video right here.

If you want to practice on, try solve in the first problem, as well as this variation off the problem.

Okay, here's how I would think about it.

I'm gonna go a little bit slowly here, so I'm gonna put on outline of this video with some time stamps in the description, so you don't have to watch the whole thing if you don't want to.

Now, I would first think about some simple cases, for example, when and is two or one like we saw earlier.

When and is, too.

There are only two ways to get to the top from bottom.

The first way was taking one step at a time.

On the second way was taking two steps.

If you label each of those steps, you be able to write down each of those pats, so you might label the first step, the bottom zero, and then this Step one and then the top two.

Then you'll have these two.

Pat's going from 0 to 1 to two or going from 0 to 2 on.

I'm just gonna write down to here to show that we have to.

Pat's here or two ways off, going from the bottom to the top, and we can do the same thing for when and is equal to one on the on leeway here for us to go from bottom to the top.

It's just by taking one step or going from zero, let's say this step right here, 21 So that's this path right here, 0 to 1, and then I'm gonna write down here one as well to show that we have only one path.

And let's do the same thing for when an equals three.

First of all, let's label these stairs as they're a 12 on three.

The first path we can immediately find is this one there.

12 and then three.

Let me write it down here.

That's the one right here.

And then the next one might be a dear one.

And then three, that's the one right here.

And then we also have 02 two, 23 And that's the one right here.

So here we have three paths.

So that's why your function should return.

If you're given an ISS three and you can do the same thing for when N is equal to forest Wall, I'm just gonna skip over this just the same time.

But you'll find that they're five pats here.

Okay, so the question here is can you find any pattern for what we've found so far?

It's actually kind of Howard if you're not used to this kind of thing.

But I think the easiest way to find a good pattern here is by visually so let's go back to when and is equal to three.

In that case, you asked yourself, How can we go from step zero to step three?

And to answer that question, you need to ask yourself, Should I go over just one step or two steps from the bottom?

If he decided to take just one step from the bottom, then you needed to ask yourself, How can we go from step one to step three?

But if you look at Onley this part up here, that's actually just a staircase with two steps.

So when you ask yourself, how can we go from Step 12?

Step three?

That's actually a problem that we've already solved when N is equal to two, because in this case, two we asked ourselves, How can we go from step zero to step to or go over a staircase off two steps on?

And I think this pattern is gonna be more clear once we re label these steps.

So let's label these steps not from the bottom, but from the top instead.

So the top step is gonna be there, here and then this step is gonna be one, too, on this last step.

The bottom step is gonna be called three on Once we re label all the other steps as well, these steps is gonna look like this.

So with this relabeling the top step for when an easy go to one becomes there on the bottom step is gonna be one on the same thing for when and is equal to two.

And with that labeling scheme, these are the paths that we have.

So instead of 0141 and is he go to one, we have 10 because we go from one to there on.

We can do the same thing for when n is equal to three as well.

The first path we can find a 3210 and then the next one is 3 to 0 on.

So okay, now let's go back to what we did earlier.

Going back to, you know, when we were on the ground.

When N is equal to three, then you need to ask yourself, Should I take just one step or two steps?

Right?

And if you decide to take one step, then you have 32 as the first part off this path on from there.

Of course, you needed to ask yourself, How can we go from step to two?

Step there?

And that's exactly the same question that we've already answered when N is equal to two going from step to two steps there.

So if you examine the rest of the paths, you know this path to 10 on 20 They're exactly the same as the past we saw when N is equal to two and you can do a similar analysis if you decide to go from 3 to 1 us.

Well, in that case, we have three won us the first part of the path on from there.

You need to ask yourself, How can we go from step 1 to 0?

And that's exactly the same question, and this is kind of silly.

But if it's exactly the same as what we asked earlier when Anne is equal to one, and in that case the rest of the path is just one there on dhe.

That's of course, exactly the same as the path we had for when and is equal to one.

So basically what we found here is that for when an easy could 23 These 1st 2 pats is the same as the past we had for when an easy go to two and the last path is the same as the past we had for when and easy go to one.

And based on that, we can write that numb ways of three.

Or the number of ways of climbing over a staircase of Three steps is equal to numb ways of two plus numb ways off one.

And actually, in general, this should be numb ways Off N is equal to numb ways of n minus one plus nine ways off and minus two.

So you can check that, for example, for When N is equal to four numb ways of four, as you can see is five here, and that's numb Ways off three, which is three plus None Ways of two, which is two.

So two plus three, which is five.

Here, you might say, What about when and is equal to zero?

I would actually argue that in that case, numb ways of zero should be one, and here's how I think about it.

It's sort of like asking yourself how many ways are there to climb over a staircase off their steps.

Or how can we get firm Step there right here to step zero, which is also the top.

Well, let's say you're standing on step zero at the bottom and then, boom, you're at the top steps there, So this is kind of silly.

But the only way to get from step 02 steps ERA is just zero this path right here.

So we only have one.

And that's why numb ways of zero should be one anyway.

Let's now think about how we can use this recursive relationship to write some coat.

Okay, so this is the recursive relationship that we found earlier to find a recursive function.

With that, we need to find base cases.

One choice would be to choose one on two, but I would argue that the simpler choice is these 20 and one, and with that will have these big cases.

None ways off there on numb ways of one being equal to one.

Based on that, we can write our recursive function.

We're gonna call it numb ways.

Of course it's gonna take and a positive integer.

And then let's first take care of the base case.

That's one and is equal to zero or one.

Where is this gonna return?

One on, if that's not the case, or else we're gonna return the some off numb ways and minus one on numb ways and minus two.

Now, examining this function, you probably see that this is just like the Fibonacci sequence.

You might also see that this is not the most efficient way to find numb ways to see why.

Let's just quickly examine when and it's equal to four or when you call and W or four or numb ways.

Afford to find the return by the off and w for you need to first find the return marries for N W three on and W.

Of two, and to compute and w three or numb ways of three.

You need to first compute and w two and and w one and so on.

Andi, just looking at this tree, you see that N W two is repeated twice, and that's wasteful on.

It's wasteful because we need to repeat the same competition twice to find the Valley off and W of two on this problem gets worse and worse as and becomes larger and larger.

So let's see how we can fix that.

We can fix it with dynamic programming on.

One way to implement it would be with a bottom up approach.

So let me just quickly explain the idea here for the bottom up approach.

We're gonna use this table off and on numb ways of n on at the beginning.

We don't have the values for numb ways off end.

And let's say, as an example, we're trying to find the Valley off numb ways off.

Four.

So N is equal to Fort in that case, will first construct Honore off length five or length and plus one and then we'll know right away that the 1st 2 elements of the array should be one.

Because that's the base case that we have here on after that will find a value for each element by adding up the two previous elements.

So one plus one equals two and they want plus two ecos three and so on.

Once we find the value that we were looking for, which is five in this case, we'll just return it from our function on that approach is gonna look like this in code.

We're gonna call dysfunction numb ways bottom up and it's gonna take a positive injure end on.

First of all, we're gonna take care of the base cases when N is equal to zero or one, we're gonna return one on otherwise or if we haven't returned yet, we're going to initialize Honore an integral ray off length and plus one.

And then we're gonna assign it to a variable called Numbs The men.

We're gonna set the 1st 2 numbers off this array numb zero and numbs 1 to 1.

And after that, we're gonna run a four loop for eye from two That's two right here, up to end.

That's for example, fort.

And for each of those I numbs I or the current element that we're examining should be the some off the previous two elements numbs I'm minus one and numbs I'm minus two on after we find the last number of this array or numbs off n where just gonna return that now this function works just fine, but if you want to make it more efficient or if you want to save more space, there's a way to do that.

So when you're running this four loop when I is equal to, for example, three right here to find numb ways off three.

Right here.

You don't need all the elements in the array.

All you need is the two previous elements.

So basically, you only need to store only two elements at a time.

As you go through this four loop so you can store these tournaments and then these two elements on these two elements and so and that way you can save some space.

So anyway, this is my solution to the first problem.

Let's take a look at the variation I told you about.

As I explained earlier, in this violation of the problem you're given end as well as X, which is a scent off numbers of steps you can take at a time.

Let's solve this problem.

Be cursed, ugly as well on.

We're gonna base our recursive solution to this problem on the recursive solution that we saw earlier to the previous problem.

So we have the functional we saw earlier numb ways.

The only difference from what we saw earlier is the fact that we don't have on else statement on with the same kind of argument that I use earlier.

You should be able to find this recursive relationship.

Numb ways Off N is the some off some ways off and minus one on the Ways of animals.

Three.

On Numb Ways off and minus five.

If the given X is this 113 and five.

So based on this function and based on this recursive relationship, your intuition might say that your function Let's call it numb ways X should look like this again.

I'm assuming that X is 135 for now.

And this says the bass case went, and a sequel to zero we should return one on.

Otherwise we should return the some off numb ways off and minus one and my three on and minus five.