Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Reddit
Contact us
Hide Buttons

Distinct ways to reach the n’th stair

Problem: Given stair case with n stairs, count the number of ways in which you can climb the stairs.

Examples:


--- Number of stairs = 1 Ways to climb = (1) Ways(1) = 1 --- Number of stairs = 2 Ways to climb = (1,1), (2) Ways(2) = 2 --- Number of stairs = 3 Ways to climb = (1, 1, 1), (2, 1), (1, 2) Ways(3) = Ways(2) + Ways(1) = 3 --- Number of stairs = 4 Ways to climb = (1, 1, 1, 1), (1, 2, 1), (2, 1, 1), (1, 1, 2), (2, 2) Ways(3) = Ways(3) + Ways(2) = 3 + 2 = 5 ---

From the above examples, we can generalize this recursive pattern as follows :

Ways(n) = Ways(n-1) + Ways(n-2)

This equation is similar to Fibonacci numbers except the base values are different. One possible implementation of the above equation is shown below where we call the fib function recursively.

function fib(n) {
  if (n <= 1) {
    return n;
  }

  return fib(n-1) + fib(n-2);
}

Watch the following video to understand this puzzle with more examples!

Further reading :


You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *