Given n stairs, how many number of ways can you climb if u use either 1 or 2 at a time?

variant of question:-

A person can take m steps at a time to reach a particular floor( say in a building). How many different ways can a person reach the nth floor?

let's try to understand problem:




but we have to make some modification in Fibonacci sequence to get correct answer.
why?
In Fibonacci first element is 0 & second is 1
i.e for step no 0  we have 0 ways & for step no 1 we have 1 way
for step no 2=no of ways(0)+ no of ways(1)=0+1=1
but  answer is 2 which is no of ways(2)+ no of ways(1)=1+1=2
look at table

Here our first element is 1 not 0
therefore to find no of ways for step no n ,we have to find  no of ways for step no n+1

code:

#include <stdio.h> 
int Fibonacci(int);
main()
{
   int n;
   printf("total no of steps:");
   scanf("%d",&n);
   printf("no of ways to climb is %d\n", Fibonacci(n+1));
   return 0;
}
 
int Fibonacci(int n)
{
   if ( n == 0 )
      return 0;
   else if ( n == 1 )
      return 1;
   else
      return ( Fibonacci(n-1) + Fibonacci(n-2) );
} 

output:-

total no of steps:4
no of ways to climb is 5

but what if person can take m steps at a time ?
if person take up-to 2 steps at time(i.e either 1-step or 2-step) then to get no of steps we add
(n-1) +(last result)=(new result)

if person take up-to 3 steps at time(i.e either 3-step or 2-step or 1-step) then to get no of steps we add
(n-2)+(n-1) +(last result)=(new result)

similarly, 
if person take up-to m steps at time then to get no of steps we add
(n-(m-1))+(n-(m-1)-1) ..............+(last result)=(new result)

Generalize code:

#include <stdio.h> 
int n, m;
int Fibonacci(int n);
int main ()
{
 printf("total no of steps:");
 scanf("%d",&n);
 printf("max no of steps can climb:");
 scanf("%d",&m);
 printf("no of ways to climb is %d\n", Fibonacci(n+1));
   return 0;
}
int Fibonacci(int n)
{ int total=0,i;
  if ( n == 0 )
      return 0;
  if ( n == 1 )
      return 1;
    for ( i = 1; i<=m && i<=n; i++) //for m steps
        total += Fibonacci(n-i);
    return total;
}

output:-

total no of steps:4
max no of steps can climb:3
no of ways to climb is 7

SHARE