## Question

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

## Summary

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

## Solution

#### Approach #1 Brute Force [Time Limit Exceeded]

Algorithm

In this brute force approach we take all possible step combinations i.e. 1 and 2, at every step. At every step we are calling the function for step and , and return the sum of returned values of both functions.

, where defines the current step and defines the destination step.

Java

public class Solution {
public int climbStairs(int n) {
climb_Stairs(0, n);
}
public int climb_Stairs(int i, int n) {
if (i > n) {
return 0;
}
if (i == n) {
return 1;
}
return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
}
}


Complexity Analysis

• Time complexity : . Size of recursion tree will be .

Recursion tree for n=5 would be like this:

• Space complexity : . The depth of the recursion tree can go upto .

#### Approach #2 Recursion with memorization [Accepted]

Algorithm

In the previous approach we are redundantly calculating the result for every step. Instead, we can store the result at each step in array and directly returning the result from the memo array whenever that function is called again.

In this way we are pruning recursion tree with the help of array and reducing the size of recursion tree upto .

Java

public class Solution {
public int climbStairs(int n) {
int memo[] = new int[n + 1];
return climb_Stairs(0, n, memo);
}
public int climb_Stairs(int i, int n, int memo[]) {
if (i > n) {
return 0;
}
if (i == n) {
return 1;
}
if (memo[i] > 0) {
return memo[i];
}
memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
return memo[i];
}
}


Complexity Analysis

• Time complexity : . Size of recursion tree can go upto .

• Space complexity : . The depth of recursion tree can go upto .

#### Approach #3 Dynamic Programming [Accepted]

Algorithm

As we can see this problem can be broken into subproblems, and it contains the optimal substructure property i.e. its optimal solution can be constructed efficiently from optimal solutions of its subproblems, we can use dynamic programming to solve this problem.

One can reach step in one of the two ways:

1. Taking a single step from step.

2. Taking a step of from step.

So, the total number of ways to reach is equal to sum of ways of reaching step and ways of reaching step.

Let denotes the number of ways to reach on step.

Example:

!?!../Documents/70_Climbing_Stairs.json:1000,563!?!

Java

public class Solution {
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}


Complexity Analysis

• Time complexity : . Single loop upto .

• Space complexity : . array of size is used.

#### Approach #4 Fibonacci Number [Accepted]:

Algorithm

In the above approach we have used array where . It can be easily analysed that is nothing but fibonacci number.

Now we just have to find number of the fibonacci series having and their first and second term respectively i.e. and .

Java

public class Solution {
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
int first = 1;
int second = 2;
for (int i = 3; i <= n; i++) {
int third = first + second;
first = second;
second = third;
}
return second;
}
}


Complexity Analysis

• Time complexity : . Single loop upto is required to calculate fibonacci number.

• Space complexity : . Constant space is used.

#### Approach #5 Binets Method [Accepted]:

Algorithm

This is an interesting solution which uses matrix multiplication to obtain the Fibonacci Number. The matrix takes the following form:

.

Let's say

As per the method, the Fibonacci Number is given by

Let's look at the proof of this method.

We can prove this method using Mathematical Induction. We know, this matrix gives the correct result for the term(base case). Since . This proves that the base case holds.

Assume that this method holds for finding the Fibonacci Number i.e. , where .

Now, we need to prove that with the above two conditions holding true, the method is valid for finding the Fibonacci Number i.e.

Proof: .

Thus, . This completes the proof of this method.

The only variation we need to do for our problem is that we need to modify the initial terms to 2 and 1 instead of 1 and 0 in the Fibonacci series. Or, another way is to use the same initial matrix and use to get the final result. This happens because the initial terms we have to use are the 2nd and 3rd terms of the otherwise normal Fibonacci Series.

Java

public class Solution {
public int climbStairs(int n) {
int[][] q = {{1, 1}, {1, 0}};
int[][] res = pow(q, n);
return res[0][0];
}
public int[][] pow(int[][] a, int n) {
int[][] ret = {{1, 0}, {0, 1}};
while (n > 0) {
if ((n & 1) == 1) {
ret = multiply(ret, a);
}
n >>= 1;
a = multiply(a, a);
}
return ret;
}
public int[][] multiply(int[][] a, int[][] b) {
int[][] c = new int[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
}
}
return c;
}
}


Complexity Analysis

• Time complexity : . Traversing on bits.

• Space complexity : . Constant space is used.

Proof of Time Complexity:

Let's say there is a matrix to be raised to power . Suppose, is the power of 2. Thus, , , where represents the set of natural numbers(including 0). We can represent in the form of a tree:

Meaning that:

So, to calculate matrix, we should calculate matrix and multiply it by itself. To calculate we would have to do the same with and so on.

Obviously, the tree height is .

Let’s estimate calculation time. matrix is of the same size in any power . Therefore, we can perform the multiplication of two matrices in any power in . We should perform of such multiplications. So, calculation complexity is .

In case, the number is not a power of two, we can break it in terms of powers of 2 using its binary representation

, where .

Thus, we can obtain the final result using:

This is the method we've used in our implementation. Again, the complexity remains as we have limited the number of multiplications to .

#### Approach #6 Fibonacci Formula [Accepted]:

Algorithm

We can find fibonacci number using this formula:

For the given problem, the Fibonacci sequence is defined by , , , . A standard method of trying to solve such recursion formulas is assume of the form . Then, of course, and so the equation becomes . If we divide the entire equation by an we arrive at or the quadratic equation

.

Solving this by the quadratic formula, we get:

.

The general solution, thus takes the form:

For , we get

For , we get

Solving the above equations, we get:

Putting these values of and in the above general solution equation, we get:

Java

public class Solution {
public int climbStairs(int n) {
double sqrt5=Math.sqrt(5);
double fibn=Math.pow((1+sqrt5)/2,n+1)-Math.pow((1-sqrt5)/2,n+1);
return (int)(fibn/sqrt5);
}
}


Complexity Analysis

• Time complexity : . method takes time.

• Space complexity : . Constant space is used.

Analysis written by: @vinod23