Data structures & algorithms · Dynamic programming

Dynamic programming: the fixed method

One recursion, four ways to write it. This page takes climbing stairs from 15 calls down to 6 table cells, and shows you the exact repeated work that a cache deletes.

Watch the repeats pile up, then vanish →

Naive · 15 calls for 6 answers

→

Table · 6 cells, nothing repeated

01 The idea

The same answer, worked out over and over

A staircase has n steps. You can take 1 step or 2 steps at a time. How many different ways are there to reach the top? The recursion writes itself: the last move onto step n was either a 1-step from step n − 1 or a 2-step from step n − 2, so the number of ways to reach n is the number of ways to reach n − 1 plus the number of ways to reach n − 2. A rule like that, which builds one answer out of smaller answers of the same kind, is called a recurrence.

Write it as plain recursion and it works — and it is unusably slow. Not because the rule is wrong, but because the call tree asks for the same value again and again. For n = 5 it makes 15 calls to produce 6 distinct answers. Dynamic programming is the fix, and it is always the same fix: remember each answer the first time you work it out.

Write the recursion first. Then look at the call tree: if the same input appears more than once, store each answer the first time you compute it. That store is the whole of dynamic programming — a table you fill top-down or bottom-up, but the same table either way.

Overlapping subproblemsThe recursion asks for the same input more than once. climb(3) is needed by both climb(5) and climb(4). This is what makes storing answers pay off.

Optimal substructureThe answer for a problem is built only from answers to its subproblems, and nothing about the path taken to get there changes them. This is what makes the recurrence correct.

MemoisationKeeping a map from input to answer, checking it before you recurse, and writing to it after. It turns a recursion that recomputes into one that looks up.

02 Hand trace

climb(5): 15 calls for 6 answers

Run the plain recursion on n = 5 and count how often each value is asked for. Every box below is one call that runs the whole computation from scratch. The first box in a row is the call that genuinely had to happen; every rose box after it recomputes a number this run already worked out.

climb(5)8asked once — the question you were given

climb(4)5asked once

climb(3)33asked twice — the second rebuilds everything under it

climb(2)222three times

climb(1)11111five times

climb(0)111three times

Count the boxes: 1 + 1 + 2 + 3 + 5 + 3 = 15 calls, and only 6 of them are the first time that value has been seen. The other 9 are pure waste, and the waste grows fast — climb(10) makes 177 calls and climb(30) makes 2,692,537. Now fill the same six answers into a table instead, smallest first, and read what each new cell needs.

seed11––––dp[0] = 1 and dp[1] = 1 are known outright

i = 2112–––dp[2] = dp[1] + dp[0] = 1 + 1 = 2

i = 31123––dp[3] = dp[2] + dp[1] = 2 + 1 = 3

i = 411235–dp[4] = dp[3] + dp[2] = 3 + 2 = 5

i = 5112358dp[5] = 5 + 3 = 8 — climb(5) = 8

Six cells, four additions, and every cell is written exactly once. The answers are identical — 1, 1, 2, 3, 5, 8 — because the rule never changed. What changed is the order: the recursion works top-down and keeps asking for values it has not stored, while the table works bottom-up and every value it needs is already sitting to its left. That is the whole insight, and the code in section 03 is four ways of writing it down.

03 The four forms

One recursion, four ways to write it

This is the method, and it does not change from problem to problem. Write the recursion. Add a cache. Turn the cache into a table you fill in order. Then throw away the parts of the table you no longer read. Each step below is a small edit to the one before it, and every version returns the same 8 for n = 5.

Form 1 · plain recursion

function climb(n):    if n <= 1:        return 1    return climb(n - 1) + climb(n - 2)# climb(5) = 8, after 15 calls

Form 2 · memoisation, top-down

memo = empty mapfunction climb(n):    if n <= 1:        return 1    if n in memo:        return memo[n]    memo[n] = climb(n - 1) + climb(n - 2)    return memo[n]

Form 3 · tabulation, bottom-up

function climb(n):    if n <= 1:        return 1    dp = new array of size n + 1    dp[0] = 1    dp[1] = 1    for i from 2 to n:        dp[i] = dp[i - 1] + dp[i - 2]    return dp[n]

Form 4 · two rolling variables

function climb(n):    if n <= 1:        return 1    prev, curr = 1, 1   # dp[0], dp[1]    for i from 2 to n:        prev, curr = curr, curr + prev    return curr

Form 1 → 2: the map is the whole optimisation. Two lines change — check memo before recursing, write to it after. The second climb(3) in the trace now returns from the map instead of rebuilding the subtree beneath it, so each of the n + 1 states is built once. The call count drops from 2 × climb(n) − 1 to 2n − 1: for n = 5 that is 15 calls down to 9, and for n = 30 it is 2,692,537 down to 59.

Form 2 → 3: once every state is built once, you can choose the order. dp[i] only ever reads i - 1 and i - 2, so filling left to right guarantees both are ready. There are no calls left, so the O(n) call stack disappears and a large n can no longer overflow it. This is the version you write when n is big.

Form 3 → 4: keep only what the recurrence still reads. After writing dp[i], every cell from 0 up to i − 2 is dead — the next cell reads only i and i − 1 — so holding the whole array is waste. Two variables carry that live window of two, and space drops to O(1). What you give up is the table itself — if the question asks which sequence of steps produced the answer, you need Form 3 to walk back through.

Get dp[0] = 1 right or everything after it is wrong. There is exactly one way to climb zero steps: take no steps. Set dp[0] = 0 instead and the table reads 0, 1, 1, 2, 3, 5 — you get 5 for n = 5 rather than 8, and the bug looks like an off-by-one rather than a bad base case.

05 Cheat sheet

The four forms, and what each costs

Form	Time	Space	What climb(5) costs
1 · Plain recursion	`O(2ⁿ)`	`O(n)` stack	15 calls, 9 of them repeats
2 · Memoisation, top-down	`O(n)`	`O(n)` map + `O(n)` stack	9 calls, 4 additions
3 · Tabulation, bottom-up	`O(n)`	`O(n)` table, no stack	6 cells, 4 additions
4 · Two rolling variables	`O(n)`	`O(1)`	2 variables, 4 additions

Two conditions, not oneOverlapping subproblems make caching worth doing; optimal substructure makes the recurrence correct. Miss the first and DP buys you nothing. Miss the second and DP gives you a wrong answer very fast.

Naming the state is the jobSay in one sentence what dp[i] means — here, the number of ways to reach step i. Once that sentence exists, the recurrence and the base cases usually fall out of it. If you cannot write the sentence, you have not found the state.

Top-down and bottom-up fill the same tableMemoisation fills the cells in whatever order the recursion happens to ask for them; tabulation fills them in an order you pick. Same cells, same values, same O(n).

06 Where & why

When a table is the right answer

Dynamic programming is not a data structure and not a category of problem. It is what you do when a correct recursion turns out to recompute. So the honest test is never “is this a DP problem” — it is “does my recursion ask for the same input twice”.

Reach for it when…

A label repeats in the call treeDraw two levels of the recursion by hand. If the same argument shows up in two places, a cache pays for itself immediately.

The question is count, best, or possibleHow many ways, what is the minimum cost, can this be made exactly — these all decompose into “the answer here, given the answer just before here”.

The state is a few small numbersAn index, maybe a remaining budget. If you can index the state with two or three bounded integers, the table fits in memory.

History does not matterThe answer from step i on depends only on i, not on how you arrived at i. When that fails, i is not the whole state and you need another dimension.

Use something else when…

Situation	Better choice	Why
Every subproblem in the tree is distinct — merge sort, quicksort, binary search	Plain divide and conquer	Nothing overlaps, so a cache only adds memory and lookup cost for zero hits.
One locally best choice is provably safe — activity selection, Huffman coding	A greedy algorithm	A single pass, no table at all, and usually `O(n log n)` from the sort rather than `O(n)` plus a table.
You need the actual sequence of choices, not just the value	Form 3, the full table	Form 4 throws away every earlier cell, so there is nothing left to walk backwards through.
The state needs a subset — every combination of 40 items	Meet in the middle, branch and bound, or an approximation	The table would have 2⁴⁰ rows. Being `O(n)` per cell does not help when there are too many cells to store.

Interviewers rarely ask “do you know DP”. They ask you to write the recursion, then say “now make it faster”. If you can point at the repeated subproblem and add the cache, you have answered the question — tabulation and the two-variable version are polish you add out loud afterwards.

07 Interview questions

Say these out loud

The question that separates people is not the definition. It is being asked to name the repeated subproblem in a recursion you just wrote.

What is dynamic programming?

Solving a recursive problem once per distinct input instead of once per path that reaches it. You write the recursion, notice the same input appearing many times in the call tree, and store each answer the first time you work it out. Top-down memoisation, bottom-up tables and rolling variables are all that same idea in different packaging.

What two properties does a problem need before DP helps?

Overlapping subproblems and optimal substructure. Overlapping means the recursion asks for the same input more than once, which is what makes storing answers pay. Optimal substructure means the answer is built only from answers to subproblems, which is what makes the recurrence correct. Without the first, DP gains you nothing; without the second, DP gives you a wrong answer quickly.

How is that different from divide and conquer?

Divide and conquer splits into subproblems that never overlap — merge sort's two halves share no element, so there is nothing to cache. DP splits into subproblems that do overlap: climb(3) is needed by both climb(5) and climb(4). The test is to draw two levels of the tree and look for a repeated label.

Walk me through climbing stairs for n = 5.

The last move onto step n is a 1-step from n − 1 or a 2-step from n − 2, so climb(n) = climb(n-1) + climb(n-2), with climb(0) = 1 and climb(1) = 1. Filled bottom-up the table reads 1, 1, 2, 3, 5, 8, so there are 8 ways. Plain recursion needs 15 calls to get there; the table needs 6 cells and 4 additions.

Why is the plain recursion exponential?

Every call above the base makes two more, so the tree branches instead of running in a line. The exact count for climb(n) is 2 × climb(n) − 1 calls — 15 for n = 5, 177 for n = 10, and 2,692,537 for n = 30. Since the values themselves are Fibonacci numbers, the true growth rate is about 1.618 per level, and O(2ⁿ) is quoted as the loose upper bound.

Does memoisation change the complexity or just the constant?

The complexity. Without it the work is proportional to the number of paths through the tree, which grows exponentially. With it, each of the n + 1 states is computed once and does O(1) work, so the total is O(n). For n = 30 that is 2,692,537 calls down to 59.

Memoisation or tabulation — which would you write?

Both are O(n) here, so pick on shape. Memoisation is the smaller edit, since you bolt a map onto a recursion you already have, and it only visits the states you actually need. Tabulation removes the call stack so a large n cannot overflow it, and its fixed fill order makes the space optimisation obvious. In an interview write the memoised version first, then say out loud that you would convert it to a loop.

What exactly is “the state”, and how do you pick it?

The state is the smallest set of values that decides everything from here onward. For climbing stairs it is one number, the step you are standing on, so the table is one-dimensional. If the answer also depended on, say, how many 2-steps you had left, that would be a second dimension. Picking the state is the whole job — the recurrence usually falls out of it.

Can you always cut the space down to O(1)?

Only when the recurrence reaches back a fixed, small distance. dp[i] here reads i-1 and i-2, so two variables are enough. If a cell can read any earlier index, or if you need to reconstruct which choices produced the answer, you must keep the full table. Space optimisation trades away every state you promise never to look at again.

Why is this the same as Fibonacci?

Hard

You may take any number of steps from 1 to k in a single move. Return the number of ways to climb n steps in O(n) total time, not O(n × k).

Follow-up

Written directly, each cell sums k earlier cells, so the table is O(n × k). The windows for two neighbouring cells overlap almost completely, and exploiting that is the sliding-window trick sitting on top of the DP.

Show the hint

Write out the sums for dp[i] and dp[i+1] side by side and subtract — they differ by exactly two terms, which gives you dp[i+1] from dp[i] in constant time.