Count Ways To Reach The N-th Stairs

One basic approach is to explore all possible steps which can be climbed with either taking one step or two steps. So at every step, we have two options to climb the stairs either we can climb with one step, or we can climb with two steps. So the number of ways  can be recursively defined as :

countDistinctWayToClimbStair ( currStep, N ) = countDistinctWayToClimbStair ( currStep+1, N ) + countDistinctWayToClimbStair ( currStep + 2, N )

Where “currStep” denotes the current step on which the person is standing, and N denotes the destination step.

In the previous approach, we were naively calculating the results for every step. So there were lots of redundant calls because if we look at the recursion tree, then there are only ‘N’ distinct function calls. So we should avoid redundant function calling. For that, we decide to store the result at each step, and we will directly return the result for that step whenever a function is called again for those steps. We will be storing the result into “dp”.

Where dp[currStep] defines the number of distinct ways to climb the stairs from “currStep” to ‘N’-th steps.

As we have seen that this problem can be broken into subproblems. And many subproblems were the same, so for that; we were using memoization. So instead of storing the result through recursion, we are going to store the result iteratively. Our intuition is:

How can we reach “currStep” step in taking one step or two steps:

1. We can take the one-step from (currStep-1)th step or,
2. We can take the two steps from (currStep-2)th step.

So the total number of ways to reach “currStep” will be the sum of the total number of ways to reach at (currStep-1)th and the total number of ways to reach (currStep-2)th step.

So from storing ways of previous two steps we can calculate the number of ways for currStep in the following way.

currStepWays = dp[0] + dp[1]

Where ‘dp[0]’, denotes the number of ways to reach ‘(currStep-2)’th stair

and 

‘dp[1]’, denotes the number of ways to reach '(currStep-2)'th stair.

Now we will update this information for ‘currStep + 1’ in following way

dp[0] = dp[1]
dp[1] = currStepWays

The base case will be, If we have 0 stairs to climb then the number of distinct ways to climb will be one (we are already at Nth stair that’s the way) and if we have only one stair to climb then the number of distinct ways to climb will be one, i.e. one step from the beginning.

In the previous approach, we were using “dp” which took O(N) space. But there was no need of taking a space of O(N). Because if we look at any step of dp:

     dp[ currStep ] = dp[ currStep-1 ] + dp[ currStep-2 ]

We only need the answer of the two-step and the one-step before the “currStep” for evaluation of the “currStep”. So we can replace “dp” with two variables let’s say “oneStep” and “twoSteps”. Where “oneStep” denotes the total number of ways to reach (currStep-1)th step from beginning and “twoSteps” denotes the total number of ways to reach (currStep-2)th step from the beginning. So,

         currStep=oneStep+twoStep

So the above statement is (N-1)th Fibonacci Number. We can calculate the ‘N’th Fibonacci Number using Binary Matrix Exponentiation explained below. Here, Fn represents the nth Fibonacci number. We will raise the matrix to the power of (n - 1) so that the top-left element gives the value of F(n + 1 - 1) = F(n).

                               [[1 1] (pow n)          [[(F(n+1)  F(n)]

                                [1 0]]                =    [   F(n)      F(n-1)]]

1. So we need to find the (N - 1)th Power of this Matrix.
2. We can write a function for the multiplication of two matrices.
3. Then we can use binary exponentiation to calculate the ‘N’ power of this Matrix in log(N).
4. Binary Exponentiation / Fast Exponentiation:

long long binpow(Matrix a, long long b) {
if (b == 0)
     return 1;
Matrix res = binpow(a, b / 2);
if (b % 2)
     return res * res * a;
else
     return res * res;
}

1. Similarly, we can write a version for Matrix Exponentiation.
2. Take care of overflow using modulo by 10^9 + 7 at each operation of Matrix Multiplication.