How to Crack the Staircase Problem with JavaScript using Memoization

#javascript #algorithms #webdev #programming

I want to write a quick follow up to a previous post on How to Solve the Staircase Problem with 5 Lines of JavaScript.

It's a very elegant solution to the infamous staircase problem, *however, as one commentor noted it's terribly inefficient to the order of O(3^n).😖

Yikes! So Now What?

There's a cool trick with a funny name to fix this problem: Memoization. Yea, I'm not exactly sure how to pronounce it either! 😂

Here's what the staircase problem looks like memoitized...

function stairSteps(N) {

  // store repeat values in memo to prevent repeat computations
  const memo = [];

  function stepsM(N) {

    if (N === 0) return 1;
    else if (N < 0) return 0;

    if (memo[N] !== undefined) return memo[N];
    else {
      memo[N] = stepsM(N - 1) + stepsM(N - 2) + stepsM(N - 3);
      return memo[N];
    }
  }

  return stepsM(N);
}

The idea is simple: the array memo just stores values that may repeat, so you can reference them later instead of having to calculate them again - which is SUPER expensive in the case of recursion.

For example...

Once you know the value of stepsM(N-3) which is calculated on the first round of stepsM(N), you do NOT need to calculate its value again when it's called later by stepsM(N-1) or stepsM(N-2).

Pretty neat, huh?