Contents · 0% complete

Learning objectives
Core idea
Key formulae
Worked examples
Explore the graph
Common mistakes
Exam tip
Guided practice
Practice questions
Challenge
Summary
Quick quiz
Same topic, different board
Past paper questions

Learn9FM0Option · Decision Mathematics 2Dynamic programmingStages, states and Bellman’s principle

Dynamic programming · Subtopic 1 of 1

Dynamic Programming

Break a multi-stage decision into stages and states and work backwards from the end. Bellman's principle: any part of an optimal route from a state onwards is itself optimal. The value at each state uses the best value of the next stage, with $+$ for shortest/longest, $\max(\min)$ for maximin and $\min(\max)$ for minimax.

Edexcel 9FM0 Option≈ 45 minRevision 1 · updated 2026-10-27

Practise this topicTimed test Ask Salam Tutor

Section 1 of 14

Learning objectives

Use stage, state, action and value correctly.
Solve shortest and longest route problems by working backwards.
Solve maximin and minimax problems.
Present the working in a table.

Pause and think

Planning the cheapest route from London to Edinburgh via some cities each day, why might it help to start planning from Edinburgh?

Section 2 of 14

Core idea

Start herePlan from the finish

On a journey through several stages, the cheapest first step might lead you into an expensive finish. Instead, start at the destination: the best last step from each place is obvious. Work backwards and every decision is made knowing exactly what follows.

The big idea

Bellman's principle: the remainder of an optimal route is optimal from where it is. So the value at a state is the best over actions of (edge combined with the value at the destination), computed backwards stage by stage.

1. Shortest route

Network: $SA3$ , $SB5$ , $AC4$ , $AD2$ , $BC1$ , $BD6$ , $CT3$ , $DT5$ .

Worked exampleWorking backwards

Find the shortest route $S$ to $T$ .

Goal: Route and value.
Strategy: Stage 1, then 2, then 3.

$C:3,\ D:5$
One step from $T$ .
$A:\min(4+3,2+5)=7$
Both routes tie.
$B:\min(1+3,6+5)=4$
Via $C$ .
$S:\min(3+7,5+4)=9$
Via $B$ .

Answer

SBCT

, length

9

✓ Check

5+1+3=9

✓.

Why work backwards

$V(s)=\min_a\{w(s,a)+V(a)\}$
Bellman equation for shortest routes.
$V(a)\ \text{known before }V(s)$
Later stages are solved first.
$\text{each state solved once}$
No route is ever recomputed.

2. Maximin and minimax

Worked exampleMaximin

Find the route whose smallest edge is as large as possible.

Goal: Route and value.
Strategy: Replace "add" by "min", "min" by "max".

$C:3,\ D:5$
Last edges.
$A:\max(\min(4,3),\min(2,5))=3$
Worst leg along each option.
$B:\max(\min(1,3),\min(6,5))=5$
Via $D$ .
$S:\max(\min(3,3),\min(5,5))=5$
Via $B$ .

Answer

SBDT

, maximin value

5

✓ CheckEdges

5,6,5

: smallest

5

✓.

Combining rules

Drawing diagram…

Pick the combining rule for the problem type.

Common misconceptionState the route After finding the value, trace the optimal actions forward from the start.

Key takeawayTable layout Columns: stage, state, action, destination, value; star the best value at each state.

Pause and think

What's the minimax route?

Summary

Stages, states, actions.
Work backwards.
Choose the combining rule.

Stage: Step of the decision process.
State: Position within a stage.
Bellman's principle: Sub-routes of optimal routes are optimal.

HistoryRichard Bellman. Bellman coined "dynamic programming" in the 1950s at RAND, choosing a name his boss, who disliked the word "research", couldn't object to.

Fun factSpell-check. Spell-checkers measure how far a typo is from real words using dynamic programming (edit distance).

Section 3 of 14

Key formulae

Shortest

V(s)=\min_a\big(w(s,a)+V(\text{dest})\big)

Maximin

V(s)=\max_a\min\big(w(s,a),V(\text{dest})\big)

Minimax

V(s)=\min_a\max\big(w(s,a),V(\text{dest})\big)

TrickMaximin in words. Maximin: make the worst leg as good as possible (e.g. the lowest bridge as high as possible). Minimax: make the worst leg as small as possible.

Section 4 of 14

Worked examples

Example 1 · Shortest route0 / 3 steps

SA3

SB5

AC4

AD2

BC1

BD6

CT3

DT5

. Find the shortest route.

Example 2 · Maximin0 / 2 steps

Find the maximin route in the same network.

Section 5 of 14

Explore the graph

The staged network

Loading the interactive graph…

Try this

$S(0,1)$ ; stage 2: $A(1,2)$ , $B(1,0)$ ; stage 1: $C(2,2)$ , $D(2,0)$ ; $T(3,1)$ .
Weights $SA3$ , $SB5$ , $AC4$ , $AD2$ , $BC1$ , $BD6$ , $CT3$ , $DT5$ .

Work from $T$ back to $S$ .

In the real worldStock control. Firms decide how much to produce each month, balancing storage and set-up costs, with dynamic programming over months.

Section 6 of 14

Common mistakes

IncorrectWorking forwards greedily

CorrectWork backwards

The cheapest first step may lead to an expensive finish.

IncorrectAdding in maximin

CorrectTake the minimum of edge and value

Maximin tracks the worst leg, not the total.

IncorrectForgetting to state the route

CorrectTrace forward from

S

Value alone is incomplete.

Solving the same subproblem again

Bellman: write it down once.

Section 7 of 14

Exam tip

Exam tipTable columns. Stage | State | Action | Destination | Value. Mark the best value at each state with a star.

Section 8 of 14

Guided practice

SA-DM-DP-G012 marksL2 StandardNon-calculatorMin and max

Network:

SA3

SB5

AC4

AD2

BC1

BD6

CT3

DT5

. Find the shortest distance from

A

T

Salam Academy Original Practice · Proposed mark scheme

Section 9 of 14

Practice questions

SA-DM-DP-0012 marksL2 StandardNon-calculatorMin and max

Find the shortest distance from

S

T

Salam Academy Original Practice · Proposed mark scheme

SA-DM-DP-0022 marksL3 ExamNon-calculatorMaximin

Find the maximin value from

S

T

(make the smallest edge on the route as large as possible).

Salam Academy Original Practice · Proposed mark scheme

SA-DM-DP-0032 marksL3 ExamNon-calculatorMaximin

Find the minimax value from

S

T

(make the largest edge on the route as small as possible).

Salam Academy Original Practice · Proposed mark scheme

More questions on every skill in this subtopic are in the question bank under Practise.

Section 10 of 14

Challenge

SA-DM-DP-0042 marksL3 ExamNon-calculatorMin and max

Find the longest route value from

S

T

Salam Academy Original Practice · Proposed mark scheme

Section 11 of 14

Summary

Stages, states, actions.
Work backwards.
Shortest: add; maximin: max of min.
Bellman's principle.

Section 12 of 14

Quick quiz

Q1 · SA-DM-DP-Q011 markL1 FoundationNon-calculatorTables

Bellman's principle of optimality says

Salam Academy Original Practice · Proposed mark scheme

Section 13 of 14

Same topic, different board

Specification: A level Further Mathematics 9FM0
Where: Decision 2 · Dynamic programming
Expected: Stage, state, action, destination, value; Bellman’s principle of optimality; minimum, maximum, minimax and maximin problems in network and table form.
Calculator: Permitted; show enough working to earn the method marks.
Typical style: Edexcel often opens with a routine part and builds to a "show that" or "prove" part.
Open in: 9FM0 · Option

Section 14 of 14

Past paper questions

No past paper questions are tagged to this subtopic yet. We add papers every week.

Browse past papers

Salam Academy original content · Content status: reviewed and published. Syllabus mapping: Pearson Edexcel 9FM0, First teaching 2017 (official specification).