Dynamic programming & advanced problems

The cost of recomputing Two styles, three dives Advanced: when DP applies

Dynamic programming is the move you reach for when a problem breaks into overlapping subproblems: solve each one once, remember the answer, and reuse it. Two styles do this — memoisation caches a recursion top-down, tabulation fills a table bottom-up. The Portal leans on both wherever it would otherwise recompute the same thing: the depth of a prerequisite chain, the fewest modules to reach a credit target, the closest catalog entry to a misspelled search.

A bottom-up table makes the idea concrete: each cell f[i] is a stored subproblem, computed once from cells already filled to its left, then read back instead of recomputed. The figure fills a Fibonacci memo table cell by cell, drawing the two dependencies into each new entry.

A memo table fills left to right

f[i] = f[i-1] + f[i-2]
Base cases f[0]=0, f[1]=1 are filled. Fill the next cell from the two to its left.

The cost of recomputing

A learner works through a track of n lessons, taking one or two per session. The number of distinct pacings follows ways(n) = ways(n-1) + ways(n-2) — the same overlapping recurrence as Fibonacci. Computed naively it re-derives the lower terms over and over; computed with a cache it touches each once. Pick a length to compare the work.

Track length · select one

naive calls: 9

cached subproblems: 5

The answer is the same either way; the cost is not. Naive recursion pays for every repeat of a subproblem, and the repeats grow exponentially. Solving each subproblem once turns that into one evaluation per lesson.

Two styles, three dives

The two ways to solve-each-once, and a classic problem worked end to end — each a deep dive.

F4.11.1 · prerequisite depth

Memoization & overlapping subproblems

Top-down: compute the longest prerequisite chain to a lesson recursively and cache each lesson’s depth, so a shared prerequisite is evaluated once instead of along every path that reaches it.

F4.11.2 · the credit target

Tabulation & bottom-up

Bottom-up: fill a table of the fewest modules to reach each credit total from zero upward, so the answer for the target reads off a row built from smaller answers — where greedy choice fails, the table is optimal.

F4.11.3 · typo-tolerant search

Classic DP problems

Edit distance, the textbook two-dimensional DP, put to work: how many single-character edits turn a misspelled query into a catalog title, filled cell by cell to power a “did you mean” suggestion.

Advanced: when DP applies

Dynamic programming earns its keep under two conditions. The problem has optimal substructure — an optimal answer is built from optimal answers to subproblems — and those subproblems overlap, so a naive recursion solves the same ones repeatedly. Where both hold, solving each subproblem once and storing it turns exponential work into work proportional to the number of distinct subproblems. Where the subproblems do not overlap, plain divide-and-conquer is enough and a cache only adds overhead.

The two styles are the same idea from opposite ends. Memoisation keeps the natural recursion and adds a cache, so it is lazy — it only ever evaluates the subproblems the answer actually needs — at the cost of recursion depth and a map lookup per call. Tabulation rewrites the recursion as a loop that fills a table from the smallest subproblem up, so it is eager and iterative, usually with better constant factors and no deep stack, at the cost of computing every cell whether the answer needs it or not. The cache, in both, is one of the maps from earlier in this chapter.

# the same recurrence, both ways — pacings of an n-lesson track
def memo(n, cache \\ %{}) do                 # top-down: recurse + cache
  case cache do
    %{^n => v} -> {v, cache}
    _ when n <= 2 -> {n, cache}
    _ ->
      {a, c1} = memo(n - 1, cache)
      {b, c2} = memo(n - 2, c1)
      {a + b, Map.put(c2, n, a + b)}
  end
end

def tab(n) do                              # bottom-up: fill a table
  Enum.reduce(3..n//1, %{1 => 1, 2 => 2}, fn i, t ->
    Map.put(t, i, t[i - 1] + t[i - 2])
  end)[n]
end

overlapping subproblems

The same smaller answers, needed again and again.

solve each once

Cache a recursion or fill a table; exponential work becomes one pass over the subproblems.

Start with memoisation, then tabulation, then a classic problem. Predecessor: F4.10 — Practical recipes in Elixir. Next module: F4.12 — Lab: build a branded CHAMP store, which closes the chapter.

References

Primary sources for this lesson, and where it connects in the course.

Sources

Dynamic programming — Wikipedia — optimal substructure and overlapping subproblems.
Memoization — Wikipedia — caching a recursion top-down.
Elixir — Map — the cache and the table are maps.

Related in this course

F4.10 · Practical recipes in Elixir — the idioms these solutions are written in.
F4.04 · Maps, sets & hashing — the map behind the cache.
F4 · Algorithms & Data Structures