Staircase.md

Prompt

Given a staircase with a given number of stairs, num, write a function that returns the number of different ways one can climb this set of stairs. A person is able to climb the stairs either one at a time, or skip a step, or a mix of both.

Examples

climbStairs(2); // should return 2: one step at a time (1 + 1), or skip a step (2).
climbStairs(0); // should return 1
climbStairs(1); // should return 1
climbStairs(5); // should return 8
climbStairs(100); // should return 573147844013817200640

Getting Started

Feel free to diagram out yourself how you would go up these steps! There may be a pattern that you can take advantage of in your code. Ask yourself

• What does it mean to have only 0, 1, 2 steps?
• What happens when I have 3 steps? 4?

Once you come to a good solution:

• What happens on large input sizes like 15, or even 1000? Will this program timeout?

Initial Solution (Recursive Brute Force)

function climbStairs(num) {
  if (num === 1 || num === 0) return 1; // this is our base case;
  return climbStairs(num - 1) + climbStairs(num - 2); // otherwise we can add up recursively the other possibilities
}

Simple right? It's just two lines, so this function looks pretty neat. However, if we look at the time complexity, it comes out to be O(2^n), exponential. As soon as we plug in a number like 20, this program will take a significant amount of time to run!

Let's take a look at the space complexity: Our recursive calls will look like the above tree, where the depth of our tree is n. Given this, our space complexity will be O(n), scaling with the depth of the tree.

Overall, this solution works, but is too expensive to run. Let's try and optimize it.

Another Solution (Optimized Recursion)

function climbStairs(n, memo = {}) {
    if (n === 0 || n === 1) {
        if (memo[n]) {
            return memo[n];
        }
        else {
            memo[n] = 1;
            return 1;
        }
    }
    if (memo[n]) {
        return memo[n];
    }
    else {
        memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
        return memo[n];
    }
};

Here we'll use a memo object, common in dynamic programming. What we want to do is keep track of all the previous recursive calls we've made, and store them in our object. This way, we will not need to make repeated calls to climbStairs(2), for example, every time a number greater than 2 is recursively called. This will improve our runtime to O(n), which is significantly more manageable. Our space complexity remains the same at O(n), scaling with the depth of our recursion tree once again (and also our memo object). Now our function can run larger inputs like 20, or even 1000, with much more ease.

Wait, there's more!

We can also take a stab at improving our space complexity. Lets take a look:

function climbStairs(num) {
  if (num === 1 || num === 0) return 1;
  let first = 1;
  let second = 2;
  for (let i = 3; i <= num; i++) { // climbing stairs is really similar to Fibonacci sequences...
    let third = first + second;
    first = second;
    second = third;
  }
  return second; // this is equal to our last third value, which is the total num ways of climbing the stairs
}

If you are unfamiliar with Fibonacci series, don't worry! Here is how they work: given a pair of numbers, such as 1 and 2, what we will do is add up our two previous numbers to get our next number, in this case 3. We keep going for as long as the Fibonacci sequence dictates. This looks really similar to our starcase problem, huh...

Given that similarity, we could approach the staircase problem the same way, with our first numbers of our series being 1 step and 2 step stairs, and then our series going up to the input number of our function. Our last number should equal the number of ways to climb our staircase! Our time complexity remains the same at O(n), where n is our input number value. Our space is now improved to O(1) constant space, given that we are no longer using memoization or recursion.