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.

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.

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

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.

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

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

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

Notice any pattern in the output?

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;
  //...
}

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;
  //...
}

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;
}

--

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