DSAMonth 4 · Week 13

Day 63: Dynamic Programming: Top-Down vs Bottom-Up Basics

Recognize overlapping subproblems and optimal substructure, then implement the same solution both top-down (memoized recursion) and bottom-up (tabulation).

Mark this day complete

Study

Concepts

The two ingredients DP requires

Dynamic Programming applies when a problem has OVERLAPPING SUBPROBLEMS (naive recursion recomputes the same smaller inputs repeatedly — Fibonacci(30) recomputes Fibonacci(28) many times over) AND OPTIMAL SUBSTRUCTURE (the optimal answer to the whole problem can be built from optimal answers to its subproblems). If either is missing, DP does not apply — recognizing this quickly is itself an interview skill (do not force-fit DP onto a problem that is really just a greedy or two-pointer problem).

Top-down (memoization): write the natural recursive solution first, then cache each unique input's result in a Map/array so repeat calls return instantly instead of recomputing. Bottom-up (tabulation): build the answer iteratively from the smallest subproblems upward, filling a table until you reach the final answer — no recursion, no call stack risk, and often easier to further optimize (e.g. collapsing a 2D table to a rolling 1D array once you see which previous rows are actually needed).

See It

Visualizations

Visualization

Top-down (memoization) vs bottom-up (tabulation)

	Top-down	Bottom-up
Starting point	The natural recursive solution	The smallest subproblems
Direction	Big problem → breaks into small ones, cached	Small problems → build up to the big one
Call stack risk	Yes — deep recursion can overflow	No — pure iteration
Computes unnecessary subproblems?	No — only what recursion actually visits	Sometimes — fills the whole table by default
Easiest to write first	Usually yes — closest to the brute force	Usually written AFTER the top-down version is understood

Visualization

Naive Fibonacci recursion — the overlap DP eliminates

fib(2) is computed 2 separate times just for fib(4) — this blows up exponentially without memoization.

fib(4)

fib(3)

fib(2)

fib(1)

fib(2) ← recomputed from scratch!

Build It

Code Examples

Fibonacci: naive, top-down memoized, and bottom-up

// Naive: O(2^n) — recomputes the same subproblems exponentially
function fibNaive(n) {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2);
}

// Top-down: O(n) time, O(n) space (cache + call stack)
function fibMemo(n, cache = new Map()) {
  if (n <= 1) return n;
  if (cache.has(n)) return cache.get(n);
  const result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
  cache.set(n, result);
  return result;
}

// Bottom-up: O(n) time, O(1) space — only ever needs the last two values
function fibTabulation(n) {
  if (n <= 1) return n;
  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    [prev2, prev1] = [prev1, prev1 + prev2];
  }
  return prev1;
}

Climbing Stairs — the same top-down/bottom-up pair on a new problem

// "How many distinct ways to climb n stairs, taking 1 or 2 steps at a time?"
// Recognize: ways(n) = ways(n-1) + ways(n-2) — same shape as Fibonacci.

function climbStairsTopDown(n, cache = new Map()) {
  if (n <= 2) return n;
  if (cache.has(n)) return cache.get(n);
  const result = climbStairsTopDown(n - 1, cache) + climbStairsTopDown(n - 2, cache);
  cache.set(n, result);
  return result;
}

function climbStairsBottomUp(n) {
  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];
}

Remember

Key Takeaways

DP needs BOTH overlapping subproblems AND optimal substructure — verify both before reaching for it.
Top-down = natural recursion + a cache; usually the easiest first draft since it mirrors the brute-force solution.
Bottom-up = iterative table-filling from the base cases up; avoids call-stack risk and is often further space-optimizable.
A recurring signal you have a DP problem: the brute-force recursive solution's recursion tree visibly repeats the same sub-calls.
Once a bottom-up table's formula only depends on the last 1-2 rows/values, collapse it to O(1) space, as in the Fibonacci tabulation example.

Do It

Practice

1Write the naive, top-down, and bottom-up versions of "House Robber" (max sum of non-adjacent array elements) and time all three on n=35.
2Convert a 2D bottom-up DP table (Unique Paths in a grid) into a space-optimized 1D rolling array version.
3Explain in writing, for one problem of your choice, exactly which two subproblems recur and why that justifies caching.