# Climbing Stairs Solution 2

We previously came up with a solution for this problem by using a recursive formula that represents how many distinct ways we can climb the stairs.
The issue with the previous solution is it has a time complexity of O(2ⁿ) which is very inefficient.
To come up with a better solution we'll be drawing out multiple recursion trees to help us see a pattern.
When n = 1 we have:

From the diagram we can see there is 1 distinct way to climb to the top when n = 1 since we can ignore the scenarios where we take extra steps.
When n = 2 we have:

So, we have 2 distinct ways to climb to the top.
When n = 3 we have:

So, we have 3 distinct ways to climb to the top.
When n = 4 we have:

So, we have 5 distinct ways to climb to the top.
Now, let's take a look at our cases from n = 1 to n = 2 and see if we can find a pattern:

Here, waysToClimb denotes our function for determining how many unique ways we can climb the stairs.
This sequence of numbers follows the Fibonacci sequence with the only difference being the value of the 1^st and 2^nd terms.
Here, the 1^st term has a value of 1 and the 2^nd term has a value of 2.
Also, notice that we know we have two ways to climb the stairs to reach the n^th step.
If we take 1 step, then we're n - 1 steps closer to n, and if we take 2 steps then we're n - 2 steps closer to n.
So, we can get the distinct number of ways to climb the steps by summing up the ways of climbing to the n - 1 step and the ways of climbing to the n - 2 step using the following formula:

The Fibonacci sequence is the following series of numbers:

The next number is found by adding up the two numbers before it.
For example, 5 is found by adding 2 and 3.
The first two terms are called seed numbers, which we'll denote as:

Here's the formula used to characterize the sequence:

The seed numbers for our problem are:

Now that we know our pattern of climbing the stairs follows a Fibonnaci sequence we can implement the sequence in our code using the waysToClimb formula and the seed numbers we came up with.
This will improve the time complexity of our solution from the O(2ⁿ) solution we previously came up with.

# Implementation

var climbStairs = function(n) {
  if (n === 1) {
    return 1;
  } else if (n === 2) {
    return 2;
  } else {
    let waysToClimb1 = 1;
    let waysToClimb2 = 2;
    let waysToClimb;
    let i = 1;

    while (n - 1 > i) {
      waysToClimb = waysToClimb2 + waysToClimb1;
      waysToClimb1 = waysToClimb2;
      waysToClimb2 = waysToClimb;
      i++;
    }

    return waysToClimb;
  }
};

let n = 4;
console.log(climbStairs(n));

# Analysis

Since we're looping over the length of n - 1 our time complexity is O(n) which is a much more efficient solution!
See if you can come up with an even more efficient solution using more properties of the Fibonnaci sequence!