A fortune-seeker in the 1800s wants to travel from the east coast to the west, crossing the country stage by stage in a stagecoach. At each stop he can choose which town to head for next, and each leg carries a different price — a proxy, the story goes, for the life-insurance premium on that dangerous stretch. There are far too many complete routes to price one by one. Yet there is a way to find the cheapest crossing that examines each town only once. That method is dynamic programming — Richard Bellman's great idea for tearing a hard sequential decision into a chain of trivial ones.

Stages, states, decisions

Dynamic programming (DP) applies whenever a decision breaks naturally into a sequence of steps. Three words carry the whole method:

The crucial economy is that the state summarises history. Once the traveller knows he is in a particular town, it does not matter one bit how he got there — the cheapest way onward is the same. All the roads that led to this town collapse into a single number: the best cost still to come.

The value function and Bellman's recursion

Define the value function f_n(s) as the minimum total cost of finishing the journey, starting from state s at stage n. If c(s, x) is the immediate cost of decision x in state s, and that decision lands us in state x at the next stage, then the value obeys a beautifully simple recursive (Bellman) relation:

In words: the best from here is the cheapest immediate step, plus the best from wherever that step takes you. This is the principle of optimality in equation form — any tail of an optimal route is itself optimal for its own smaller problem, so we can build the whole optimum out of solved sub-problems.

Backward induction

The recursion tells us to work backwards. Start at the destination, where the cost to finish is zero. Step back one stage: for each town in the last stage the value is just the price of the final leg. Step back again, applying the Bellman relation with the values we already computed. Keep going until we reach the start. Because each stage only ever consults the next stage's answers, we solve the whole network in a single sweep.

Here is the stagecoach network — five stages, the towns as nodes, each edge labelled with its cost. Step through to reveal the cheapest crossing:

Working back: from the two stage-4 towns the finishing costs are 3 and 4. The stage-3 values come out as f(5)=4, f(6)=7, f(7)=6; the stage-2 values as f(3)=7 (and so on); and finally the start value f(1)=11. The highlighted route 1 \to 3 \to 5 \to 8 \to 10 achieves that cost of 11 — and we proved it optimal without ever listing all eighteen complete routes.

Why this beats brute force

A network with k intermediate stages, each holding m towns, has on the order of m^{k} complete routes — exponentially many. DP instead evaluates the Bellman relation once per town, a total of only about k \cdot m little minimisations. Turning an exponential search into a linear one is the payoff, and it is why DP underlies shortest paths, equipment-replacement schedules, production planning, and much of what follows in this course.