Count ways to reach the n'th stair - GeeksforGeeks

Count ways to reach the n'th stair - GeeksforGeeks
There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top.

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

there is one thing to notice, the value of ways(n) is equal to fibonacci(n+1).

ways(1) = fib(2) = 1
ways(2) = fib(3) = 2
ways(3) = fib(4) = 3

Generalization of the above problem
How to count number of ways if the person can climb up to m stairs for a given value m? For example if m is 4, the person can climb 1 stair or 2 stairs or 3 stairs or 4 stairs at a time.

We can write the recurrence as following.

   ways(n, m) = ways(n-1, m) + ways(n-2, m) + ... ways(n-m, m) 

int countWaysUtil(int n, int m)

{

    int res[n];

    res[0] = 1; res[1] = 1;

    for (int i=2; i<n; i++)

    {

       res[i] = 0;

       for (int j=1; j<=m && j<=i; j++)

         res[i] += res[i-j];

    }

    return res[n-1];

}

 

// Returns number of ways to reach s'th stair

int countWays(int s, int m)

{

    return countWaysUtil(s+1, m);

}

// A recursive function used by countWays

int countWaysUtil(int n, int m)

{

    if (n <= 1)

        return n;

    int res = 0;

    for (int i = 1; i<=m && i<=n; i++)

        res += countWaysUtil(n-i, m);

    return res;

}

Program for Fibonacci numbers
http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ……..
DP:

  for (i = 2; i <= n; i++)

  {

     c = a + b;

     a = b;

     b = c;

  }

Method 4 ( Using power of the matrix {{1,1},{1,0}} ) Log(N)

The matrix representation gives the following closed expression for the Fibonacci numbers:

int fib(int n)

{

  int F[2][2] = {{1,1},{1,0}};

  if (n == 0)

      return 0;

  power(F, n-1);

 

  return F[0][0];

}

 

void multiply(int F[2][2], int M[2][2])

{

  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];

  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];

  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];

  int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];

 

  F[0][0] = x;

  F[0][1] = y;

  F[1][0] = z;

  F[1][1] = w;

}

 

void power(int F[2][2], int n)

{

  int i;

  int M[2][2] = {{1,1},{1,0}};

 

  // n - 1 times multiply the matrix to {{1,0},{0,1}}

  for (i = 2; i <= n; i++)

      multiply(F, M);

}

Read full article from Count ways to reach the n'th stair - GeeksforGeeks