• #### 科普

SCIENCE

#### 英语

ENGLISH

#### 科技

TECHNOLOGY

MOVIE

FOOD

#### 励志

INSPIRATIONS

#### 社会

SOCIETY

TRAVEL

#### 动物

ANIMALS

KIDS

#### 卡通

CARTOON

#### 计算机

COMPUTER

#### 心理

PSYCHOLOGY

#### 教育

EDUCATION

#### 手工

HANDCRAFTS

#### 趣闻

MYSTERIES

CAREER

GEEKS

#### 时尚

FASHION

• 精品课
• 公开课
• 欢迎下载我们在各应用市场备受好评的APP

点击下载Android最新版本

点击下载iOS最新版本 扫码下载译学馆APP

#### 编程面试题3:多少台阶组合可以上到第x级台阶

IQ 3: How many step combinations to get up x number of steps?

[音乐]
[Music]

Hi, guys how are you? I have the another coding interview problem that I want to share with you guys.

Here is the problem.

You have a stair case with n steps.

Let’s just say you have a staircase and it has n number of steps here.

You may take 1 or 2steps at a time to climb the stairs.

So let’s just say you have three stairs.

In order to get up these staires you have to take either one or two steps to make your way to the top of staircase.

So the first way to make your way up these stairs are
1次1级 就是第1级 第2级 第3级
to take one step at a time which you go one two three.

One step one step one step, that’ll be one combination.

Another way of making your way up these stairs would be to take two steps first

and then one step to make your way to the top of these stairs.

And another way to your way up these stairs would be to take one step first and take two steps

In order to get to the top of these stairs which would ultimately result in three ways or three combinations

to making your way up this staircase.

Write a method to find the total number of combinations to climb the stair case.

So when I was looking at this I know I had to consider two things,

I had to take note of the base case and I had to create a formula that

that would calculate the total number of combinations to make my way up this staircase.

So the first thing I consider was the base case,

if n which is equivalent to the number of stairs is lesser than or equal to 2 then I want to return n

so this basically means that if there’s only one stair

there is only one way up that stair, which is one step.

You couldn’t take two steps, because simply just one step

if there are two steps there are two ways to reach the top stair case
1次1级 或1次2级
1 step at a time or 2 steps at a time.

Another thing I consider was the formula.

So the formula would be equal to so so basically when I’m creating the formula

I wanted the formula that would account for if n is greater than 2 if there are more than two steps.

And it turned out that in order to calculate the combination
n级台阶的组合数 我需要将之前登顶
of the total number of ways that you can get to the top of n steps.
n-1级和n-2级台阶的组合数相加
I had to take the sum of the previous two steps.

ln order to come up with the combination so this is the formula here
Steps(n-1)+Steps(n-2)
steps n minus 1 plus steps n minus 2

I have an example down here let’s just say n is equal to 3.

So what I want to do is just pass 3 until … into n here.
(3-1)+(3-2) 等于 2+1
So 3 minus 1 plus 3 minus 2 you get 2 plus 1

which will be equal to three ways up the stairs.

So to make this a little clearer let’s start coding.

So the first thing I wanted to do was to create a function

I want this function to return a number.

Now I’m going to name this function

calculatestepways. Basically, number of ways that you can reach the top of a staircase.

Another thing I want to do is actually add a parameter value here.

This parameter value is just going to take the number of steps that are passed in.

The first thing I want to do is handle this base case.

So the first thing I want to write is if n is less than or equal to 2

then I want to return n.

So basically what’s happening here is

if the number as I explained before in the presentation is less than or equal to 2 I want to return n

if n equal to 1 I want to return 1 because there is only one stair

if it is equal to 2 I want to return 2

Because you can make your way up the steps one way with just one step at a time or two steps at a time

now another thing I want to do is add this else clause down here

And this else clause is simply going to return the method

let’s go back here

It is going to return this formula that I’ve created here n minus 1 plus n minus 2.
calculatestepways(n-1)+ calculatestepways(n-2)
So calculatestepways n minus 1 plus calculatestepways n minus 2

and that’s pretty much it as far as the function goes.

The only thing I need to do now is go up to this main method and call this function

also want this value to be printed out to the console so I’m going to do a

And then I’m going to pass in 3 now as we know as I explained before

by passing in 3 I’m supposed to get 3 steps.

So I should have 3 printed out to the console here.

Then you save and let’s run the application here.

We get three exactly what we were expecting.

that it looks it looks similar to the Fibonacci formula that I created in one of my earlier tutorial.

So another thing we need to consider is the time complexity.

The time complexity of this function is exponential

exponential time complexity to raise to the end to raise to the end all right.

So during this interview they also asked me to create a function for a better performance.

So basically a way of doing that as I said before it’s pretty much similar to the Fibonacci sequence.

The only thing that really changes is this basically this this base case condition

instead of returning one which I have done in the Fibonacci formula.

I’m just returning n now.

So I’m going to create a new function

a non recursive function that calculates the number of ways you can make your way up these steps

So I’m going to start off with public static int calculatestepways

And I’m going to name this non recursive.

And this function is also going to take in a number yes n.

It’s pretty much and also the base case we are going to set it up the same way we set it up here.

So if n is less than or equal to 2, then I want to return n.

What I want to do now is create three variables
“int first = 1” “int second = 2” “int nth = 3”
int first equals one, int second equals two, int nth equals three.

After this well not three, actually this is actually going to be two, my bad.

So I then want to create myself a for loop
“for (int i = 3)”
for int I equals three.

The reason we are starting at three I explained this in previous tutorial.

But the reason I started at 3 is because I’ve already handled the case for 2 here.

Then I want to go i is lesser than or equal to n i plus plus.

Alright so first thing I want to do is write nth equals first plus second,
“first = second” “second = nth”
first equals second, second equals nth

simply at the end I just want to return nth.

And this this is it as you notice with this for loop down here.

Time complexity is O of n, which is a better time complexity than the exponential one that we have up here.

So what I’m going to do now is call this function.

And I’m passing in the same value here save it if I run it again I should get the same number three.

See exactly what we’re looking for.

So that’s pretty much it for solving this problem.

If you have any questions please leave them in the comments below.

Make sure to also subscribe and like the video

if you felt like you’ve learned something from this and until next time.

[B]倔强

B11101001