Fibonacci & Memoization

Dynamic Programming: Memoization

Dynamic programming (DP) solves problems by breaking them into overlapping subproblems and caching the results to avoid redundant computation.

Memoization is the top-down approach: write the recursive solution, then add a cache.

The Fibonacci Problem

The naive recursive Fibonacci is exponential:

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);  // O(2^n) calls!
}

For fib(50), this makes over 20 trillion function calls.

With Memoization

Cache the result of each fib(n) call so it is only computed once:

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

Now fib(50) makes only ~100 calls. Time complexity goes from O(2ⁿ) to O(n).

The Pattern

Memoization follows three steps:

1. Identify the base cases.
2. Check the cache before computing.
3. Store the result before returning.

This pattern applies to many problems: coin change, longest common subsequence, edit distance, 0/1 knapsack, and more.

Your Task

Implement fib(n) using memoization. fib(0) = 0, fib(1) = 1, fib(n) = fib(n-1) + fib(n-2).