Name: 亞馬遜編碼面試題--遞歸樓梯問題。 (Amazon Coding Interview Question - Recursive Staircase Problem)
Uploaded: 2021-01-14T10:21:48.000Z
Duration: 20 min 1 s
Description: 【看影片學英語】數萬部 YouTube 影片，搭配英漢字典即點即查，輕鬆掌握單字發音與用法，長久累積看電影不必再看字幕。

everyone today I have according interview question on.

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.

情態助動詞 A2

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.

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.

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

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.

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

The first way was taking one step at a time.

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.

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.

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

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?

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?

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.

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.

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.

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.

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

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

字幕列表影片播放

亞馬遜編碼面試題--遞歸樓梯問題。 (Amazon Coding Interview Question - Recursive Staircase Problem)

approach

quote

pattern

positive