This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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:2Output:2Explanation:There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps

**Example 2:**

Input:3Output:3Explanation: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## Summary

\n## Solution

\n

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

\n

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

\n

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

\n

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

\n

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

\n

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

\n

\n

'
\n\n

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

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

\n\n

**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.

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

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : . Size of recursion tree will be .

\nRecursion 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

**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.

\nIn 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
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

**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.

\nOne can reach step in one of the two ways:

\n- \n
- \n
Taking a single step from step.

\n \n - \n
Taking a step of from step.

\n \n

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

\nLet denotes the number of ways to reach on step.

\n\n\n

\nExample:

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

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : . Single loop upto .

\n \n - \n
Space complexity : . array of size is used.

\n \n

\n

**Algorithm**

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

\n\n\n

\nNow 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
Time complexity : . Single loop upto is required to calculate fibonacci number.

\n \n - \n
Space complexity : . Constant space is used.

\n \n

\n

**Algorithm**

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

\n\n.

\nLet\'s say \n

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

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

\nWe 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.

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

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

\nProof: .\n \n\n

\nThus, . This completes the proof of this method.

\nThe 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
Time complexity : . Traversing on bits.

\n \n - \n
Space complexity : . Constant space is used.

\n \n

Proof of Time Complexity:

\nLet\'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\nMeaning that:

\n\n\n

\nSo, 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.

\nObviously, the tree height is .

\nLet\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 .

\nIn 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 .

\nThus, we can obtain the final result using:

\n\n\n

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

\n\n

**Algorithm**

We can find fibonacci number using this formula:

\n\n\n

\nFor 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.

\nSolving this by the quadratic formula, we get:

\n\n.

\nThe general solution, thus takes the form:

\n\n\n

\nFor , we get \n

\nFor , we get \n

\nSolving the above equations, we get:

\n\n\n

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

\n\n\n

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : . method takes time.

\n \n - \n
Space complexity : . Constant space is used.

\n \n

\n

Analysis written by: @vinod23

\n