Day 25: Dynamic Programming I

DAY 25 / 30 · WEEK 4

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. Tracing that call tree by hand: naive fib(4) makes 9 total calls, and the fib(2) subtree gets fully re-expanded both times it’s reached. A memoized version of the exact same call makes only 7 calls — the second fib(2) hits a cache and returns instantly instead of re-expanding into fib(1) and fib(0) again. 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: filling a DP table left to right

Same recurrence, two differently-worded problems — watch both tables fill cell by cell. Green cells are filled and confirmed, blue cells are the source cells being read for the current computation, and purple is the cell being computed right now.

filled / confirmedsource cell being readcell being computed now

1. Fibonacci — bottom-up table

Press Play or Step to begin.

Step 0 / 0

▶ Play⏭ Step↺ Reset🔀 Shuffle

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

Press Play or Step to begin.

Step 0 / 0

▶ Play⏭ Step↺ Reset🔀 Shuffle

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

i	dp[i-1]	dp[i-2]	dp[i] = dp[i-1] + dp[i-2]
1 (base)	—	—	dp[1] = 1 (one way: a single step)
2 (base)	—	—	dp[2] = 2 (two ways: 1+1, or 2)
3	dp[2] = 2	dp[1] = 1	dp[3] = 2 + 1 = 3
4	dp[3] = 3	dp[2] = 2	dp[4] = 3 + 2 = 5
5	dp[4] = 5	dp[3] = 3	dp[5] = 5 + 3 = 8
6	dp[5] = 8	dp[4] = 5	dp[6] = 8 + 5 = 13
7	dp[6] = 13	dp[5] = 8	dp[7] = 13 + 8 = 21
8	dp[7] = 21	dp[6] = 13	dp[8] = 21 + 13 = 34

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

Approach	Time	Space	Why
Naive recursive	O(2^n)	O(n)	Every call branches into 2 more calls with no cache, so the call count roughly doubles per level of depth. Space is O(n) for the call stack (deepest chain of waiting frames), not the exponential call count itself.
Memoized (top-down)	O(n)	O(n)	Each of the n distinct subproblems (fib(0) through fib(n)) is computed exactly once and then cached; every later call for the same n is an O(1) lookup. Space is the cache (n entries) plus the O(n) call stack.
Tabulated (bottom-up)	O(n)	O(n)	A single loop from 0 to n, one O(1) step per cell — no recursion, no call stack, but the full table is kept, so space is still O(n).
Tabulated, rolling variables	O(n)	O(1)	Identical loop, but only the last 2 values are ever read, so 2 variables replace the whole array — the same optimization applied to climbStairs above.

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

1. Climbing Stairs — Easy

LeetCode: Climbing Stairs

You’re climbing a staircase with n steps. Each move you can climb 1 or 2 steps. Return the number of distinct ways to reach the top. Today’s second worked example — the code above is the real solution.

Hint

Write out ways(1), ways(2), ways(3) by hand before coding — you’ll notice ways(3) = ways(2) + ways(1) immediately. That’s the whole recurrence; today’s fibonacci pattern applies directly, just with different base cases.

Show solution

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;
}

2. Min Cost Climbing Stairs — Easy

LeetCode: Min Cost Climbing Stairs

Each stair i has a cost cost[i] to step on it. You may start from step 0 or step 1, and from a step you can climb 1 or 2 steps. Return the minimum total cost to reach the top (one step past the last index).

Hint

Same shape as Climbing Stairs, but now each cell holds a minimum cost instead of a count, and it’s a min of 2 options instead of a sum: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). dp[0] and dp[1] are both 0 — reaching the starting step itself is free.

Show solution

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;
}

3. Unique Paths — Medium

LeetCode: Unique Paths

A robot sits at the top-left corner of an m x n grid and can only move right or down. Return the number of distinct paths to the bottom-right corner. Same idea as today’s 1D recurrences, stretched to 2 dimensions — a preview of the grid DP shapes coming up on Day 26.

Hint

The number of ways to reach any cell is the sum of the ways to reach the cell above it and the cell to its left: dp[r][c] = dp[r-1][c] + dp[r][c-1]. The entire first row and first column are base cases (only 1 way to reach them — straight line, no choices).

Show solution

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

Quiz: 1. What two properties must a problem have for dynamic programming to apply?

Overlapping subproblems AND optimal substructure

DP applies when both hold: overlapping subproblems (the same smaller question recurs) AND optimal substructure (the big answer is built directly from those smaller answers). Overlapping subproblems alone just means you’re repeating work — DP needs the second property too, so the recurrence can actually assemble a correct answer.

Quiz: 2. What’s the one core change memoization makes to naive recursion?

Check a cache before recursing; store the answer after computing it

Memoization keeps Day 9’s exact recursive structure and adds one new idea: check a cache before recursing, and store the result after computing it. It’s a small patch on top of existing recursion, not a rewrite into a loop.

Quiz: 3. What’s the time complexity of naive recursive fib(n), with no memoization?

O(2^n)

Naive recursive fibonacci is O(2^n) — every call branches into 2 more with nothing cached, so the call count grows exponentially with n (177 calls for fib(10), 2,692,537 for fib(30)). Memoized and tabulated versions are both O(n).

Quiz: 4. When can a tabulated DP be optimized from O(n) space down to O(1) with rolling variables?

Only when each cell depends on a small, constant number of earlier cells

The O(1)-space rolling-variable trick only works when each cell depends on a small, constant number of previous cells (fibonacci and Climbing Stairs each need just the last 2). If a recurrence needs an arbitrary earlier cell or a whole previous row (common in 2D grid DP), the full table has to be kept.

Quiz: 5. Why is Climbing Stairs considered “the same DP” as fibonacci?

Both share the identical recurrence dp[i] = dp[i-1] + dp[i-2] — only base cases differ

Strip the story away and both have the identical recurrence dp[i] = dp[i-1] + dp[i-2] — only the base cases and indexing differ (fib(0)=0/fib(1)=1 vs. ways(1)=1/ways(2)=2). Recognizing the same recurrence under different wording is the actual skill being tested.