If you're new to algorithms and leetcode, the staircase problem is infamous! 😬 What is the Staircase Programming Challenge? Stated simply.... 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? Imagine a staircase with N 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, times.  If is divisible by 2, you can take 2 steps, times.  Also, if is divisible by 3, you can take 3 steps, times. N N N/2 N N/3 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. is just a simple recursive counter. function steps(N, stepsTaken = 0) Let's walk through it: We're at the bottom of the stairs, no steps taken.  So . stepsTaken = 0 You have 3 possibilities in front of you: take 1 step, jump up 2 steps, or leap up 3 steps. 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 variable you’re carrying with you. You and your clones each go through one of these 'doors' (note each of you must go through a DIFFERENT door): stepsTaken steps(N,stepsTaken + 1)
steps(N,stepsTaken + 2)
steps(N,stepsTaken + 3) Once you go through your chosen door, 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: your individual stepsTaken steps(N,stepsTaken + 1)
steps(N,stepsTaken + 2)
steps(N,stepsTaken + 3) Again, you'll clone yourself 2 times and each go through one of these doors.  Your counter will increment by 1, 2, or 3. again steps stepsTaken again This will KEEP HAPPENING until: if (stepsTaken === N) return 1;
  else if (stepsTaken > N) return 0; , your combination of steps does NOT count towards the total of unique ways to go up the stairs. If you overstepped stepsTaken > N , then bingo 🤩 you found a legit combo of steps to go up the stairs, and you to add to the count of ways to go up the stairs. However, if (stepsTaken === N) return 1 Now remember the way we count the number of possible combinations of to reach the top of the step staircase is to simply add all the possibilities: stepsTaken N return steps(N,stepsTaken + 1) + steps(N,stepsTaken + 2) + steps(N,stepsTaken + 3); Remember each legitimate combo of steps where and each if path is not valid (overstep) then 0 is returned : else . if (stepsTaken === N) return 1 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 for more illuminating
content. 🤓 Indepth JavaScript

Solving The Staircase Problem With Just 5 Lines

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

13 Ways to Traverse a Tree: Recursion vs Iteration

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

13 Ways to Traverse a Tree: Recursion vs Iteration

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps