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;

};

Comments

[Evgeny Artemov]

Could you provide me with some further explanations, why do you start i from 3 ?

[Maksym Parfenov]

hi
because for the first iteration where n = 1 we go to the first if and return 1
because for 1 step we have only 1 way
second iteration is also defined and return second is 2, because for 2 steps, we have also only 1 way, 1 step + 1 step
if n = 3 , we 're calculating only 1 iteration in for loop , and getting second = third which is result first + second , and we have 3 ways , 1 + 1, 1 + 2, 1 + 1 + 1 ,

other variants is about Fibonacci Fib(n) = Fib(n-1)+Fib(n-2)

[Noah Blumenstein]

I've seen this logic elsewhere that there's one way to climb 0 steps - that "you just don't climb". This makes no sense at all as your options are to take 1 step or 2 steps. Could anyone help clarify this?

[Paul Goble]

It only makes sense in the context of the Fibonacci sequence:
0, 1, 1, 2, 3, 5, 8, ...
which maps to the inputs:
undefined, 0, 1, 2, 3, 4, 5, ...
therefore a zero step produces a result of 1.

In this case however it is not allowed to take a zero step unless all other options are exhausted.