Leetcode - Climbing Stairs (with JavaScript)

Today I am going to show how to solve the Climbing Stairs algorithm problem.

Here is the problem:

I am going to build a tree to help better understand the solution to this problem.

Let’s determine in how many distinct ways we can climb to the top of a 4-step staircase.

I am going to add branches to the tree based on the number of steps we can take. In this problem, we can either take 1 step or 2 steps. If we take 1 step, we will have to climb 3 more steps. If we take 2 steps, we will have 2 steps left. I will continue to add branches until I reach the base cases:

• When we have 0 steps, how many ways are there to climb? There's 1 way - we just don’t climb.
• When we have 1 step, how many ways are there to climb? There's 1 way - just climbing on that one step.

To calculate the total number of ways to climb the staircase, we have to first figure out how many ways there are to get to each step, starting from the bottom. We then add the number of ways for each step together and find that there are a total of 5 ways to climb a 4-step staircase.

Now we can see that the solution to this problem is the sum of its subproblems. In our case, the total number of ways to climb a 4-step staircase is the sum of the total ways to climb a 3-step staircase and a 2-step staircase. Based on that we can write:
num_ways(4) = num_ways(3) + num_ways(2)
For n number of steps, the equation is:
num_ways(n) = num_ways(n-1) + num_ways(n-2)

This is actually a fibonacci sequence. Each number in a fibonacci sequence is the sum of the two preceding ones, starting from 0 and 1.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Fib(n)=Fib(n−1)+Fib(n−2)

So the solution will be:

var climbStairs = function(n) {
    if (n == 1 || n == 0) return 1 // our base cases

    let first = 1;
    let second = 2;

    for (let i = 3; i <= n; i++) {
        let third = first + second;
        first = second;
        second = third;
    }
    return second;

};