Pascal's Triangle (Memoization)

Given an integer n, find the first n rows of Pascal's triangle.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Pascal's Triangle, 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 binomial(n, k):
  if n < 0 or n < k:
    return 0

  if k == 0 or k == n:
    return 1
  
  global cache
  if not cache[n][k]:
    cache[n][k] =  binomial(n - 1, k - 1) + binomial(n - 1, k)

  return cache[n][k]

n = 5
output = []
cache = [[None for _ in range(n + 1)] for _ in range(n + 1)]

for i in range(n):
  result = []

  for j in range(i + 1):
    result.append(binomial(i, j))

  output.append(result)

print(output)

function binomial(n, k) {
  if (n < 0 || n < k) {
    return 0;
  }

  if (k === 0 || k === n) {
    return 1;
  }

  if (cache[n][k] == null) {
    cache[n][k] = binomial(n - 1, k - 1) + binomial(n - 1, k);
  }

  return cache[n][k];
}

const n = 5;
const output = [];
const cache = Array.from(Array(n + 1), () => Array(n + 1).fill(null));

for(let i = 0; i < n; i++) {
  let result = [];

  for (let j = 0; j <= i; j++) {
    result.push(binomial(i, j));
  }

  output.push(result);
}

console.log(output);