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.
Top comments (0)