DEV Community

Urfan Guliyev
Urfan Guliyev

Posted on • Updated on

Leetcode - Climbing Stairs (with JavaScript)

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

Here is the problem:
Alt Text

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.

Alt Text

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;

};



Enter fullscreen mode Exit fullscreen mode

Top comments (4)

Collapse
 
evgenyartemov profile image
Evgeny Artemov

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

Collapse
 
maparr profile image
Maksym Parfenov • Edited

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)

Collapse
 
roadtomoab profile image
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?

Collapse
 
paulgoble profile image
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.