Climbing stairs with 3 moves (Memoization)

There are n stairs, and a person standing at the bottom can climb either 1 stair, 2 stairs or 3 staris at a time, count the number of ways that a person can reach at the top.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Climbing stairs with 3 moves, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

• Initialize cache to store results.
• Using the key to check cached result. If the result is not found in the cache, do the calculation and save the result in cache.
• Return the cached result.

• Python
• Javascript
•  Run

cache = {}

def climb(n):
  if n < 0:
    return 0

  if n == 1:
    return 1

  if n == 2:
    return 2

  if n == 3:
    return 4
  
  if n not in cache:
    cache[n] = climb(n - 1) + climb(n - 2) + climb(n - 3)

  return cache[n]

n = 5

print(climb(n))

const cache = {}

function climb(n) {
  if (n < 0) {
    return 0;
  }

  if (n === 1) {
    return 1;
  }

  if (n === 2) {
    return 2;
  }

  if (n === 3) {
    return 4;
  }

  if (cache[n] === undefined) {
    cache[n] = climb(n - 1) + climb(n - 2) + climb(n - 3);
  } 
  
  return cache[n];
}

const n = 5;

console.log(climb(n));