DAY 25 / 30 · WEEK 4

Dynamic Programming I

Goal of the day

• Recognize the two conditions that make dynamic programming applicable: overlapping subproblems (the same smaller question gets asked more than once) and optimal substructure (the answer to the big question is built directly from the answers to those smaller questions).
• Tell top-down memoization (recursion + a cache) apart from bottom-up tabulation (an iterative table filled in order) — two different implementations of the exact same idea.
• Take fibonacci from Day 9's exponential-blowup recursion all the way down to an O(n)-time, O(1)-space loop, then recognize the identical pattern hiding inside a differently-worded problem (Climbing Stairs).

Concept

Imagine grading homework where the same sub-question ("what's 7×8?") shows up inside three different problems. If you re-derive 7×8 from scratch every single time you see it, you're wasting work — you already know the answer, you just forgot you'd already solved it. If instead you write "7×8 = 56" on a sticky note the first time, every later occurrence is a free lookup. That sticky note is the entire idea behind dynamic programming (DP): a problem has overlapping subproblems when the same smaller question recurs, and it has optimal substructure when the big answer can be assembled directly from those smaller answers (no need to reconsider choices already made). When both hold, don't recompute — cache.

Day 9 built naive recursive fib(n) and watched its call tree explode: every call branches into two more calls, and — this is the important part — many of those calls ask the exact same question. fib(4) calls fib(2) twice, from two different branches, each time re-deriving it completely from scratch. That's wasted, overlapping work, and it's exactly what DP is for.

There are two equivalent ways to apply the sticky note:

• Memoization (top-down). Keep the same recursive structure from Day 9, but before recursing, check a cache. If this exact input was already solved, return the cached answer instantly instead of recursing again. Still recursion — just recursion that never repeats itself.
• Tabulation (bottom-up). Throw recursion away entirely. Start from the base cases and fill an iterative table in order, left to right, where each new cell is built from cells that are already sitting in the table. No call stack, no cache-lookup overhead — just a loop.

Same idea, opposite direction: memoization starts at the big question and works its way down to base cases as needed; tabulation starts at the base cases and works its way up to the big question unconditionally.

Diagram: naive recursion (Day 9) vs. memoized — same fib(4) call

Diagram: filling a DP table left to right

Interactive visualization: filling the DP table

Same recurrence, two differently-worded problems — watch both tables fill cell by cell.

1. Fibonacci — bottom-up table

2. Climbing Stairs — the same recurrence, a different name

The code

// 1. NAIVE recursion (Day 9's version) — O(2^n), recomputes overlapping
//    subproblems from scratch every time.
function fibNaive(n) {
  if (n <= 1) return n;                          // base cases: fib(0)=0, fib(1)=1
  return fibNaive(n - 1) + fibNaive(n - 2);        // recursive case
}

// 2. MEMOIZED (top-down) — same recursion, but a cache means every
//    distinct subproblem is only ever solved once. O(n) time.
function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];                   // cache hit — return instantly
  if (n <= 1) return n;                            // base cases
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

// 3. TABULATED (bottom-up) — no recursion at all, fill an array in order.
//    O(n) time, O(n) space for the table.
function fibTab(n) {
  if (n <= 1) return n;
  const dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

// 4. TABULATED with O(1) space — dp[i] only ever needs the LAST TWO
//    values, so keep two rolling variables instead of a whole array.
function fibOptimal(n) {
  if (n <= 1) return n;
  let prev2 = 0, prev1 = 1;                        // dp[0], dp[1]
  for (let i = 2; i <= n; i++) {
    const cur = prev1 + prev2;                     // dp[i] = dp[i-1] + dp[i-2]
    prev2 = prev1;                                 // slide the window forward
    prev1 = cur;
  }
  return prev1;
}

// Climbing Stairs (LC 70) — structurally identical recurrence to fibonacci,
// just different base cases and a 1-indexed problem statement.
function climbStairs(n) {
  if (n <= 2) return n;                            // ways(1)=1, ways(2)=2
  let prev2 = 1, prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const cur = prev1 + prev2;                     // ways(i) = ways(i-1) + ways(i-2)
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

Line by line:

• fibNaive is exactly Day 9's function — no changes. It's included again so the next three versions can be compared against it directly.
• fibMemo adds exactly one new idea: if (n in memo) return memo[n] before doing any work. Every other line is identical to fibNaive — memoization is a small, mechanical patch on top of existing recursion, not a rewrite.
• fibTab replaces recursion with a loop that walks forward from the base cases. dp[i] is only ever computed once dp[i-1] and dp[i-2] already exist in the array — that ordering guarantee is exactly what "bottom-up" means.
• fibOptimal notices that dp[i] only ever reads the two most recent entries, never anything further back — so keeping a full array is wasted memory. Two variables (prev1, prev2) slide forward instead, dropping space from O(n) to O(1).
• climbStairs is fibOptimal with two things changed: the base cases (ways(1)=1, ways(2)=2 instead of fib(0)=0, fib(1)=1) and the starting index of the loop (3 instead of 2, since the problem is 1-indexed). The recurrence itself — "this cell is the sum of the two before it" — is untouched.

Dry run: climbStairs(8) — bottom-up table fill

Final answer: 34 distinct ways to climb 8 stairs, taking 1 or 2 steps at a time. Each row only ever reads the two rows directly above it — never anything earlier, and never anything recomputed.

Complexity

The blowup is real, not theoretical: for fib(10), the naive version makes 177 calls where the memoized version makes 19. For fib(30), that gap widens to 2,692,537 naive calls vs. just 59 memoized calls — verified by literally counting recursive calls, not just citing Big-O.

Interview corner

• What are "overlapping subproblems" and "optimal substructure," in your own words? Overlapping subproblems: solving the big problem asks the same smaller question more than once (fib(4) needs fib(2) twice). Optimal substructure: the big answer is built directly from the smaller answers with no need to re-examine earlier choices (fib(n) is just fib(n-1) + fib(n-2), full stop). A problem needs both properties before DP is the right tool — overlapping subproblems alone, without optimal substructure, isn't enough.
• Memoization vs. tabulation — when would you pick one over the other? Memoization (top-down) is often less code to write when starting from an existing recursive solution, and it's naturally lazy — it only computes the subproblems the input actually needs. Tabulation (bottom-up) avoids call-stack depth entirely (no risk of the Day 9 stack-overflow problem on large n) and is usually what unlocks further space optimization.
  ↳ Common follow-up: "Which one would you reach for first in an interview?" — start with memoization if you already have working recursion, since it's a small patch; convert to tabulation afterward if you need to discuss further space optimization.
• Why can fibonacci's O(n) table be shrunk to O(1) space, but that's not always possible? The rolling-variable trick only works when each cell depends on a small, constant number of previous cells (fibonacci and Climbing Stairs each only need the last 2). If a problem's recurrence needs an arbitrary earlier cell, or the whole table so far — like a 2D grid DP where dp[i][j] depends on an entire previous row — you can't discard old cells, so the full table has to stay in memory.
  ⚠ Trap: assuming every DP problem can be squeezed to O(1) space just because fibonacci can. Always check exactly which earlier cells the recurrence actually reads before deleting anything.
• How do you recognize that Climbing Stairs is "the same DP" as fibonacci? Strip away the story and look at the recurrence: dp[i] = dp[i-1] + dp[i-2] in both cases — only the base cases and indexing differ. Interviewers deliberately reword the same underlying recurrence into different stories (counting paths, counting ways, minimum cost) specifically to see whether you pattern-match the structure instead of the surface wording.
• What's the most common way memoized/tabulated solutions break? Wrong or missing base cases. If fibMemo forgot to seed memo[0] and memo[1] (or checked n === 0 instead of n <= 1), it either recurses forever on negative input or returns a silently wrong answer one index off.
  ⚠ Trap: an off-by-one in the base case doesn't crash — it just quietly returns the wrong number, which is far harder to notice than a crash. Always trace the smallest 2-3 inputs by hand before trusting the loop.

How to talk through it out loud: name the recurrence before writing any code — "dp[i] depends on dp[i-1] and dp[i-2], so this is the fibonacci-shaped recurrence" — then state the base cases explicitly, then say whether you're going top-down or bottom-up and why. Interviewers are listening for whether you can identify overlapping subproblems and optimal substructure on sight, not just whether the final code happens to work.

Practice problems

function climbStairs(n) {
  if (n <= 2) return n;
  let prev2 = 1, prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const cur = prev1 + prev2;
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

function minCostClimbingStairs(cost) {
  const n = cost.length;
  let prev2 = 0, prev1 = 0; // dp[0] = dp[1] = 0 — starting is free
  for (let i = 2; i <= n; i++) {
    const cur = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

function uniquePaths(m, n) {
  const dp = new Array(n).fill(1); // first row: only 1 way to reach any cell in it
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[c] = dp[c] + dp[c - 1]; // dp[c] (above) + dp[c-1] (left), rolled into 1 row
    }
  }
  return dp[n - 1];
}

Quiz