[Intermediate] — Decisions made in stages, where each choice changes what’s possible next. Bellman’s principle turns an explosion of combinations into a chain of small tables. This is the operations research origin of the DSA pattern, with the stages, states and uncertainty made explicit.

Source: [reference] — see the domain note. The code below was run and its output checked.

Before you start

You should have met dynamic programming as a coding pattern — memoisation and tabulation → DSA: dynamic programming. If you haven’t, this note still works, but the DSA version gives you more reps. You should know what an expected value is → random variables.

After this lesson you will be able to:

  1. Describe a multi-stage decision problem in terms of stages, states, decisions and a recursion.
  2. Solve a resource-allocation problem by backward recursion with tables, by hand.
  3. Extend a recursion to uncertain outcomes using expected values.
  4. Say when dynamic programming is the right tool and when the state space makes it hopeless.

Study route: sections 1–3, then close the note and rebuild the allocation tables yourself. Then section 4 (uncertainty) and the code.

The kid version

You’re walking home through a town and want the shortest route. At every crossroads you have a choice. Here’s the trick: whichever crossroads you’re at, the best way home from there doesn’t depend on how you got there. So work backwards: from the crossroads next to your house, the best way is obvious. From one further out, it’s “the best first step, then whatever was best from where that lands you.” Dynamic programming is solving a big decision by working backwards one step at a time, remembering the best answer from each place.

Where the analogy stops working. A town has a few hundred crossroads. Many real problems have a “place” (the state) described by several numbers at once — stock of five products, cash, time — and the number of states multiplies until there are too many to remember. That’s called the curse of dimensionality, and it’s dynamic programming’s real limit.

1. Why this exists

A firm has 3 units of budget to spread across three regions. Each region’s return depends on how much it gets, and not linearly — the first unit helps most:

   units given:   0    1    2    3
   region R1      0    4    6    7
   region R2      0    3    8    9
   region R3      0    5    6    7

The returns aren’t proportional, so this isn’t an LP. You could list every split (there are 10), but with 10 regions and 20 units there are about 10 million, and with real problems it’s worse. Dynamic programming solves it by deciding one region at a time, so the work grows with (regions × budget × options) instead of exploding.

Richard Bellman developed the method at RAND in the early 1950s for multi-stage planning. He later said he chose the name “dynamic programming” partly because it sounded impressive and was hard to object to.

Terms used in dynamic programming

  1. Stage: This is one step of the decision sequence — a region to fund, a month to plan, a city on a route. Stages are usually numbered in the order decisions are made.
  2. State: This is the information you need at a stage to make the rest of the decisions well. Here, it’s “how much budget is left.” A good state is the smallest summary of the past that the future depends on.
  3. Decision: This is the choice made at a stage — how many units to give this region.
  4. Transition: This is the rule for the next state given the current state and decision. Budget left next = budget left now − units given.
  5. Value function: This is also known as the optimal value function or cost-to-go. Written , it’s the best total you can get from stage onwards if you arrive in state .
  6. Bellman equation: This is also known as the recursion or the functional equation. This is the formula that defines in terms of .
  7. Principle of optimality: This is Bellman’s statement that an optimal policy has the property that whatever the first decision was, the remaining decisions must be optimal for the state that decision leads to.
  8. Policy: This is a rule giving the best decision for every stage and state — not just a single plan, but what to do in any situation you might find yourself in.

2. The principle of optimality

Bellman’s principle of optimality states that, whatever the current state and however you got there, the remaining decisions of an optimal plan must themselves be optimal from that state.

That’s what makes working backwards valid. It means you can write the best value from stage as:

In words: the best you can do from here is the best over all choices now of (what this choice earns) plus (the best you can do from where it leaves you).

The principle fails if the future depends on the past in a way the state doesn’t capture. If region R2’s returns depended on how much R1 got, “budget left” wouldn’t be a sufficient state. The fix is always to enlarge the state until the principle holds — which is where the cost comes from.

3. Backward recursion, step by step

Set up the allocation problem:

  1. Stages: region 1, region 2, region 3, in that order.
  2. State : units of budget still unallocated when you reach that stage.
  3. Decision : units to give this region, from 0 to .
  4. Transition: next state .
  5. Recursion: , with (nothing left to fund).

Work from the last stage backwards.

Stage 3 — region R3

Whatever’s left goes to R3 (giving less would waste it). So :

0123
0567

Stage 2 — region R2

For each possible budget , try each for R2, and add the best R3 can do with the rest.

best
00 + 0 = 0———00
10 + 5 = 53 + 0 = 3——50
20 + 6 = 63 + 5 = 88 + 0 = 8—81 or 2
30 + 7 = 73 + 6 = 98 + 5 = 139 + 0 = 9132

Read the bold cell: with 3 units left for R2 and R3 together, give R2 two units (earning 8) and leave one for R3 (earning 5).

Pause and predict: at stage 1 we start with 3 units. What will be, and how much goes to R1?

Stage 1 — region R1

Only one state matters here: we start with the full budget, .

30 + 13 = 134 + 8 = 126 + 5 = 117 + 0 = 713

Read the plan forwards

  1. R1 gets . Budget left: 3.
  2. At stage 2 with , the table says give R2 two units. Left: 1.
  3. R3 gets the last unit.

Allocation: R1 = 0, R2 = 2, R3 = 1. Total return: 13.

Notice R1 gets nothing even though its first unit is worth 4 — more than R2’s first unit. That’s because R2’s second unit is worth 5 (from 3 to 8), and greedy “best next unit” reasoning misses it. That’s exactly the kind of interaction dynamic programming handles and greedy doesn’t → when greedy works.

What it cost

Each stage-2 cell considers at most 4 options, for 4 states: about 16 evaluations. Stage 1: 4. Brute force over all splits: 20 combinations. With regions and budget , dynamic programming does about work instead of the combinatorial number of splits. For 10 regions and 20 units: about 4,000 evaluations against about 10 million.

4. Decisions under uncertainty

The real power shows up when outcomes are random. Then the recursion takes an expected value over what might happen.

Example — a two-week stocking problem. A shop sells a seasonal item for 2 weeks. Each week, demand is 1 unit with probability 0.5, or 2 units with probability 0.5. Each unit sold earns ₦10; each unit ordered costs ₦4; unsold stock at the end is worth nothing. At the start of each week, you can order up to 2 units, and unsold stock carries over.

State: stock on hand at the start of the week. Decision: how much to order. Randomness: demand. Write for the best expected profit from week onwards, starting with units.

Week 2 (the last week). With units available after ordering, expected sales are: if , 0; if , 1 (both demand outcomes sell it); if , . Expected revenue is that.

  1. From : order 0 → 0. Order 1 → . Order 2 → . Best: order 2, .
  2. From : order 0 → 10. Order 1 → . Best: order 1, .
  3. From : order 0 → 15. .

Week 1, starting with 0 stock. If you order , you then have ; demand sells and leaves for week 2.

  1. Order 1 (): always sell 1, leftover 0. Value .
  2. Order 2 (): with probability 0.5 sell 1 and carry 1; with 0.5 sell 2 and carry 0. Expected value .
  3. Order 0: .

Best: order 2 in week 1, expected profit ₦16. And the policy for week 2 is a rule, not a number: order 2 if you have none left, order 1 if you have one. That’s the point of a policy — you don’t know in advance which state you’ll be in.

This structure — states, decisions, random transitions, expected values — is a Markov decision process, and it’s the mathematical foundation of reinforcement learning → Markov chains.

5. When to use it, and when not

Use dynamic programming when:

  1. Decisions happen in a natural sequence (stages).
  2. A small state captures everything the future depends on.
  3. Rewards or constraints are nonlinear, so LP doesn’t fit.
  4. Outcomes are random and you need a policy, not just a plan.

Don’t, when the state is big. With five products and stock levels 0–100 each, there are states. That’s the curse of dimensionality, Bellman’s own phrase. Approximate dynamic programming and reinforcement learning exist to deal with it — by learning an approximation to instead of tabulating it.

Connections:

  1. Shortest path (note 06) is dynamic programming: Bellman–Ford is literally the Bellman equation applied repeatedly.
  2. The knapsack problem (note 07) has a DP solution that’s fast when the capacity is small.
  3. LQR in control theory is dynamic programming with a quadratic cost, solved in closed form → optimal control and LQR.

Worked example — the allocation recursion in Python

Runnable, standard library only.

# allocate.py — note 08's resource-allocation DP, backward recursion
returns = {"R1": [0, 4, 6, 7], "R2": [0, 3, 8, 9], "R3": [0, 5, 6, 7]}
regions = list(returns)
BUDGET = 3
 
f = {len(regions): {s: 0 for s in range(BUDGET + 1)}}   # nothing left to allocate: value 0
choice = {}
for stage in reversed(range(len(regions))):
    r = returns[regions[stage]]
    f[stage], choice[stage] = {}, {}
    for s in range(BUDGET + 1):
        best_k = max(range(s + 1), key=lambda k: r[k] + f[stage + 1][s - k])
        f[stage][s] = r[best_k] + f[stage + 1][s - best_k]
        choice[stage][s] = best_k
    print(regions[stage], "f =", f[stage])
 
s = BUDGET
for stage, name in enumerate(regions):
    k = choice[stage][s]
    print(f"give {name} {k} unit(s)")
    s -= k
print("total return:", f[0][BUDGET])
python3 allocate.py

Expected output:

R3 f = {0: 0, 1: 5, 2: 6, 3: 7}
R2 f = {0: 0, 1: 5, 2: 8, 3: 13}
R1 f = {0: 0, 1: 5, 2: 9, 3: 13}
give R1 0 unit(s)
give R2 2 unit(s)
give R3 1 unit(s)
total return: 13

The R2 line matches the stage-2 table. The R1 line fills in all four budgets, though only is used — the code computes the whole policy, which is what you’d want if the budget might change.

Common pitfalls and traps

  1. A state that’s too small. If the future depends on something the state doesn’t include, the recursion gives wrong answers without any error. Ask: “if two different histories arrive at the same state, should they make the same future decisions?”
  2. Off-by-one in the transition. Does stock carried over include this week’s order? Write the timeline of a single stage out in words before writing the formula.
  3. Forgetting the boundary. (or a salvage value) has to be set. A missing boundary is the commonest bug in tabulated code.
  4. Greedy instinct. Giving each unit to wherever it earns most right now fails whenever returns interact — as R1 vs R2 showed.
  5. Plan instead of policy. Under uncertainty, reporting “order 2 then order 2” is wrong: the second order depends on what happened.

Check your understanding

  1. In the allocation problem, what would change if region R3 could only accept at most 1 unit?
  2. Why is “budget remaining” a sufficient state for allocation, but “week number” alone is not sufficient for the stocking problem?
  3. In week 1 of the stocking problem, ordering 2 gives expected profit 16 but you might end up with stock that has to be carried. Why does carrying stock not show up as a cost in this model? What would change if it did?
  4. How many states would the stocking problem have if there were 3 products, each with stock 0–10?
After your attempt — answers
  1. becomes : . Stage 2 with : options , , , — still 13 at . The plan is unchanged because the optimum only gave R3 one unit anyway.
  2. In the allocation problem, the only way past decisions affect the future is through how much budget is left. In the stocking problem, past demand affects the future through how much stock is on hand, so stock must be in the state; the week number tells you how many weeks remain but not what you hold.
  3. The model has no holding cost, so the only cost of over-ordering is the chance that stock ends unsold at the end of week 2. With a holding cost per unit carried, each “carry 1” outcome would subtract , making ordering 2 in week 1 less attractive; above some , ordering 1 would win.
  4. states per week. Manageable — but with 10 products it would be .

Practice — independent task

  1. Reconstruct: with the note closed, rebuild the stage-2 and stage-1 tables for the allocation problem with a budget of 4 units, using these returns for 4 units: R1 = 7, R2 = 9, R3 = 7 (no gain beyond 3). Predict whether R1 now gets anything.
  2. Apply: write stock.py to solve the two-week stocking problem by recursion, then extend it to 4 weeks and to demand of 0, 1 or 2 with probabilities 0.2, 0.5, 0.3. Print the policy as a table: for each week and starting stock, the best order.
  3. Check: for the 2-week case, confirm your code gives and the week-2 rule “order 2 if empty, 1 if holding 1”.

Done when: your code reproduces the hand answers for 2 weeks, prints a full policy table for 4 weeks, and you can explain one row of it in words.

Before moving on

You’re ready when you can name the stages, state, decision and transition for a new problem, write its Bellman equation in words, and fill in a small table backwards.

Recap:

  1. Stage, state, decision, transition, value function — name all five before writing any maths.
  2. The principle of optimality makes backward recursion valid: the rest of an optimal plan is optimal from wherever you are.
  3. Under uncertainty, the recursion takes expectations and returns a policy.
  4. The work grows with the number of states; when the state has many dimensions, it explodes.

Next: Nonlinear Optimisation — when the objective curves, and what replaces corners and shadow prices.

↑ Back to Operations Research