Dynamic programming
Suppose a friend asks you to add up 17 + 24. A minute later they ask
again — 17 + 24. You wouldn't count it out a second time; you'd just
say "still 41". Redoing work you've already done is wasteful, and a surprising number of
algorithms do exactly that: they solve the same little sub-problem over and over without noticing.
Dynamic programming (DP) is the technique of spotting this waste and stamping it
out. The recipe has two parts:
- break a problem into overlapping sub-problems — smaller versions of the same
problem that keep reappearing;
- solve each distinct sub-problem only once and store its answer,
so every later time you need it you just look it up instead of recomputing it.
Both of those parts matter. The magic only works when the sub-problems overlap — when the
same sub-answer is wanted again and again. That's what makes remembering pay off. This page builds
the whole idea on one perfect example: the Fibonacci sequence.
The name is a bit of a historical accident. In the 1950s the mathematician Richard Bellman needed a
title for this method that sounded impressive to a research-funding boss who disliked mathematics —
so he chose "dynamic programming" precisely because it was hard to object to. Here "programming"
means planning a schedule (as in a TV programme), not writing code.
The problem: Fibonacci redoes everything
In the Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, 13, \dots each term is the
sum of the two before it. Written as a recurrence, that is beautifully simple:
F(n) = F(n-1) + F(n-2), \qquad F(0) = 0,\;\; F(1) = 1.
The recurrence translates straight into a recursive function. But there's a hidden monster. Because
each call makes two more calls, the number of calls explodes. Let's prove it by
adding a counter and printing how many times the function actually runs. Press Run,
then try bumping N up towards 35 and watch the call count rocket.
let calls = 0;
function fib(n: number): number {
calls++; // count every single call
if (n < 2) return n; // base cases: fib(0)=0, fib(1)=1
return fib(n - 1) + fib(n - 2); // two recursive calls
}
const N = 30;
const answer = fib(N);
console.log("fib(" + N + ") =", answer);
console.log("...but it took", calls, "function calls to get there!");
Over a million calls just to find the 30th Fibonacci number. The work roughly doubles for
every extra step — that's exponential time. Something is badly wrong, and to see
what, we need to look at the shape of all those calls.
Seeing the waste: the call tree
Every call to fib splits into two smaller calls, which split again, forming a
call tree. Here is the tree for \text{fib}(5). Step
through it and watch the highlights: the same sub-problems appear again and again in
different branches.
\text{fib}(3) is computed twice,
\text{fib}(2) three times,
\text{fib}(1) five times — and each repeat drags its
whole subtree along with it. The tree is fat with duplicated work. These are exactly the
overlapping sub-problems DP is built to exploit: there are really only
n + 1 different Fibonacci values to find, so why compute any of
them more than once?
Cure #1 — Memoisation (top-down)
Memoisation keeps the natural recursion but gives it a memory. Before working out
\text{fib}(n) we check a cache: if we've already solved
this n, return the stored answer instantly; otherwise compute it once,
store it, and return it. The first branch to reach a value pays for it; every other branch
gets it free. It's called top-down because we still start at the big problem and let the
recursion dig downward.
Let's run the naive and memoised versions side by side, each counting its own calls, so the
difference is impossible to miss:
// --- naive: no memory, redoes everything ---
let naiveCalls = 0;
function fibNaive(n: number): number {
naiveCalls++;
if (n < 2) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}
// --- memoised: remembers each answer the first time ---
let memoCalls = 0;
const cache = new Map<number, number>();
function fibMemo(n: number): number {
memoCalls++;
if (n < 2) return n;
if (cache.has(n)) return cache.get(n)!; // seen before → look it up, no recursion
const result = fibMemo(n - 1) + fibMemo(n - 2);
cache.set(n, result); // remember it for next time
return result;
}
const N = 30;
console.log("fibNaive(" + N + ") =", fibNaive(N), "in", naiveCalls, "calls");
console.log("fibMemo(" + N + ") =", fibMemo(N), "in", memoCalls, "calls");
console.log("Memoising made about",
Math.round(naiveCalls / memoCalls), "times fewer calls.");
Same answer, but the memoised version makes only about 2n calls instead
of over a million. Each of the n + 1 distinct sub-problems is now solved
exactly once — we've turned exponential time into linear time just
by refusing to forget.
Cure #2 — Tabulation (bottom-up)
Memoisation works down from the top. Tabulation flips it around: start from the
smallest sub-problems and build a table upward, so that by the time you
need an answer it's already sitting there. No recursion at all — just a loop filling a list, each
entry built from the two before it.
function fibTable(n: number): number {
if (n < 2) return n;
const table: number[] = [0, 1]; // the two base cases
for (let i = 2; i <= n; i++) {
table[i] = table[i - 1] + table[i - 2]; // build each answer from earlier ones
}
return table[n];
}
for (let i = 0; i <= 10; i++) {
console.log("fibTable(" + i + ") =", fibTable(i));
}
We fill the table left to right: [\,0, 1, 1, 2, 3, 5, 8, \dots\,]. Each
cell is computed once from cells already known, so this is linear time too. Memoisation and
tabulation are the two faces of dynamic programming — same insight (solve each sub-problem
once), approached from opposite ends.
For Fibonacci, no! To build the next number we only ever look back two steps, so
we can throw the rest away and keep just two running values. This drops the memory from
n cells down to a constant, and is a common finishing touch on a DP
solution — shrinking the table to only the slice you still need:
function fibRolling(n: number): number {
let prev = 0, curr = 1; // fib(0) and fib(1)
for (let i = 0; i < n; i++) {
[prev, curr] = [curr, prev + curr]; // slide the window forward one step
}
return prev;
}
console.log("fib(40) =", fibRolling(40));
A problem is a candidate for dynamic programming when it has both of these properties:
- Overlapping sub-problems — solving it involves the same smaller sub-problems
many times over (as \text{fib}(3) and
\text{fib}(2) reappear across the call tree). This is what caching
can exploit.
- Optimal substructure — the answer to the whole is built directly from the
answers to its sub-problems (here F(n) is literally
F(n-1) + F(n-2)), so storing sub-answers is enough to reconstruct the
full one.
Dynamic programming only helps when the sub-problems genuinely overlap — when the
same sub-answers are asked for again and again. If every sub-problem you generate is
different, there is nothing to look up: the cache fills with entries that are each used
exactly once, and you've paid extra time and memory to store answers you never reuse.
That's the situation ordinary divide-and-conquer is built for. Merge sort, for
example, splits a list into two distinct halves that share no sub-work — so bolting a
cache onto it would be pure overhead, and plain divide-and-conquer is the right tool. Remember the
core trade DP makes: it spends memory to buy speed. That bargain is only worth
taking when the same work would otherwise be repeated.
They compute the same thing, so it's mostly a matter of fit:
- Memoisation keeps your code looking like the recurrence, and only ever
computes the sub-problems you actually need. Its weakness is that deep recursion can pile up the
call stack.
- Tabulation uses a simple loop (no recursion, no stack limit) and often lets
you shrink the stored table, but you must work out a safe order to fill it in — every
cell's dependencies have to be ready before it.
In an exam, either earns the marks; just be clear about which one you're describing.