## Interview Question

## Interview Answer

8 Answers

Let c(i-1) = the total for a staircase with i-1 steps. Now add one step to the beginning. You have two choices: start with one step and then do c(i-1), or start with two steps and then do c(i-2). In other words, c(i) = c(i-1) + c(i-2). The basis for the recurrence is c(0) = c(1) = 1.

This is exactly the Fibonacci sequence. I submit that the solution to this problem of n steps is Fib(n+1). Let's verify for small values of n:

1 steps: There's only one way to take one step. (1)

2 steps: There are 2 ways (1+1) or (2)

3 steps: 3 ways (1+1+1), (1+2), (2+1)

4 steps: 5 ways (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (2+2)

No. of integral solutions to equation:

x+y = n

= n+2-1C2

int getways(int n)

{

int i,j;

int sumways=0;

for(i=0;i<=n-i;i++)

{

if(i==0)

sumways++;

else

{

int subways=1;

for(j=1;j<=i;j++)

subways*=((n-j)/j);

sumways+=subways;

}

}

}

If I may take the steps in 1 or 2 or any combination thereof =4 (remember, # of stairs are not factored). HOWEVER, this combination may have infinite combination the more stairs there are! You would still use the basic steps as the question has a base of two :

1+1

1+2

2+1

2+2

1+1+1+1+2+2+2+2. . . .

this is fibonacci

your first step can be either 1 or 2 step.

if first step is 1 step, remaining is an N-1 problem.

if first step is 2 steps, remaining is an N-2 problem.

N problem = N-1 problem + N-2 problem

This is a dynamic programming puzzle with the Fibonacci recurrence: s(i) = s(i-1) + s(i-2).

More details here: http://dailyjobquestions.com/2011/10/17/stairs/

Fibonacci....

## Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up

2.*1*n distinct ways to climb

Jan 25, 2011