Find Binomial coefficient (Memoization)

A binomial coefficient, n choose k formula, is also known as combinations formula, and is defined as

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Binomial coefficient, 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:
    cache = [[None for _ in range(k + 1)] for _ in range(n + 1)]

  if not cache[n][k]:
    cache[n][k] = (float(n) / k) * binomial(n - 1, k - 1)

  return cache[n][k]

n = 10
k = 5

print(binomial(n, k))

let cache = null;

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

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

  if (cache == null) {
    cache = [];

    for (let i = 0; i < n + 1; i++) {
      cache[i] = [];
    }
  }

  if (cache[n][k] === undefined) {
    cache[n][k] = (n / k) * binomial(n - 1, k - 1);
  }

  return cache[n][k]
}

const n = 10;
const k = 5;

console.log(binomial(n, k));