Module P-11·12 min read

What dynamic programming actually is — memoization, tabulation, and the space/time trade-off, built from Fibonacci up.

Written by Jatin Jain Saraf · Architect of SupraScan

Module P-11 — Dynamic Programming I: Memoization and Tabulation

What this module covers: Module P-1 flagged naive recursive Fibonacci's O(2ⁿ) blowup and promised a fix — this module delivers it. Dynamic programming is the systematic version of Module F-4's "remember what you've seen" idea, applied to overlapping recursive subproblems instead of array elements. This module covers both directions of the same idea — memoization (top-down) and tabulation (bottom-up) — using the exact same recursive structure each time, just changing how results get stored and reused.

Where the Waste Comes From

Recall Module P-1's naive Fibonacci: every call branches into two further calls, and those calls overlap heavily.

function fibNaive(n: number): number {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2);
}

fibNaive(5) calls fibNaive(4) and fibNaive(3) — but fibNaive(4) also independently calls fibNaive(3), recomputing an entire subtree of work that was already computed moments earlier, just in a different branch of the call tree. This is the defining feature of a dynamic programming problem: overlapping subproblems — the same smaller input recurs many times across different branches of the recursion.

Memoization: Remember, Then Check Before Recomputing

The fix is the identical idea from Module F-4's Two Sum: before doing the expensive work, check a hash map to see if you've already computed this exact result.

function fibMemo(n: number, cache: Map<number, number> = new Map()): number {
  if (n <= 1) return n;
  if (cache.has(n)) return cache.get(n)!; // already computed — O(1) lookup, no recursion needed
 
  const result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
  cache.set(n, result); // remember it, so future calls (in any branch) skip straight to this line
  return result;
}

The recursive structure is completely unchanged from fibNaive — same base case, same recursive case. The only addition is cache: check it first, and populate it before returning. This single change collapses the complexity from O(2ⁿ) to O(n) — each distinct value of n is now computed exactly once, ever, no matter how many different branches of the original recursion would have asked for it. This is called top-down dynamic programming: you still start from the original question (fib(n)) and recurse downward toward the base case, same as before — you've just added a memory so no subproblem gets solved twice.

Tabulation: Build the Answer Bottom-Up, No Recursion at All

Tabulation solves the same overlapping-subproblems issue from the opposite direction: instead of starting at n and recursing down to the base cases, start at the base cases and iteratively build up to n, filling a table (usually just an array) as you go.

function fibTabulation(n: number): number {
  if (n <= 1) return n;
 
  const table = new Array(n + 1);
  table[0] = 0;
  table[1] = 1;
 
  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2]; // build each answer from already-computed smaller answers
  }
 
  return table[n];
}

Same O(n) time as the memoized version, but with two practical differences worth naming: no recursion at all, so no call stack depth to worry about (Module P-1's O(n) stack-space concern simply doesn't apply here — this is a for loop), and the order of computation is explicit and iterative rather than following the shape of a call tree.

Climbing Stairs: The Same Three-Step Progression, Applied Fresh

"How many distinct ways can you climb n stairs, taking either 1 or 2 steps at a time?" — worth walking through the identical naive → memoized → tabulated progression on a different problem, to see that this isn't a Fibonacci-specific trick.

// Naive — O(2^n). Reaching step n means you arrived from step n-1 or step n-2.
function climbStairsNaive(n: number): number {
  if (n <= 2) return n; // 1 way to reach step 1; 2 ways to reach step 2 (1+1, or 2)
  return climbStairsNaive(n - 1) + climbStairsNaive(n - 2);
}
 
// Memoized — O(n). Identical recursive structure, plus a cache.
function climbStairsMemo(n: number, cache: Map<number, number> = new Map()): number {
  if (n <= 2) return n;
  if (cache.has(n)) return cache.get(n)!;
  const result = climbStairsMemo(n - 1, cache) + climbStairsMemo(n - 2, cache);
  cache.set(n, result);
  return result;
}
 
// Tabulated — O(n), no recursion.
function climbStairsTabulation(n: number): number {
  if (n <= 2) return n;
  const table = new Array(n + 1);
  table[1] = 1;
  table[2] = 2;
  for (let i = 3; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }
  return table[n];
}

function fibConstantSpace(n: number): number {
  if (n <= 1) return n;
 
  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
 
  return prev1;
}