Interview Question for Software Engineer Intern at Google:

Jan 16, 2011

2.*1*n distinct ways to climb

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