How to Solve the Staircase Problem with 5 Lines of JavaScript

If you're new to algorithms and leetcode, the staircase problem is infamous!

What is the Staircase Programming Challenge?

Stated simply....

Imagine a staircase with N steps. If you can take 1, 2, or 3 steps at a time, how many different ways can you reach the top of the stairs?

Encountering a problem like this for the first time is for sure frightening. Even on its own as a math problem, IT'S REALLY HARD.

There are a few obvious cases. You can take 1 step at a time, N times. If N is divisible by 2, you can take 2 steps, N/2 times. Also, if N is divisible by 3, you can take 3 steps, N/3 times.

And then there is everything in between. 🤔

The good news is there is a really simple way to solve this problem using everyone's favorite algorithm: recursion. 😨

Recursion to the Rescue

As promised, here is the solution in 5 lines of JavaScript code...

// N is total number of steps in the staircase
// stepTaken is a counter for steps taken in each combination
function steps(N, stepsTaken = 0) {

  if (stepsTaken === N) return 1;
  else if (stepsTaken > N) return 0;

  return steps(N,stepsTaken + 1) + steps(N,stepsTaken + 2) + steps(N,stepsTaken + 3);
}

Yikes! What does this mean??

*Don't panic or feel bad if the above code confuses you. * I struggled for a long time with recursion since I first learned it in high school CS class. It's tricky for sure. * But once you understand it, it opens up a whole new world of possibilities!*

Let's walk through this solution

If you're thinking of just copying the above solution and leaving, you're missing the point. It's super important you understand what's happening.

function steps(N, stepsTaken = 0) is just a simple recursive counter.

Let's walk through it:

1. We're at the bottom of the stairs, no steps taken. So stepsTaken = 0.
2. You have 3 possibilities in front of you: take 1 step, jump up 2 steps, or leap up 3 steps.
3. Now we need to account for ALL 3 possibilities. So imagine you clone the stairs and yourself 2 times. Plus, you each have your own version of stepsTaken variable your carrying with you. You and your clones each go through one of these 'doors' (note each of you must go through a DIFFERENT door):

steps(N,stepsTaken + 1)
steps(N,stepsTaken + 2)
steps(N,stepsTaken + 3)

Once you go through your chosen door, your individual stepsTaken counter will be incremented by 1, 2, or 3 (depending on the door you went through). Then after that, you'll immediately see 3 more doors:

steps(N,stepsTaken + 1)
steps(N,stepsTaken + 2)
steps(N,stepsTaken + 3)

Again, you'll clone yourself 2 times again and each go through one of these steps doors. Your stepsTaken counter will increment again by 1, 2 or 3. This will KEEP HAPPENING until :

  if (stepsTaken === N) return 1;
  else if (stepsTaken > N) return 0;

If you overstepped stepsTaken > N, your combination of steps does NOT count towards the total of unique way to go up the stairs.

However, if (stepsTaken === N), then bingo 🤩 you found a legit combo of steps to go up the stairs and you return 1 to add to the count of way to go up the stairs.

1. Now remember the way we count the number of possible combinations of stepsTaken to reach the top of the N step staircase, is to simply add all the possibilities:

return steps(N,stepsTaken + 1) + steps(N,stepsTaken + 2) + steps(N,stepsTaken + 3);

Remember each legitimate combo of steps where if (stepsTaken === N) return 1 and each if path is not valid (overstep) then 0 is returned : else if (stepsTaken > N) return 0.

Some of you may be asking: Nice, this is elegant, but isn't it super inefficient in terms of time complexity?

Yea, it's super high time complexity. However, there's a trick to dramatically improving that ➡️ How to Solve the Staircase Problem with JavaScript using Memoization

Hope this makes sense, comment below if you have any questions?

If you enjoyed this article, please check out my blog Indepth JavaScript for more illuminating content. 🤓

Comments

[Erhan Tezcan]

A cool thing about the recursive solution and the nature of this problem is that it can be solved in reverse!

Instead of starting at the bottom and going up, you can start from the top and go to the bottom of the staircase. The code is very similar, but does not require the stepsTaken variable:

function stepsReverse(N) {
  if (0 === N) return 1;
  else if (0 > N) return 0;
  return stepsReverse(N-1) + stepsReverse(N-2) + stepsReverse(N-3);
}

Good article!

[Christian Kozalla]

great article! Once I've copied the steps function to the browser console of this tab and played around with it, and reading through your great explanation, I understand what this function represents: a tree diagram of climbing up the stairs, one step after the other.. i can literally see the tree in front of me. Every node represents a step, and from each step, we have to make one of three choices for the next step :D

[Amit Mehta]

Yes! A tree is a brilliant way of thinking about it!

[Freddy Global]

Great explanation, thank you!