Pitfalls while memoization

As practicing dynamic programming, I was implementing a function that returns the binomial coefficient nCr given n and r.

Naive formula:

function binomial_naive(n, r) { if (n < 0 || r < 0 || r > n) { return 0; } if (r === 0 || r === n) { return 1; } return binomial_naive(n-1, r-1) + binomial_naive(n-1, r); } 

We can memoize this function to get O(r(n-r)) running time.

I was using Map<number, Map<number, number>>s but encountered a problem.

My initial memoization implementation had cache updating code and cache retrieval code interleaved, which made subtle bugs that only occurs only when some cache is computed.

I threw it away and coded a more straightforward implementation:

const cache = new Map(); function binomial(n, r) { if (!cache.has(n)) { cache.set(n, new Map()); } if (!cache.get(n).has(r)) { cache.get(n).set(r, binomial_naive(n, r)); } return cache.get(n).get(r); } function binomial_naive(n, r) { if (n < 0 || r < 0 || r > n) { return 0; } if (r === 0 || r === n) { return 1; } return binomial(n - 1, r) + binomial(n - 1, r - 1); } 

Now I see that we could implement this using 2d arrays which makes it a little more straightforward.