DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 966,155 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
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;

};

Top comments (2)

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 on

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)

πŸŒ–πŸŒ—πŸŒ˜ Turn on dark mode in Settings