What is dynamic programming, really?

The Fibonacci numbers start 0, 1, and each one after that is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21… The most natural program for the nth one is three lines long, and it says exactly that.

def fib(n):
    if n < 2: return n
    return fib(n - 1) + fib(n - 2)

It is correct, and it is a trap. Before you read on: to work out fib(50), how many times does fib end up being called?

Forty billion: 40,730,022,147 calls, to get one number, 12,586,269,025.² At a billion calls a second that is most of a minute, and fib(60) would take more than an hour.

Where do the calls come from?

Each call asks two smaller questions, and each of those asks two more. Here is every call the program makes for fib(7): 41 calls, for an answer of 13. The calls in red are all the same question, fib(2), which the program works out 8 times, from scratch every time.

Drag the red number and look at how often each question comes back. The counts are Fibonacci numbers themselves: inside fib(50), the question fib(2) is answered 7,778,742,049 times. There are only 8 different questions in the whole tree. All the rest is the program forgetting what it already knew.

Remember the answers

So keep them. Before working anything out, look in a notebook: if the answer is already there, use it; if not, work it out once and write it down. Press remember answers above and watch the tree. Every question after its first is a single lookup, and the bushy tree collapses into a chain: 13 calls instead of 41.

from functools import cache

@cache
def fib(n):
    if n < 2: return n
    return fib(n - 1) + fib(n - 2)

In Python that is one line, @cache, which keeps every answer the function has given.⁷ Now fib(50) makes 99 calls: 51 questions, each worked out once, and 48 lookups. Forty billion steps have become ninety-nine.

So what is dynamic programming?

Working each smaller question out once, on purpose. A problem is a good fit when two things are true:¹ its answer can be built from the answers to smaller copies of the same problem, and the same smaller copies keep coming up again and again. Then you work each one out once. Doing it the way above, from the top and remembering as you go, is called memoization. The other way is to start at the bottom and fill in a table.

Box 0 holds 0, box 1 holds 1, and every box after is the two before it added up. No calls at all, just a loop: fib(50) is 49 additions. Most textbook dynamic programming is a table like this one, sometimes with two dimensions, and the hard part is never the table. It is spotting the smaller copies.

Wait, but then…

Here is a puzzle that looks nothing like it. You can climb a staircase one step or two steps at a time. How many different ways are there to climb 10 stairs? The first move is one step or two, and either way what is left is a smaller staircase of the same kind, so the ways to climb n stairs are the ways for n − 1 plus the ways for n − 2. It is Fibonacci again: 89 ways. It is LeetCode problem 70,⁶ and spotting that it is the same problem in disguise is the whole skill.

And the name? Richard Bellman said he chose it at RAND in 1950 for two reasons. Dynamic said the problems unfold in stages, over time, and programming meant planning, not code. And it hid the mathematics: the Secretary of Defense, Charles Wilson, had “a pathological fear and hatred of the word, research”, and this was a name “not even a Congressman could object to”.³ It is a good story, but the dates don’t quite fit: Bellman’s first paper with the name came out in 1952,⁴ and Wilson only took office in 1953.⁵ Why do you think he remembered it that way?

Try it yourself

Each task ticks itself off when the page above shows it.

1. Make the tree work out fib(2) more than ten times.From fib(8) on: it asks fib(2) 13 times, a Fibonacci number, because every question is asked as often as Fibonacci says.
2. Draw the biggest tree, then make it take fewer than twenty calls.With remembering, fib(9) takes 17 calls, 2 × 9 − 1, instead of 109.
3. Find a staircase with more than a thousand ways to climb it.Fifteen stairs: 987 ways for 15 is just short, so it takes 16 stairs, with 1,597 ways.
4. In your own words: why is the remembering version so much faster?

So dynamic programming is working each smaller copy of a problem out once: remember the answers on the way down, or fill a table from the bottom up, and the repeated work, often almost all of it, disappears.