On this page
Richard Bellman was an American mathematician, born in Brooklyn in 1920, who earned his PhD at Princeton in 1946 and died in Los Angeles in 1984, according to his MacTutor biography. In the summer of 1949, consulting at the RAND Corporation in Santa Monica, he was advised to work on "multistage decision processes" (Dreyfus, Operations Research, 2002): problems where you make a chain of choices, and each choice changes the situation for the next.
His first paper on the method, On the Theory of Dynamic Programming, appeared in the Proceedings of the National Academy of Sciences in August 1952.
Why is it called dynamic programming?
The name has nothing to do with writing code. In his autobiography, excerpted by Stuart Dreyfus, Bellman wrote that Secretary of Defense Wilson "had a pathological fear and hatred of the word, research", so he wanted a name that hid the mathematics (Dreyfus, 2002). "Programming" stood in for planning, and "dynamic" said the problem was multistage and changed over time. Bellman's verdict on his choice: "It was something not even a Congressman could object to."
What does the principle of optimality say?
Bellman's principle of optimality, from his 1957 book Dynamic Programming, states: "An optimal policy has the property that, whatever the initial state and initial decision, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision" (as quoted by Polson and Witte).
In plain words: if the fastest route from Delhi to Chennai passes through Nagpur, then its Nagpur-to-Chennai part must be the fastest route from Nagpur to Chennai. If it were not, you could swap in the faster tail and beat the "fastest" route, which is impossible. So you can solve a big problem backwards from the goal, writing down the best answer from each place once and reusing it.
Bellman meant the principle as a guide. When his colleague Oliver Gross said the principle was not rigorous, Bellman replied, "Of course not. It's not even precise," adding that "a good principle should guide the intuition" (Dreyfus, 2002).
How does dynamic programming work? A worked example
Say you travel from home (H) to an exam centre (Z) in three legs. Travel times, in minutes:
H to A: 10, H to B: 15
A to C: 20, A to D: 12
B to C: 8, B to D: 18
C to Z: 9, D to Z: 14
A greedy plan takes the quickest leg each time: H to A (10), A to D (12), D to Z (14), for 36 minutes.
Bellman's way starts at the end and writes one number at each stop: the least time left from there to Z.
From C it is 9. From D it is 14.
From A: the smaller of 20 + 9 = 29 and 12 + 14 = 26, so 26.
From B: the smaller of 8 + 9 = 17 and 18 + 14 = 32, so 17.
From H: the smaller of 10 + 26 = 36 and 15 + 17 = 32, so 32.
The best route is H, B, C, Z in 32 minutes, four minutes faster than greedy. Step 4 reused the numbers already written at A and B. That reuse is the whole trick. Here there are only 4 complete routes, but with 20 stages of two stops each there would be 2^20, more than a million, while the backward method still needs just four sums per stage.
How can you use Bellman's idea in your own maths?
How many ways can you climb 10 stairs taking 1 or 2 steps at a time? Your last step was either a single or a double, so ways(n) = ways(n − 1) + ways(n − 2). Start with ways(1) = 1 and ways(2) = 2, then fill in 3, 5, 8, 13, 21, 34, 55, 89. There are 89 ways, found with eight additions instead of listing every climb. You can count shortest routes on a grid the same way, adding the counts at the two corners you could have come from.
When a problem feels too big to list out:
Name the state: what do you need to know about where you are right now?
List the choices at each state and what each one costs or gains.
Check Bellman's test: does the best future depend only on the current state, not on how you got there?
Write the recurrence and the base case.
Fill a table in order from the base case, reusing every entry you have written.
If step 4 reminds you of proof by mathematical induction, that is no accident: both build each answer from the one before.
If you get stuck turning a word problem into a recurrence, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer. To revise sequences and recursion first, the Fermi Concept Library gives every concept in mathematics and computing its own lesson.
Try the stairs problem for 12 steps tonight, writing each answer once and reusing it.
