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?
If you enjoyed this article please check out my blog
Indepth JavaScript for more illuminating
content. 🤓
Top comments (0)