Memoization - top-down vs. bottom-up

by Dawid Ryłko

HTML

<!-- Z góry na dół vs. z dołu do góry -->

<a href="https://dawidrylko.com/memoizacja-harry-potter-i-myslodsiewnia/" target="_blank">Z góry na dół vs. z dołu do góry</a>

TypeScript

const fibTopDown = (n: number, memo: Record<number, number> = {}): number => {
  if (n in memo) return memo[n];
  if (n < 2) return n;

  memo[n] = fibTopDown(n - 1, memo) + fibTopDown(n - 2, memo);
  return memo[n];
};

console.log(`Top-down fib(10): ${fibTopDown(10)}`);

const fibBottomUp = (n: number): number => {
  if (n < 2) return n;

  const table = [0, 1];

  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }

  return table[n];
};

console.log(`Bottom-up fib(10): ${fibBottomUp(10)}`);