What is dynamic programming?
Dynamic programming solves a problem by breaking it into smaller subproblems and reusing
each subproblem's answer instead of recomputing it. The two things that make a problem a fit are
optimal substructure — the best answer is built from the best answers to smaller versions —
and overlapping subproblems — the same smaller question gets asked more than once.
- Subproblem
- A smaller version of the same question, like "how many ways to reach step 3?"
- Optimal substructure
- The best answer to the whole problem is built from the best answers to its subproblems
- Overlapping subproblems
- The same subproblem gets asked for more than once — caching it pays off
Why dynamic programming at all?
Picture climbing a staircase, one or two steps at a time. To count the ways to reach step 5, you ask "how many ways to reach step 4?" and "how many ways to reach step 3?" — but answering step 4 also asks about step 3 all over again.
Write each step's answer down the first time you compute it, and every later question about that step becomes a lookup instead of a recount.
Every step reuses the two answers right before it — never recounted.
What kinds of problems does it solve?
Four common shapes. The table changes — counts, running bests, costs, capacities — but each cell is always built from a small number of earlier cells.
Counting the number of ways
To reach step i, you either came from step i-1 or step i-2. The count
at i is just the sum of the counts already sitting at those two earlier steps.
Each new cell adds the two cells directly behind it.
Choosing to include or skip
At each house, either rob it and add its value to the best total two houses back, or skip it and keep the best total from the house right before. Take whichever is bigger.
Every house is a small decision built on two cached answers.
Minimizing a running cost
The cheapest way to reach step i is its own cost plus whichever of the two steps
before it was cheaper to reach. Track the running minimum instead of every possible path.
Cheaper of two cached paths, plus the cost of landing here.
Building up to a target
The fewest coins for amount i is one coin plus the fewest coins already found for
i minus that coin's value — tried for every coin, keeping the smallest result.
Every amount reuses the fewest-coins answer for a smaller amount.
Two types
The subproblems are the same either way. What changes is the order you fill them in — pulled on demand from the top, or built up methodically from the bottom.
Top-down (memoization)
Write the natural recursive solution, then cache each subproblem's answer the first time it's computed. Later calls for the same subproblem return the cached value instantly instead of recursing again.
Only computed the first time it's asked for — every repeat is a cache hit.
function fib(n: number, cache: Map = new Map()): number {
if (n <= 1) return n;
if (cache.has(n)) return cache.get(n)!; // already solved, skip the recursion
const result = fib(n - 1, cache) + fib(n - 2, cache);
cache.set(n, result); // write it down once
return result;
}
Bottom-up (tabulation)
Build a table from the smallest subproblems up to the full answer, no recursion needed. Every cell is filled exactly once, strictly in order, using only cells already sitting to its left.
One pass, left to right — every cell built before it's needed.
function fib(n: number): number {
if (n <= 1) return n;
const table = new Array(n + 1);
table[0] = 0;
table[1] = 1;
for (let i = 2; i <= n; i++) {
table[i] = table[i - 1] + table[i - 2]; // built from cells already filled
}
return table[n];
}
Where it works — and where it breaks
Dynamic programming leans on a quiet assumption: the same subproblem actually gets asked for more than once. Break that assumption and the cache is just extra bookkeeping around a plain loop.
Works when subproblems overlap
Fibonacci-style recursion asks for fib(2) over and over on the way to fib(5).
Caching it once turns an exponential number of calls into a handful of lookups.
Breaks when nothing repeats
Summing an array only ever asks for each running total once, moving strictly forward. There's no subproblem to reuse, so a cache just holds values nobody asks for twice — plain iteration is already optimal.