## 70. Climbing Stairs

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.

Example 1:

Input: 2
Output:  2
Explanation:  There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps


Example 2:

Input: 3
Output:  3
Explanation:  There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step


b'
\n\n

## Summary

\n

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

\n

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

\n

## Solution

\n
\n

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

\n

Algorithm

\n

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.

\n

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

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Size of recursion tree will be .

\n

Recursion tree for n=5 would be like this:

\n \n
• \n
• \n

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

\n
• \n
\n
\n

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

\n

Algorithm

\n

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.

\n

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

\n\n

Complexity Analysis

\n
\n
• \n

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

\n
• \n
• \n

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

\n
• \n
\n
\n

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

\n

Algorithm

\n

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.

\n

One can reach step in one of the two ways:

\n
\n
1. \n

Taking a single step from step.

\n
2. \n
3. \n

Taking a step of from step.

\n
4. \n
\n

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

\n

Let denotes the number of ways to reach on step.

\n

\n\n

\n

Example:

\n\n

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

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Single loop upto .

\n
• \n
• \n

Space complexity : . array of size is used.

\n
• \n
\n
\n

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

\n

Algorithm

\n

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

\n

\n\n

\n

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

\n\n

Complexity Analysis

\n
\n
• \n

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

\n
• \n
• \n

Space complexity : . Constant space is used.

\n
• \n
\n
\n

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

\n

Algorithm

\n

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

\n

\n.

\n

Let\'s say \n

\n

As per the method, the Fibonacci Number is given by \n

\n

Let\'s look at the proof of this method.

\n

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.

\n

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

\n

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

\n

Proof: .\n \n\n

\n

Thus, . This completes the proof of this method.

\n

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.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Traversing on bits.

\n
• \n
• \n

Space complexity : . Constant space is used.

\n
• \n
\n

Proof of Time Complexity:

\n

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:

\n \n

Meaning that:

\n

\n\n

\n

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.

\n

Obviously, the tree height is .

\n

Let\xe2\x80\x99s 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 .

\n

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

\n

\n, where .

\n

Thus, we can obtain the final result using:

\n

\n\n

\n

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

\n
\n

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

\n

Algorithm

\n

We can find fibonacci number using this formula:

\n

\n\n

\n

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

\n

\n.

\n

Solving this by the quadratic formula, we get:

\n

\n.

\n

The general solution, thus takes the form:

\n

\n\n

\n

For , we get \n

\n

For , we get \n

\n

Solving the above equations, we get:

\n

\n\n

\n

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

\n

\n\n

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . method takes time.

\n
• \n
• \n

Space complexity : . Constant space is used.

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'