Amit Mehta
Indepth JavaScript

Indepth JavaScript

How to Solve the Staircase Problem with JavaScript using Memoization

How to Solve the Staircase Problem with JavaScript using Memoization

Amit Mehta's photo
Amit Mehta
ยทJul 8, 2022ยท

2 min read

I want to write a quick follow up to my last 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?

mewoization

Did you find this article valuable?

Support Amit Mehta by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
ย 
Share this