Find Nth Catalan Number (Memoization)

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Catalan number, 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 = None

def C(n):
  if (n <= 1):
    return 1

  global cache
  if not cache:
    cache = [None for _ in range(n + 1)]

  if not cache[n]:      
    result = 0

    for i in range(n):
      result += C(i) * C(n - 1 - i)
    
    cache[n] = result

  return cache[n]

n = 5

print(C(n))

const cache = [];

function C(n) {
  if (n <= 1) {
    return 1;
  }

  if (cache[n] === undefined) {
    let result = 0;

    for (let i = 0; i < n; i++) {
      result += C(i) * C(n - 1 - i);
    }

    cache[n] = result;
  }

  return cache[n];
}

const n = 5;

console.log(C(n));