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

Cover image for The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant
Alisa Bajramovic
Alisa Bajramovic

Posted on

The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant

Today's algorithm is the Climbing Stairs problem:

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.

For example, if the input were 2 (there's 2 stairs in the staircase), then there are 2 distinct ways to climb to the top. You can either climb one step at a time, or climb both steps at once.

Two 2-step staircases. In the first staircase, a blue line goes from the base to the first step, then from the first step to the second step (one step at a time). In the second staircase, a red line goes from the base to the second step (two steps at a time).

This is one of those problems where there's a lot of ways to solve it--including recursion and memoization, and dynamic programming--but the solution I like the most involves the Fibonacci number. In this post, I'll explain what the Fibonacci numbers are, their relevance to this problem, and how to solve the algorithm.

The Fibonacci Numbers

What are they?

The Fibonacci numbers (also known as the Fibonacci sequence) are a series of numbers defined by a recursive equation:

Fn = Fn-1 + Fn-2

The sequence starts with F0 = 0, and F1 = 1. That means that F2 = 1, because F2 = F1 + F0 = 1 + 0. Then, F3 = 2, because F3 = F2 + F1 = 1 + 1. The sequence continues on infinitely: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

You can read more about Fibonacci numbers here.

Why are Fibonacci numbers relevant in the staircase problem?

Let's look at a few examples of the expected output of the staircase problem. We can start with n = 0. That means the staircase has 0 steps. There's 0 ways to climb this staircase, so when n = 0, the output = 0.

`n = 0` written in black. Then a short straight line indicating 0 steps. Then `output = 0` written in green.

When n = 1, the staircase has 1 step. There's 1 way to climb this staircase, so when n = 1, the output = 1.

`n = 1` written in black. Then a 1 step staircase in black, which a blue line going from the base to to the top of step 1. Then `output = 1` written in green.

When n = 2, the staircase has 2 steps. Since we can either climb 1 or 2 stairs at a time, there's 2 ways to climb this staircase. So, when n = 2, the output = 2.

`n = 2` written in black. Then two 2-step staircases. In the first staircase, a blue line goes from step 0 to 1, 1 to 2. In the second staircase, a red line goes from step 0 to 2. Then `output = 2` written in green.

When n = 3, the staircase has 3 steps. There are 3 ways we can climb this staircase.

`n = 3` written in black. Then three 3-step staircases. In the first staircase, a blue line goes from step 0 to 1, 1 to 2, 2 to 3. In the second staircase, a red line goes from step 0 to 2, 2 to 3. In the third staircase, a green line goes from step 0 to 1, 1 to 3. Then `output = 3` written in green.

We can keep doing this for when n = 4 (output = 5)...

`n = 4` written in black. Then five 4-step staircases. In the first staircase, a blue line goes from step 0 to 1, 1 to 2, 2 to 3, 3 to 4. In the second staircase, a red line goes from step 0 to 2, 2 to 4. In the third staircase, a green line goes from step 0 to 2, 2 to 3, 3 to 4. In the fourth staircase, an orange line goes from 0 to 1, 1 to 2, 2 to 4. In the fifth staircase, a purple line goes from 0 to 1, 1 to 3, 3 to 4. Then `output = 5` written in green.

... and n = 5 (output = 8).

`n = 5` written in black. Then eight 5-step staircases. In the first staircase, a blue line goes from step 0 to 1, 1 to 2, 2 to 3, 3 to 4, 4 to 5. In the second staircase, a red line goes from step 0 to 2, 2 to 4, 4 to 5. In the third staircase, a green line goes from step 0 to 2, 2 to 3, 3 to 5. In the fourth staircase, an orange line goes from 0 to 1, 1 to 3, 3 to 5. In the fifth staircase, a pink line goes from 0 to 1, 1 to 2, 2 to 4, 4 to 5. In the sixth staircase, a purple line goes from 0 to 1, 1 to 2, 2 to 3, 3 to 5. In the seventh staircase, a cyan line goes from 0 to 2, 2 to 3, 3 to 4, 4 to 5. In The eight staircase, a navy line goes from 0 to 1, 1 to 3, 3 to 4, 4 to 5. Then `output = 8` written in green.

Notice any pattern in the output?

A table with two rows and 6 column. First row is n, in black, second row is output, in blue. When n is 0, output is 0. When n is 1, output is 1. When n is 2, output is 2. When n is 3, output is 3. When n is 4, output is 5, when n is 5, output is 8.

We can see the Fibonacci sequence in our outputs! Each time we increment n, the number of ways to climb the staircase is the sum of the previous two ways. That means that we can solve the staircase problem by solving for the Fibonacci number at each stair, until we get to n.

Solving the Algorithm

Now that we've recognized the pattern in the output, we can go ahead and solve the algorithm. To start, we need to write out a few base cases. When n is 0, 1, and 2, the number of ways to climb the stairs 0, 1, and 2 (in that order) -- so if n is one of those numbers, we can just return n.

function climbStairs3(n) {
  if (n < 3) return n;
  //...
}
Enter fullscreen mode Exit fullscreen mode

We need to initialize two constants, one called first and one called second. We'll start by setting first equal to 1, and second equal to 2. We'll be using these numbers to add up to the current number we're on, and will continue to change them.

function climbStairs3(n) {
  if (n < 3) return n;
  let first = 1;
  let second = 2;
  //...
}
Enter fullscreen mode Exit fullscreen mode

Now, starting at the number 2, and going until we reach n, we can have a for loop incrementing one number at a time. Inside the for loop, we'll initiate a new variable called current which will store the sum of first and second. Then, we can move first over to equal second, and second to equal current.

Once the for loop ends, we'll want to return whatever the second number was.

function climbStairs3(n) {
  if (n < 3) return n;
  let first = 1;
  let second = 2;
  for (let i = 2; i < n; i++) {
    const current = first + second;
    first = second;
    second = current;
  }

  return second;
}
Enter fullscreen mode Exit fullscreen mode

--

Please let me know if you have any questions or other ways of solving this!

Top comments (9)

Collapse
 
cgenie profile image
CGenie

Could use a proof that this indeed makes a Fibonacci sequence. Couting to 5 and concluding it must be that sequence is wrong. Just look at how many possible (named) sequences are there:
https://oeis.org/search?q=0%2C1%2C2%2C3%2C4%2C8&language=english&go=Search

Collapse
 
ajgrover profile image
ajgrover • Edited on

For anybody unsure of how to prove this, a strong inductive proof follows easily.


Base: n=1 has one solution and n=2 has two solutions (2 single steps or a double step) which are Fib(1) and Fib(2), respectively.

Step: In order to get to step n+1, you must've originated from step n (and then single stepped) or step n-1 (and double stepped). Therefore summing all ways to get to n and n-1 will get you how many ways to get to n+1. Invoking the strong hypothesis, the number of ways to get to step n-1 is the Fib(n-1) and the number of ways to get to step n is Fib(n). Summing Fib(n) and Fib(n-1) gets you Fib(n+1) by the definition of the Fibonacci sequence.

Collapse
 
stemdeafteacher profile image
Harry Wood

What does the i and the i++ mean in the final image? I don't see any explanation for it. I was with you up until that point. Thanks.

Collapse
 
alisabaj profile image
Alisa Bajramovic

Hi Harry,
"For loops" are great for if you want to do something a certain number of times. In this case, we wanted to alter the variables first, second, and current until we reached the number n (which is the input value). For loops have this syntax where you declare a variable (in this case, i), initialize its starting index (in this case, 2), set its condition to keep executing (in this case, keep executing as long as i < n), and state how the variable will be updated each time we go through the loop (in this case, i increments every time we go through the loop). The syntax i++ is the shorthand for i = i + 1. You can find a longer explanation here. Hope this helps!

Collapse
 
stemdeafteacher profile image
Harry Wood

Ah, I think I understand now. It's sort of like a counter ?

Collapse
 
chintukarthi profile image
Karthikeyan Dhanapal

Thanks for this explanation :)

Collapse
 
javiersalcedopuyo profile image
Javier Salcedo

Well explained!
This particular problem was really hard for me the first time I encountered it.
I still have a little hate towards it hahaha

Collapse
 
jpkontreras profile image
Julio Contreras Marchant

good content!

Collapse
 
goelajit profile image
ajit goel

great explanation, thank you @alisabaj

πŸ‘‹ Hey, my name is Noah and I’m the one who set up this ad. My job is to get you to join DEV, so if you fancy doing me a favor, I’d love for you to create an account.

If you found DEV from searching around, here are a couple of our most popular articles on DEV: