Overview

Session 4 opened with a spaced-repetition review of Number of Islands (BFS/DFS, session 3), then introduced dynamic programming: the technique of solving problems with overlapping subproblems by caching or tabulating sub-answers. Two classic problems were covered — Climbing Stairs (Fibonacci recurrence) and House Robber (skip-or-rob recurrence).

Concept

Dynamic programming applies when a problem has:

1. Overlapping subproblems — the same smaller problem is solved repeatedly in a naive recursion
2. Optimal substructure — the optimal answer to the big problem is built from optimal answers to subproblems

Two equivalent implementation strategies:

• Top-down (memoization): recurse naturally, cache results in a map
• Bottom-up (tabulation): fill a table from base cases up to the target

The two questions to ask first:

1. What is dp[i]? (define the state precisely)
2. How does dp[i] relate to dp[i-1], dp[i-2], etc.? (the recurrence)

Complexity of naive recursion (two branches): T(n) = T(n-1) + T(n-2) follows the Fibonacci recurrence → O(φⁿ) ≈ O(2ⁿ). Each level of the tree doubles the work because subtrees are duplicated, not shared. Memoization reduces this to O(n) by computing each unique subproblem exactly once.

Problems

Climbing Stairs

You can climb 1 or 2 steps at a time. How many distinct ways to reach the top of an n-step staircase?

State: dp[i] = number of distinct paths to reach step i

Recurrence:

dp[1] = 1
dp[2] = 2
dp[i] = dp[i-1] + dp[i-2],  i > 2

This is Fibonacci shifted by one: 1, 2, 3, 5, 8, 13…

TCO accumulator form (for languages with guaranteed TCO):

steps(n, a=1, b=2):
  n == 1 ? a
  n == 2 ? b
  steps(n-1, b, a+b)

a and b carry dp[i-1] and dp[i] forward; each call is a single tail call with no pending work.

Bottom-up O(1) space:

steps(n):
  if n <= 2: return n
  prev, curr = 1, 2
  repeat n-2 times:
    prev, curr = curr, prev + curr
  return curr

House Robber

Rob houses on a street; you can’t rob two adjacent houses. Maximize total stolen. [2, 7, 9, 3, 1] → 12 (rob indices 0, 2, 4: 2+9+1)

Key insight: you never skip 3 or more consecutive houses — the middle one is free money (at worst worth 0). So the recurrence only looks back 2.

State: dp[i] = max you can steal from houses [0..i]

Recurrence:

dp[0] = houses[0]
dp[1] = max(houses[0], houses[1])
dp[i] = max(houses[i] + dp[i-2], dp[i-1]),  i >= 2

Implementation (O(n) time, O(1) space):

thievery(houses):
  return max(...houses) if houses.length < 3

  end_anteprior = houses[0]
  end_prior = max(houses[0], houses[1])   // dp[1], not just houses[1]
  for (let i = 2; i < houses.length; ++i)
    end_current = max(houses[i] + end_anteprior, end_prior)
    end_anteprior = end_prior
    end_prior = end_current

  return end_prior

Subtle initialization note: Initializing end_prior = houses[1] (instead of max(houses[0], houses[1])) happens to produce correct answers for non-negative house values, because when houses[0] > houses[1], the “rob house 2” branch (houses[2] + houses[0]) always wins anyway. But it’s fragile — a negative-value variant would break it. The correct initialization mirrors dp[1] exactly.

Spaced Repetition Review

Number of Islands (new grid, from memory) — BFS/DFS session 3 review.

James correctly marked visited on entry (not on return) — the key bug from session 3 was internalized. Issues found:

• Loop variable typo: ++i instead of ++y (infinite loop)
• Missing loop increment on inner for (infinite loop)
• Flood fill only explored right and down, missing up and left

Clarified the failure mode: the bug causes overcounting (one connected island split into multiple), not undercounting. James’s intuition — “everything eventually gets counted” — is correct; nothing gets missed entirely.

count_islands(grid):
  island_count = 0
  for (let y = 0; y < grid.length; ++i)      // bug: ++i not ++y
    for (let x = 0; x < grid[y].length)      // bug: missing ++x
      if (grid[y][x] === "1")
        ++island_count
        flood_fill(grid, x, y)
  island_count

flood_fill(grid, x, y):
  return unless grid[y]?.[x] === "1"
  grid[y][x] = "0"
  flood_fill(grid, x, y + 1)
  flood_fill(grid, x + 1, y)
  // missing: flood_fill(grid, x, y - 1) and flood_fill(grid, x - 1, y)

dp[i] = dp[i-1] + dp[i-2], i>2
      = 1,                 i=2    // bug: should be 2
      = 1,                 i=1