Dynamic Programming
Some decisions are not made all at once but in a sequence — which route to take leg by leg, how to allocate a budget period by period, when to replace a machine year by year. Dynamic programming is the art of solving such problems by cutting them into a chain of smaller stages, solving the last stage first, and letting each earlier decision lean on the best answer already computed for everything that follows. There is no single equation to memorise; instead there is a way of thinking — Bellman's principle of optimality — that turns a forbiddingly large search into a short recursion.
- The dynamic-programming idea — decompose a sequential problem into stages.
- The vocabulary of stages, states, decisions, and the optimal policy.
- Bellman's principle of optimality and why it makes recursion valid.
- The recursive (functional) equation and backward recursion.
- A fully worked staged shortest-path problem, solved stage by stage.
- Dynamic programming for the knapsack, and the curse of dimensionality.
The Dynamic Programming Idea
Dynamic programming (DP) solves a complex problem by breaking it into a sequence of simpler, interlocking subproblems called stages, solving each once, and storing the result so it is never recomputed. It applies when a problem has two features: an optimal substructure (an optimal solution is built from optimal solutions of its subproblems) and overlapping subproblems (the same subproblem recurs many times).
Unlike linear or integer programming, DP is not a single algorithm with a fixed form. It is a strategy: you must identify the stages, define what information carries from one stage to the next, and write a recursion linking them. The pay-off is enormous — problems whose brute-force search grows exponentially often collapse to a handful of table look-ups.
Stages, States & Decisions
Every dynamic program is described with four ingredients. A stage \(n\) is one step of the sequential decision. A state \(s_n\) summarises everything about the current situation that the remaining decisions need to know — and nothing more. A decision \(x_n\) is the choice made at stage \(n\); it earns an immediate return and moves the system to a new state \(s_{n+1}\). The collection of decisions across all stages is a policy, and the best one is the optimal policy.
The single most important modeling skill is choosing the state. A good state is a sufficient summary — given \(s_n\), the optimal continuation does not depend on how the system arrived there. This memoryless quality is exactly what the next principle formalises.
The Principle of Optimality
Dynamic programming rests on one idea, stated by Richard Bellman as the principle of optimality: whatever the current state and the decision just made, the remaining decisions must form an optimal policy for the state that results. In short, every tail of an optimal path is itself optimal.
The Recursive Equation
The principle of optimality translates directly into a recursive (functional) equation. Let \(f_n(s_n)\) be the best total return obtainable from state \(s_n\) at stage \(n\) through to the end. Then the best value at a stage equals the best immediate return plus the best value of wherever that decision leads:
Here \(c_n\) is the immediate return of decision \(x_n\) and \(t_n\) is the transition to the next state. The recursion is seeded at the final stage with a known boundary condition (for a destination, \(f = 0\)), then solved backward stage by stage. For maximization, replace \(\min\) with \(\max\). Each \(f_n(s_n)\) is stored, and the decision achieving it is recorded so the optimal policy can be traced forward at the end.
The Stagecoach Problem
The classic introduction is a staged shortest-path problem: a traveler must go from \(S\) to \(T\) across four stages, choosing one node at each stage, to minimise total cost. The number on each arc is its cost.
Solve backward. At stage 3 only one arc leads to \(T\), so \(f_3(C) = 4\) and \(f_3(D) = 2\). At stage 2, each node picks its cheaper onward option:
| state | via C | via D | \(f_2\) | go to |
|---|---|---|---|---|
| A | 3+4 = 7 | 6+2 = 8 | 7 | C |
| B | 2+4 = 6 | 3+2 = 5 | 5 | D |
Finally at stage 1, node \(S\) compares its two options using the stage-2 values:
| state | via A | via B | \(f_1\) | go to |
|---|---|---|---|---|
| S | 2+7 = 9 | 3+5 = 8 | 8 | B |
Reading the recorded decisions forward from \(S\): go to \(B\), then \(D\), then \(T\). The minimum cost is \(8\). Notice that each state's value was computed exactly once and reused — the essence of dynamic programming.
Dynamic Programming for the Knapsack
Dynamic programming also cracks the 0–1 knapsack of Chapter 15. Take the items as stages and the remaining capacity \(w\) as the state. Let \(f_i(w)\) be the best value achievable from items \(i, i{+}1, \dots\) with capacity \(w\). At each item we either skip it or take it (if it fits):
Consider three items with values \((6, 10, 12)\), weights \((1, 2, 3)\), and capacity \(W = 5\). Working backward from the last item, tabulate \(f_i(w)\) for each capacity:
| capacity \(w\) | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| \(f_3\) (item 3 only) | 0 | 0 | 0 | 12 | 12 | 12 |
| \(f_2\) (items 2–3) | 0 | 0 | 10 | 12 | 12 | 22 |
Then \(f_1(5) = \max\{\,f_2(5),\ 6 + f_2(4)\,\} = \max\{22,\ 18\} = 22\). The optimum takes items 2 and 3 (weight \(2+3 = 5\), value \(10 + 12 = 22\)), leaving item 1 behind. Each cell was filled once, giving a table of \(O(nW)\) entries rather than \(2^n\) subsets.
Features & Comparisons
Several traits distinguish dynamic programming from the other methods in this book:
| Feature | What it means |
|---|---|
| No fixed formulation | DP is an approach, not one algorithm — you design the stages, states, and recursion for each problem. |
| Backward or forward | Recursion can run from the last stage back or the first stage forward; both give the same optimum, and the choice is a matter of convenience. |
| Handles nonlinearity | Returns and transitions may be nonlinear or discrete, which linear programming cannot accommodate. |
| Curse of dimensionality | The table grows with the number of state variables; a state with several dimensions can become computationally intractable. |
Worked Examples
Problem. A firm plans production over 4 months to meet monthly demand while managing inventory. Name the stage, state, and decision.
Solution. The stage is the month \((n = 1,\dots,4)\); the state is the inventory carried into the month (a sufficient summary of the past); the decision is how much to produce that month. The return is the month's production plus holding cost.
Problem. An optimal route from \(S\) to \(T\) passes through node \(D\). What can you say about the portion from \(D\) to \(T\)?
Solution. By the principle of optimality it must itself be a shortest route from \(D\) to \(T\). If a cheaper \(D\)-to-\(T\) route existed, splicing it in would give a cheaper \(S\)-to-\(T\) route, contradicting optimality.
Problem. In the stagecoach network, compute \(f_2(A)\) and the decision it implies.
Solution. \(f_2(A) = \min\{\,c_{AC} + f_3(C),\ c_{AD} + f_3(D)\,\} = \min\{3 + 4,\ 6 + 2\} = \min\{7, 8\} = 7\), achieved by going to \(C\). So \(f_2(A) = 7\) with decision \(A \to C\).
Problem. Given the recorded decisions \(S \to B\), \(B \to D\), \(D \to T\), state the optimal path and cost.
Solution. Follow the pointers from the start: \(S \to B \to D \to T\). Summing the arcs, \(3 + 3 + 2 = 8\), which matches \(f_1(S) = 8\). The forward trace turns the stored decisions into the actual route.
Problem. For the knapsack example, verify \(f_2(5) = 22\).
Solution. \(f_2(5) = \max\{\,f_3(5),\ 10 + f_3(5-2)\,\} = \max\{12,\ 10 + 12\} = \max\{12, 22\} = 22\), taking item 2 and then the best of items \(\ge 3\) with capacity \(3\), namely item 3.
Problem. A knapsack has \(n = 20\) items and capacity \(W = 50\). Compare brute force with dynamic programming.
Solution. Brute force checks up to \(2^{20} \approx 10^{6}\) subsets. Dynamic programming fills a table of \(n \times (W+1) = 20 \times 51 = 1020\) cells, each with a constant-time comparison — three orders of magnitude fewer operations, because overlapping subproblems are solved once and reused.
Chapter Summary
Decompose a sequential problem into stages with optimal substructure and overlapping subproblems.
Stage, state (a sufficient summary), decision, and the optimal policy.
Every tail of an optimal policy is itself optimal — so states can be reused.
\(f_n(s_n) = \operatorname*{opt}_{x_n}\{c_n + f_{n+1}(s_{n+1})\}\), solved backward from a boundary.
Staged shortest path (cost 8) and the knapsack table (value 22).
No fixed formula; the curse of dimensionality bounds practical state sizes.
Problems
Set up the stages, states, and recursion for each, then solve backward and trace the policy forward. Difficulty rises down the list.
- Define stage, state, decision, and policy, and give an example of each for a shortest-route problem.
- State the principle of optimality in your own words and explain why it permits reusing a state's value.
- What two properties must a problem have for dynamic programming to apply? Give a one-line reason for each.
- Write the general backward-recursion equation for a minimization problem and identify every symbol.
- In the stagecoach network, compute \(f_2(B)\) and its decision, and confirm \(f_2(B) = 5\).
- Solve the stagecoach network by forward recursion instead and confirm the same optimum of \(8\).
- For the knapsack example, compute \(f_2(3)\) and \(f_2(4)\) and explain why item 2 is not taken at capacity \(3\).
- Explain the curse of dimensionality and give an example of a state that would cause it.
- A 3-stage network has costs \(S\!\to\!A=4,\ S\!\to\!B=2,\ A\!\to\!T=3,\ B\!\to\!T=6\). Solve by DP and give the optimal path and cost.
- Compare dynamic programming with branch and bound: how does each treat subproblems, and when is each preferable?
- Formulate (do not fully solve) a DP for allocating a budget of \(B\) units among \(n\) projects, each with its own return function \(r_j(\cdot)\): state the stage, state, decision, and recursion.
- Solve the knapsack with values \((10, 13, 18, 31)\), weights \((2, 3, 4, 7)\), capacity \(7\) by dynamic programming; report the optimal value and the items chosen.