Dynamic Programming

in Optimization
A Complete Guide with ELI5 Explanations,
Worked Examples, and Practice Problems

Those who cannot remember the past are condemned to repeat it.
 adapted for Dynamic Programming

Operations Research Series

February 16, 2026

Prepared as an instructional reference for students of

Operations Research, Industrial Engineering, and Applied Mathematics.

Dynamic Programming in Optimization 1

Contents
1 What is Optimization? 3

2 What is Dynamic Programming? 3

2.1 The Trip-Planning Analogy . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 The Two Key Ingredients . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Why Dynamic Programming Works 5

3.1 Bellman's Principle of Optimality . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Why Should You Trust It? . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4 Dynamic Programming vs Linear Programming 6

5 Common Characteristics of DP Problems 7

6 Stages, States, and Decisions 7

6.1 Stages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.2 States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.3 Decisions (Controls) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.4 How They Fit Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

7 The Value Function Concept 9

8 Recurrence Relation (Bellman Equation) 10

8.1 Maximization Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
8.2 Additive vs Non-Additive Objectives . . . . . . . . . . . . . . . . . . . . 10

9 Forward vs Backward Dynamic Programming 11

9.1 Backward DP (Most Common) . . . . . . . . . . . . . . . . . . . . . . . 11
9.2 Forward DP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
9.3 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

10 Algorithmic Steps 12

11 Graphical Interpretation 13
11.1 Multi-Stage Decision Network . . . . . . . . . . . . . . . . . . . . . . . . 13
11.2 State Transition Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . 14

12 Fully Worked Example: Shortest Path in a Network 14

12.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
12.2 Stage Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
12.3 State Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
12.4 Decision and Transition . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
12.5 Recurrence (Backward) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
12.6 Computation Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
12.7 Optimal Path and Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Dynamic Programming in Optimization 2

13 Fully Worked Example: Prot Maximization Across Zones 17

13.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
13.2 DP Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
13.3 Stage 3 (Zone 3  last zone) . . . . . . . . . . . . . . . . . . . . . . . . 17
13.4 Stage 2 (Zone 2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
13.5 Stage 1 (Zone 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
13.6 Optimal Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

14 Common Mistakes 18

15 Computational Complexity 19
15.1 The Curse of Dimensionality . . . . . . . . . . . . . . . . . . . . . . . . . 20

16 Applications of Dynamic Programming 20

16.1 Operations Research and Management Science . . . . . . . . . . . . . . . 20
16.2 Computer Science . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
16.3 Economics and Finance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

17 Practice Problems 21
17.1 Easy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
17.2 Medium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
17.3 Hard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

18 Exam-Level Questions 23

19 Selected Solutions 24
Dynamic Programming in Optimization 3

1 What is Optimization?
⋆ ELI5 Insight

Imagine you have a box of crayons and a colouring book. You want to colour the
prettiest picture possible, but you only have limited time before dinner. Optimization
is choosing which pages to colour and which crayons to use so that you get
the best result with the resources you have.

In mathematical terms, optimization is the process of nding the best solution from
a set of feasible alternatives.

Denition 1.1 (Optimization Problem). An optimization problem has the general form

min f (x)
x∈X
subject to gi (x) ≤ 0, i = 1, . . . , m,
hj (x) = 0, j = 1, . . . , p,

where
ˆ x is the decision variable (what we choose),
ˆ f (x) is the objective function (what we want to minimize or maximize),
ˆ gi , hj are constraint functions (the rules we must follow),
ˆ X is the feasible set.

Σ Math Translation

ˆ Objective: What do I want? −→ f (x)

ˆ Decision: What can I control? −→ x
ˆ Constraints: What are the rules? −→ gi (x), hj (x)
ˆ Feasible set: What choices are allowed? −→ X

Optimization appears everywhere: airlines scheduling ights, factories minimizing

waste, delivery trucks nding shortest routes, and investors maximizing returns. The
techniques we use depend on the structure of f , gi , hj , and X. One of the most powerful
and elegant techniques is Dynamic Programming, the subject of this document.

Remark 1.1. We write  min for minimization; for maximization, simply replace min with
max (or equivalently minimize −f (x)).

2 What is Dynamic Programming?

⋆ ELI5 Insight

You are climbing a staircase with 10 steps. You can take either 1 step or 2 steps
at a time. You want to know: How many dierent ways can I reach the top?
You could try every possible combinationbut that is exhausting! Instead, notice
this:
ˆ The number of ways to reach step 10 depends only on how many ways you can
reach step 8 and step 9 (because from either of those you can jump to 10).
ˆ The number of ways to reach step 9 depends only on steps 7 and 8.
Dynamic Programming in Optimization 4

ˆ ... and so on, all the way down to steps 1 and 2.

So you solve the tiny problems rst (steps 1, 2, 3,. . . ), remember the answers, and
build up to the big problem. That is Dynamic Programming!

Denition 2.1 (Dynamic Programming). Dynamic Programming (DP) is an opti-

mization technique that solves a complex problem by
1. breaking it into a collection of simpler, overlapping sub-problems,
2. solving each sub-problem only once,
3. storing (memorizing) the result, and
4. combining stored results to solve larger sub-problems until the original problem is
solved.

The term was coined by Richard Bellman in the 1950s. Despite the name, it has
nothing to do with programming in the software senseprogram here means a plan
or schedule.

2.1 The Trip-Planning Analogy

⋆ ELI5 Insight

Imagine you are planning a road trip from City A to City E, passing through
intermediate cities B, C, D. At every city you choose which road to take next. Each
road has a cost (fuel, tolls, time).

2
B2 C2 5
5 2
6 D E
3 4
A B1 C1 3

Instead of listing every route from A to E, you work backwards :

1. From D to E the cost is 2. (Only one choice.)
2. From C1 the cheapest way is C1 → D → E costing 3 + 2 = 5.
3. From C2 it costs 5 + 2 = 7.
4. Continue backwards to B's, then to A.
You never re-examine routes you already evaluatedyou just look up stored answers.
This is DP in action.

2.2 The Two Key Ingredients

Every DP problem has two essential properties:

Key Concept

1. Optimal Substructure: An optimal solution to the whole problem contains

within it optimal solutions to sub-problems.

2. Overlapping Sub-problems: The same sub-problems are solved many times

when using a naive recursive approach.
Dynamic Programming in Optimization 5

✓ Why This Works

Because of optimal substructure, we can safely build global optima from local optima.
Because of overlapping sub-problems, storing solutions (memoization / tabulation)
gives us a huge speed-up compared to brute force.

3 Why Dynamic Programming Works

3.1 Bellman's Principle of Optimality
Theorem 3.1 (Principle of Optimality  Bellman, 1957). An optimal policy has the
property that whatever the initial state and initial decision are, the remaining decisions
must constitute an optimal policy with regard to the state resulting from the rst decision.

⋆ ELI5 Insight

Suppose you found the cheapest route from your home to the airport, passing
through the highway and then the tunnel. The Principle of Optimality says: the part
of your route from the highway onward must also be the cheapest way to get from
the highway to the airport.
If it weren't, you could swap in a cheaper highway-to-airport route and your total trip
would be even cheapercontradicting the fact that your original route was optimal!

Proof sketch (by contradiction). Let π ∗ = (d∗1 , d∗2 , . . . , d∗N ) be an optimal policy for an
N -stage problem starting in state s1 .
Suppose the sub-policy (d∗k , d∗k+1 , . . . , d∗N ) is not optimal for the sub-problem starting
∗ ∗
in the state sk that results from applying (d1 , . . . , dk−1 ). Then there exists a sub-policy

(dˆk , . . . , dˆN ) with a strictly better objective value from sk onward. Replacing the tail of
π ∗ yields a new policy
π̂ = (d∗1 , . . . , d∗k−1 , dˆk , . . . , dˆN )
whose total objective value is strictly better than that of π∗. This contradicts the opti-
∗
mality of π . Hence the sub-policy must be optimal.

Σ Math Translation

Let f ∗ (s) denote the optimal cost-to-go from state s. The Principle of Optimality
implies the recursive structure

n o
f ∗ (sk ) = min c(sk , dk ) + f ∗ (s ) ,
dk ∈Dk (sk ) | {zk+1}
immediate cost optimal future cost
| {z }

where sk+1 = T (sk , dk ) is the state transition. This is the Bellman equation, the
engine of all DP algorithms.
Dynamic Programming in Optimization 6

3.2 Why Should You Trust It?

✓ Why This Works

The Principle of Optimality converts one giant N -decision problem into N single-
decision problems, each of which is easy. We solve them in order (forward or back-
ward), and the stored optimal values guarantee that every local decision is globally
consistent. No backtracking is ever needed.

4 Dynamic Programming vs Linear Programming

Students often confuse DP with LP because both are programming methods. They are
fundamentally dierent.

⋆ ELI5 Insight

Think of Linear Programming as lling out a single giant form where every rule
(constraint) is a straight line and you slide along those lines to nd the best corner.
Dynamic Programming is more like playing a video game level by levelyou make
the best move at each level, remembering what happened before.

Table 1: DP vs LP at a glance

Feature Linear Programming Dynamic Programming

(LP) (DP)

Problem structure Single-stage; all decisions at Multi-stage; decisions made

once sequentially

Objective / constraints Must be linear Can be any form (linear,

nonlinear, discrete)

Solution method Simplex, Interior Point Recursive computation

(Bellman equation)

Decision variables Continuous (usually) Discrete or continuous

State concept No explicit state Central concept: state sum-

marizes history

Curse of dimensionality Scales with # vari- Scales exponentially with #

ables/constraints state variables

Typical applications Blending, transportation, Shortest path, inventory,

assignment scheduling, knapsack

Σ Math Translation

LP solves min{c⊤ x : Ax ≤ b, x ≥ 0}one shot, all variables simultaneously.

∗ ∗
DP solves f (s1 ) = mind1 {c1 + f (s2 )}stage by stage, building on sub-problem
solutions.
Dynamic Programming in Optimization 7

Remark 4.1. LP and DP are not competitors; they are complementary. Some problems
(e.g., stochastic inventory) use DP at the top level and LP inside each stage.

5 Common Characteristics of DP Problems

How do you recognize a problem that can be solved by DP? Look for these ve telltale
signs:

⋆ ELI5 Insight

Before you build a LEGO castle using the level-by-level trick (DP), check:
1. Can you split the build into stages (layers)?
2. At each layer, does the best way to continue depend only on what the current
layer looks likenot on how you got there?
3. Do the same what does this layer look like? questions pop up again and
again ?
4. Can you describe what this layer looks like with a small label (the state )?
5. Is there a clear way to go from one layer to the next?
If yes to all, DP will work beautifully.

Key Concept

1. Multi-stage structure: The problem can be divided into a sequence of stages

k = 1, 2, . . . , N .

2. Optimal substructure: An optimal solution contains optimal solutions to

sub-problems (Principle of Optimality holds).

3. Overlapping sub-problems: Sub-problems recur across dierent branches of

the recursion tree.

4. State representation: At each stage, the system can be described by a state

sk that captures all information needed to make future decisions.

5. Recursive relationship: A recurrence (Bellman equation) links the value at

one stage to the value at the next.

✓ Why This Works

Properties 12 guarantee correctness (we are not missing the true optimum). Prop-
erty 3 guarantees eciency (we save time by not re-solving). Properties 45 give us
the machinery (states and recurrences) to implement the algorithm.

6 Stages, States, and Decisions

These three concepts form the vocabulary of every DP formulation.
Dynamic Programming in Optimization 8

6.1 Stages
Denition 6.1 (Stage). A stage is a point in the problem at which a decision must be
made. Stages are indexed k = 1, 2, . . . , N and often correspond to time periods, locations,
or items being considered.

⋆ ELI5 Insight

Think of stages as checkpoints in a race. At each checkpoint you decide which path
to take to the next checkpoint.

Example 6.1. In a 4-city trip A → B → C → D:

ˆ Stage 1: Choose the road from A.
ˆ Stage 2: Choose the road from B .
ˆ Stage 3: Choose the road from C .

6.2 States
Denition 6.2 (State). A state sk at stage k is a complete description of the system's
conditionit contains all the information needed to make optimal decisions from stage
k onward, without knowing how the system arrived at sk .

⋆ ELI5 Insight

The state is your save le in a video game. If someone loads your save le, they
can play optimally from that point without knowing anything about what you did
before.

Σ Math Translation

Formally, the state must satisfy the Markov property :

P (sk+1 | sk , dk , sk−1 , dk−1 , . . . ) = P (sk+1 | sk , dk ).

The future depends on the present state and current decision, not on the past.

Example 6.2. In the shortest-path problem, the state at stage k is simply which node
you are at. Your past route does not matteronly your current node determines what
you can do next.

6.3 Decisions (Controls)

Denition 6.3 (Decision). A decision (or control ) dk is the action taken at stage k.
The set of admissible decisions when the system is in state sk is denoted Dk (sk ).

Example 6.3. If you are at node B and you can go to C1 , C2 , or C3 , then

Dk (B) = {C1 , C2 , C3 }.

Your decision dk is which of those three you pick.

Dynamic Programming in Optimization 9

6.4 How They Fit Together

The relationship between stages, states, and decisions is captured by the state transition
function:
sk+1 = Tk (sk , dk ), dk ∈ Dk (sk ).

Dk (sk ) Tk (sk , dk )
Stage k State sk Decision dk State sk+1

Remark 6.1. Choosing good states is the art of DP. States that are too detailed lead to
the curse of dimensionality; states that are too coarse lose the Markov property.

7 The Value Function Concept

Denition 7.1 (Value Function / Cost-to-Go Function). The value function fk∗ (sk )
gives the optimal objective value achievable from state sk at stage k to the end of the
problem.
For a minimization problem:

N
X
fk∗ (sk ) = min ci (si , di ).
dk ,dk+1 ,...,dN
di ∈Di (si ) i=k

⋆ ELI5 Insight

Imagine you are on stage 3 of a 5-stage journey. The value function f3∗ (s3 ) answers:
If I play perfectly from here onward, what is the least total cost I will pay from stage 3
to the nish?
It is like asking a GPS: What is the shortest remaining distance to the destination
from right here?

Σ Math Translation

The value function converts an N -stage optimization into a single number for every
(k, sk ) pair:
fk∗ : Sk −→ R, k = 1, 2, . . . , N.
ˆ fN∗ (sN ) is the boundary condition (cost at the last stage).
ˆ f1∗ (s1 ) is the answer to the whole problem.

Properties of the value function:

1. Recursive: fk∗ can be computed from

∗
fk+1 (backward DP) or
∗
fk−1 (forward DP).

2. Monotonic information: As we move from the boundary toward stage 1, the

value function accumulates more and more cost/reward.

3. Policy extraction: Once all fk∗ are known, the optimal decisions are obtained by

d∗k (sk ) = arg min ck (sk , dk ) + fk+1

∗


Tk (sk , dk ) .
dk ∈Dk (sk )
Dynamic Programming in Optimization 10

✓ Why This Works

The value function reduces the search space dramatically. Instead of optimizing
QN ∗
over all k=1 |Dk | possible decision sequences, we evaluate fk for each state at each
stagea much smaller computation.

8 Recurrence Relation (Bellman Equation)

The Bellman equation is the mathematical heart of dynamic programming.

Denition 8.1 (Bellman Equation  Minimization Form).

n
o
fk∗ (sk ) = min ∗
ck (sk , dk ) + fk+1 Tk (sk , dk ) , k = N, N −1, . . . , 1.
dk ∈Dk (sk )

with boundary condition

fN∗ +1 (sN +1 ) = 0 (or a terminal cost, if applicable).

⋆ ELI5 Insight

The Bellman equation says:

The best I can do from here = the cheapest `one-step cost plus best-I-can-do-from-
the-next-place' .

You try every allowed action at this stage, compute cost of this action + already-
known future cost, and pick the smallest.

Σ Math Translation

Breaking the equation into words:

 
fk∗ (sk ) = min c (sk , dk ) + ∗
fk+1 (sk+1 ) .
dk |k {z
optimal cost from stage k immediate cost at stage k optimal cost from stage k+1
| {z } } | {z }

ˆ sk+1 = Tk (sk , dk ): state transition.

ˆ d∗k = arg min: the decision that achieves the minimum.

8.1 Maximization Form

For prot-maximization problems, simply replace min with max:
n
o
fk∗ (sk ) = max ∗
rk (sk , dk ) + fk+1 Tk (sk , dk ) .
dk ∈Dk (sk )

8.2 Additive vs Non-Additive Objectives P

The standard Bellman equation assumes an additive objective k ck . DP also works for:
ˆ Multiplicative: fk∗ (sk ) = mindk {ck (sk , dk ) · fk+1
∗
(sk+1 )}.
ˆ Minmax: fk∗ (sk ) = mindk max{ck (sk , dk ), fk+1
∗
(sk+1 )}.
as long as the Principle of Optimality holds.
Dynamic Programming in Optimization 11

✓ Why This Works

The recurrence exploits the Principle of Optimality: because the optimal tail from
∗
sk+1 is already stored as fk+1 , we only need to search over one decision dk at each
stage rather than over all future decision sequences. This is what makes DP ecient.

9 Forward vs Backward Dynamic Programming

DP can be executed in two directions. Both reach the same optimal value, but they
unroll the recurrence dierently.

9.1 Backward DP (Most Common)

Denition 9.1 (Backward Recursion). Start at the last stage and work toward the rst :

fN∗ +1 (sN +1 ) = 0 (boundary), (1)

fk∗ (sk ) ∗

= min ck (sk , dk ) + fk+1 (Tk (sk , dk )) , k = N, N −1, . . . , 1. (2)
dk ∈Dk (sk )

The answer is f1∗ (s1 ).

⋆ ELI5 Insight

Backward DP is like planning a trip from the destination back to your house.
1. You start at the nish line and note: cost from here to nish = 0.
2. You step one city back and ask: What is the cheapest way to the nish from
here?
3. Keep stepping back until you reach home.

9.2 Forward DP
Denition 9.2 (Forward Recursion). Start at the rst stage and work toward the last.
Dene gk∗ (sk ) as the optimal cost to reach state sk :

g1∗ (s1 ) = 0 (boundarystarting state is free), (3)

∗
gk∗ (sk )

gk+1 (sk+1 ) = min + ck (sk , dk ) , k = 1, 2, . . . , N. (4)
sk , d k :
Tk (sk ,dk )=sk+1

∗
The answer is min gN +1 (sN +1 ).
sN +1

⋆ ELI5 Insight

Forward DP is the natural way you might think about it: start from home and ask
at every city, What is the cheapest way to get here ?
Dynamic Programming in Optimization 12

9.3 Comparison
Table 2: Forward vs backward DP

Backward DP Forward DP

Value function meaning cost-to-go (future) cost-to-come (past)

Boundary condition at last stage at rst stage

Recursion direction k=N →1 k=1→N

∗
Policy read-out follow dk forward trace back through stored decisions

✓ Why This Works

Both directions produce the same optimal value because the Principle of Optimality
holds in both directions. Choose whichever direction makes the boundary condition
easier to dene or the state-space simpler to enumerate.

10 Algorithmic Steps
Here is a step-by-step recipe that works for any DP problem.

Key Concept

The DP Recipe (Backward Recursion)

1. Identify the stages. What sequential decisions must be made? Label them
k = 1, 2, . . . , N .
2. Dene the state. What information at stage k fully determines the future?
Call it sk ∈ Sk .
3. Dene the decision. What choices are available at stage k in state sk ? Call
the decision dk ∈ Dk (sk ).
4. Write the state transition. sk+1 = Tk (sk , dk ).
5. Write the stage cost/reward. ck (sk , dk ).
6. Write the Bellman equation.

fk∗ (sk ) = ∗

min ck (sk , dk ) + fk+1 (Tk (sk , dk )) .
dk ∈Dk (sk )

7. Set the boundary condition. fN∗ +1 (sN +1 ) = 0 (or appropriate terminal

value).

8. Solve backward from stage N

to stage 1. At each stage, for each state,
∗ ∗
evaluate the Bellman equation and record fk (sk ) and dk (sk ).

9. Extract the optimal policy. Starting from s1 , follow the recorded decisions:
d∗1 → s2 → d∗2 → · · · → sN → d∗N .
Dynamic Programming in Optimization 13

⋆ ELI5 Insight

Think of it as baking a cake:

1. Decide how many layers (stages).
2. Know what avour each layer should be (state).
3. Choose the icing for each layer (decision).
4. Know how one layer aects the next (transition).
5. Score each layer's taste (cost).
6. Use the best remaining taste formula (Bellman equation).
7. The top layer's score is known (boundary).
8. Work down layer by layer.
9. Stack the cake and enjoy (optimal policy)!

Remark 10.1. For forward recursion, swap steps 78: set the boundary at stage 1 and
solve forward from stage 1 to stage N.

11 Graphical Interpretation
Visualizing DP problems as graphs is one of the most powerful ways to build intuition.

11.1 Multi-Stage Decision Network

A DP problem can be drawn as a directed acyclic graph (DAG) where:
ˆ Columns represent stages.
ˆ Nodes within a column represent states.
ˆ Arcs represent decisions, labelled with costs.

Stage 1 Stage 2 Stage 3 Stage 4

4 C
2
A 1
3
5
S D T
5 6
B 3
2 E

Figure 1: A four-stage decision network. Node S is the source (start), T is the sink
(terminal). Each arc label is the cost of that decision.

⋆ ELI5 Insight

This picture is like a board game. You start at S, and at each column you pick
which node to jump to. The numbers on the arrows are the tolls you pay. DP nds
the path with the smallest total toll.
Dynamic Programming in Optimization 14

11.2 State Transition Diagram

A state transition diagram focuses on one stage and shows how each decision transforms
the current state into the next state.

Stage k Stage k+1

s′1
d = α, c = 3
s1
d = β, c = 7

States s′2

d = α, c = 4
s2
d = γ, c = 2
s′3

Figure 2: State transition diagram for one stage of a DP problem. Each arrow shows a
decision d, the resulting next state, and the immediate cost c.

Σ Math Translation

In graph-theoretic terms:
ˆ Nodes = (stage, state) pairs.
ˆ Arcs = decisions; arc weight = stage cost ck (sk , dk ).
ˆ DP = nding the shortest (or longest) path in this DAG.
Because the graph is a DAG (no cycles), the shortest path can be found in O(|nodes|+
|arcs|) timewhich is exactly what the Bellman equation does.

12 Fully Worked Example: Shortest Path in a Network

12.1 Problem Statement
A delivery truck must travel from node 1 (warehouse) to node 10 (customer) through
the network below. The number on each arc is the travel cost. Find the minimum-cost
path using backward DP.
Dynamic Programming in Optimization 15

2 7 5
1
2 4 8
3
6 3
1 4 3 2 6 10
5 3 4
3 6 9
3
4 4 7

Stage 1 Stage 2 Stage 3 Stage 4 Stage 5

Figure 3: Shortest-path network with 10 nodes and 5 stages.

12.2 Stage Denition

We partition the nodes into stages based on their distance from the source:

Stage 1: {1}
Stage 2: {2, 3, 4}
Stage 3: {5, 6, 7}
Stage 4: {8, 9}
Stage 5: {10}

12.3 State Denition

At each stage, the state is the node the truck is currently at. The state captures all
information needed to determine future costs.

12.4 Decision and Transition

At each node, the decision is which outgoing arc to take. The transition is determin-
istic: taking arc (i → j) moves the truck to node j.

12.5 Recurrence (Backward)

Let f ∗ (i) denote the minimum cost from node i to node 10.

f ∗ (i) = cij + f ∗ (j) , f ∗ (10) = 0.


min
j∈Next(i)

12.6 Computation Tables

Node i f ∗ (i) d∗ (i)
10 0 

Stage 5 (Boundary).
Dynamic Programming in Optimization 16

Node Calculation f ∗ (i) d∗ (i)

8 c8,10 + f ∗ (10) = 3 + 0 = 3 3 → 10
9 c9,10 + f ∗ (10) = 4 + 0 = 4 4 → 10

Stage 4.

Node Candidates cij + f ∗ (j) f ∗ (i) d∗ (i)

5 →8:1+3=4 4 →8
6 → 8 : 6 + 3 = 9; →9:3+4=7 7 →9
7 →9:3+4=7 7 →9

Stage 3.

Node Candidates cij + f ∗ (j) f ∗ (i) d∗ (i)

2 → 5 : 7 + 4 = 11; → 6 : 4 + 7 = 11 11 → 5 (tie)
3 → 5 : 3 + 4 = 7; → 6 : 2 + 7 = 9; → 7 : 5 + 7 = 12 7 →5
4 → 6 : 6 + 7 = 13; → 7 : 4 + 7 = 11 11 →7

Stage 2.

Node Candidates c1j + f ∗ (j) f ∗ (1) d∗ (1)

1 → 2 : 2 + 11 = 13; → 3 : 4 + 7 = 11; → 4 : 3 + 11 = 14 11 →3

Stage 1.

12.7 Optimal Path and Cost

4 3 1 3
1 →
− 3 →
− 5 →
− 8 →
− 10 Total cost = 4 + 3 + 1 + 3 = 11.

⋆ ELI5 Insight

We started at the nish and asked how far am I? for every node near the end. Then
we stepped one column left and asked the same question, using answers we already
found. After four steps backward we reached the start and could read o the cheapest
route forwards : 1 → 3 → 5 → 8 → 10 costing just 11.

✓ Why This Works

We evaluated only 2 + 3 + 3 + 3 = 11 arc costs (plus lookups of stored f∗ values),

whereas brute-force enumeration would examine 3 × 3 × 2 = 18 complete paths. For
larger networks the savings are enormous.
Dynamic Programming in Optimization 17

13 Fully Worked Example: Prot Maximization Across

Zones
13.1 Problem Statement
A company has a budget of 5 units of capital to invest across 3 sales zones. The
prot (in $1000s) from investing xi units in zone i is given in the table below. Each xi
must be a non-negative integer and x1 + x2 + x3 = 5. Maximize total prot.

Table 3: Prot table ri (xi ) (in $1000s)

Investment xi Zone 1 r1 Zone 2 r2 Zone 3 r3

0 0 0 0

1 3 5 4

2 5 8 6

3 7 9 9

4 8 12 11

5 9 13 13

13.2 DP Formulation
ˆ Stages: k = 1, 2, 3 (one per zone).
ˆ State: sk = remaining budget when entering zone k . So s1 = 5.
ˆ Decision: xk = amount invested in zone k , 0 ≤ xk ≤ sk .
ˆ Transition: sk+1 = sk − xk .
ˆ Recurrence (backward, maximization):

fk∗ (sk ) = max ∗

f4∗ (s4 ) = 0.

rk (xk ) + fk+1 (sk − xk ) ,
0≤xk ≤sk

13.3 Stage 3 (Zone 3  last zone)

All remaining budget goes to Zone 3: f3∗ (s3 ) = r3 (s3 ).

s3 f3∗ (s3 ) x∗3

0 0 0
1 4 1
2 6 2
3 9 3
4 11 4
5 13 5

13.4 Stage 2 (Zone 2)

f2∗ (s2 ) = max0≤x2 ≤s2 {r2 (x2 ) + f3∗ (s2 − x2 )}.
Dynamic Programming in Optimization 18

s2 x2 =0 x2 =1 x2 =2 x2 =3 x2 =4 x2 =5 f2∗ x∗2
0 0      0 0

1 4 5     5 1

2 6 9 8    9 1

3 9 10 12 9   12 2

4 11 13 14 13 12  14 2

5 13 15 17 15 16 13 17 2

For example, at s2 = 5, x2 = 2: r2 (2) + f3∗ (3) = 8 + 9 = 17. This is the maximum.

13.5 Stage 1 (Zone 1)

f1∗ (5) = max0≤x1 ≤5 {r1 (x1 ) + f2∗ (5 − x1 )}.

s1 x1 =0 x1 =1 x1 =2 x1 =3 x1 =4 x1 =5 f1∗ x∗1
5 17 17 19 19 13 9 19 2 (or 3)

13.6 Optimal Solution

∗
Taking x1 = 2: remaining s2 = 3, then from Stage 2 table x∗2 = 2: remaining s3 = 1,
∗
then x3 = 1.

x∗1 = 2, x∗2 = 2, x∗3 = 1, Total prot = r1 (2) + r2 (2) + r3 (1) = 5 + 8 + 4 = $19,000.

⋆ ELI5 Insight
5+3−1


We had $5 to spread across three shops. Instead of trying all
3−1
= 21 combi-
nations, we rst gured out the best way to use any leftover money in Shop 3, then
combined that with Shop 2, and nally Shop 1. Only three small tables instead of
one huge enumeration!

14 Common Mistakes
△ Common Mistake

Mistake 1: Wrong state denition. Choosing a state that does not capture
enough information to satisfy the Markov property. If future costs depend on how
you arrived at a state (not just which state you are in), your DP will give wrong
answers.
Fix: Augment the state until the Markov property holds.
Dynamic Programming in Optimization 19

△ Common Mistake

Mistake 2: Wrong recursion direction. Computing fk∗ before

∗
fk+1 is known (in
backward DP), which leads to undened look-ups.
Fix: Always start from the boundary and work toward the unknown side.

△ Common Mistake

Mistake 3: Forgetting the boundary condition. Without fN∗ +1 = 0 (or the

appropriate terminal value), the recursion has no base case and cannot produce nu-
merical answers.
Fix: Explicitly write the boundary before computing anything.

△ Common Mistake

Mistake 4: Confusing min and max. Using min in a prot-maximization problem

or max in a cost-minimization problem.
Fix: Read the problem statement carefully. Ask: Am I trying to make this quantity
as small or as large as possible?

△ Common Mistake

Mistake 5: Not recording decisions. Computing fk∗

correctly but forgetting to
∗
record which decision dk achieved the optimum, making it impossible to reconstruct
the optimal policy.
Fix: Always store both fk∗ (sk ) and d∗k (sk ) in your tables.

△ Common Mistake

Mistake 6: Double-counting costs. Including the same cost in two consecutive

stages (e.g., counting the arc cost in both ck and ck+1 ).
Fix: Clearly assign each cost element to exactly one stage.

15 Computational Complexity
⋆ ELI5 Insight

Imagine you have a bookshelf with S books (states) on each of N shelves (stages),
and for each book you must ip through D pages (decisions) to decide the best one.
The total work is roughly N ×S ×D page-ips. Compare this with brute force, which
N
would be D (trying every combination)exponentially worse!

Denition 15.1 (DP Complexity). For a problem with:

ˆ N stages,
ˆ at most |S| states per stage,
ˆ at most |D| decisions per state,
the time complexity of the DP algorithm is

O(N · |S| · |D|) .

Dynamic Programming in Optimization 20

The space complexity is O(N · |S|) to store all value-function tables, or O(|S|) if only
two consecutive stages need to be kept in memory.

15.1 The Curse of Dimensionality

Key Concept

(1) (2) (p)

When the state is a vector sk = (sk , sk , . . . , sk ), the number of possible states
p
grows as |S| = O(M ), where M is the number of distinct values each component
can take and p is the dimension.
This exponential blow-up in the state space is called the curse of dimensionality
(a term also coined by Bellman).

Σ Math Translation

State dimension p States per stage Tractable?

1 M Yes

2 M2 Usually

3 M3 Challenging

≥5 M 5+ Often intractable

Remark 15.1. Approximate DP, reinforcement learning, and state-aggregation techniques

are used to combat the curse of dimensionality in practice.

16 Applications of Dynamic Programming

DP is one of the most versatile tools in Operations Research and Computer Science.
Below is a (non-exhaustive) list of classic applications.

16.1 Operations Research and Management Science

1. Shortest / Longest Path Problems. Finding optimal routes in networks (road,
communication, project).

2. Resource Allocation. Distributing a limited budget, workforce, or raw material

across competing activities to maximize prot or minimize cost (as in Section 3).

3. Inventory Management. Deciding how much to order each period to balance

holding costs, shortage costs, and ordering costs (WagnerWhitin algorithm).

4. Equipment Replacement. Deciding when to replace an aging machine to mini-

mize total maintenance plus purchase costs over a planning horizon.

5. Production Planning and Scheduling. Determining production quantities per

period to meet demand while minimizing setup, production, and inventory costs.

6. Reliability Optimization. Allocating redundant components to system stages to

maximize overall system reliability subject to weight/cost constraints.
Dynamic Programming in Optimization 21

16.2 Computer Science

1. Knapsack Problem. Selecting items with given weights and values to maximize
total value without exceeding capacity.

2. Sequence Alignment (bioinformatics). Finding the best match between DNA/protein

sequences.

3. Optimal Binary Search Trees. Arranging keys to minimize expected search

time.

4. Matrix Chain Multiplication. Parenthesizing a product of matrices to minimize

scalar multiplications.

5. Edit Distance. Minimum insertions, deletions, and substitutions to transform one

string into another.

16.3 Economics and Finance

1. Optimal ConsumptionSavings. Deciding how much to consume vs. save each
period to maximize lifetime utility.

2. Option Pricing. Binomial-tree models for pricing American options use backward
DP.

3. Markov Decision Processes (MDPs). Stochastic DP for sequential decision-

making under uncertainty (robotics, healthcare, revenue management).

✓ Why This Works

All of these problems share the two DP prerequisites: optimal substructure and over-
lapping sub-problems. Recognizing this structure is the key skill that lets you apply
DP broadly.

17 Practice Problems
17.1 Easy
E1. Staircase. You climb a staircase of n steps. At each step you may go up 1 or 2
stairs. In how many distinct ways can you reach the top? Formulate as a DP and
solve for n = 6.

E2. Coin Row. A row of n coins with values v1 , v2 , . . . , vn is laid out. You may pick
coins, but you cannot pick two adjacent coins. Maximize the total value. Formulate
the recurrence.

E3. Minimum Cost Path. Given a 3 × 3 grid where each cell has a positive cost, nd
the minimum cost path from the top-left corner to the bottom-right corner. You
can only move right or down.
Dynamic Programming in Optimization 22

Cost grid:
 
1 3 1
1 5 1
4 2 1

17.2 Medium
M1. 0/1 Knapsack. A knapsack has capacity W = 7. Items:

Item Weight Value

1 2 10
2 3 14
3 4 18
4 5 22

Find the maximum value subset using DP. Show the full table.

M2. Resource Allocation. A company has 4 units of resource to distribute among

3 projects. The return ri (xi ) for allocating xi units to project i is:

xi r1 r2 r3
0 0 0 0
1 4 2 6
2 6 5 8
3 7 6 10
4 8 8 11

Maximize total return using backward DP.

M3. Shortest Path. Consider the network below. Use backward DP to nd the shortest
path from node 1 to node 7.

2 6 4
3 2
2 4
1 6 7
4
5 5
3 3 5

17.3 Hard
H1. Equipment Replacement. A machine is purchased at the start of year 1. At the
beginning of each year k = 1, 2, 3, 4 you may keep the machine (paying maintenance
cost mk that increases with age) or replace it (paying purchase price P and resetting
age to 0). Given:

P = 10, salvage value at end of year 4 depends on age, m = (2, 4, 7, 11) for ages
1, 2, 3, 4. Salvage values: age 1: 8, age 2: 5, age 3: 3, age 4: 1.

Minimize total net cost over 4 years using DP.

Dynamic Programming in Optimization 23

H2. ProductionInventory. Demand over 4 periods is d = (3, 5, 4, 2). You can pro-
duce up to 6 units per period at cost cp = 2 per unit, plus a xed setup cost of
K=8 whenever production is positive. Holding cost is h=1 per unit per period.
Initial inventory is 0; nal inventory must be 0. Minimize total cost.

H3. Longest Common Subsequence (LCS). Given sequences X = ⟨A, B, C, B, D, A, B⟩

and Y = ⟨B, D, C, A, B, A⟩, nd the length of the LCS and reconstruct it. Write
the DP table.

18 Exam-Level Questions
Q1. (Theory, 10 marks.) State and prove Bellman's Principle of Optimality. Illus-
trate with an example of a 3-stage shortest-path problem.

Q2. (Formulation, 15 marks.) A charitable foundation has $6 million to distribute

among 4 programs. The social impact (in utility units) of allocating x million to
each program is:

x Program A Program B Program C Program D

0 0 0 0 0
1 5 4 6 3
2 9 7 10 7
3 11 9 13 9
4 14 12 15 12
5 16 14 17 14
6 17 16 19 16

(a) Dene stages, states, decisions, and the recurrence relation.

(b) Solve the problem completely using backward DP.

(c) State the optimal allocation and maximum total utility.

Q3. (Shortest Path, 15 marks.) Given the following network with 8 nodes and the
arc costs shown, nd the shortest path from node 1 to node 8 using forward DP.
Draw the network, dene stages, and show all computation tables.

Arc costs: (1, 2) = 4, (1, 3) = 2, (2, 4) = 5, (2, 5) = 3, (3, 4) = 8, (3, 5) = 1,

(4, 6) = 2, (4, 7) = 6, (5, 6) = 7, (5, 7) = 3, (6, 8) = 1, (7, 8) = 4.
Stages: {1}, {2, 3}, {4, 5}, {6, 7}, {8}.
Q4. (Comparison, 8 marks.) Compare and contrast Dynamic Programming with
Linear Programming along the following dimensions: (a) problem structure, (b) so-
lution methodology, (c) types of variables, (d) scalability.

Q5. (Critical Thinking, 12 marks.) A student claims: DP always gives the global
optimum faster than any other method. Critically evaluate this statement. Discuss

(a) conditions under which DP is guaranteed to nd the global optimum,

(b) the curse of dimensionality,

(c) a scenario where LP would be preferred over DP.

Dynamic Programming in Optimization 24

19 Selected Solutions
Solution to E1 (Staircase)
Let W (n) = number of ways to climb n stairs.
Recurrence: W (n) = W (n − 1) + W (n − 2), with W (1) = 1, W (2) = 2.

n 1 2 3 4 5 6

W (n) 1 2 3 5 8 13

There are 13 ways to climb 6 stairs.

Solution to E3 (Minimum Cost Path)

Let C(i, j) = minimum cost to reach cell (i, j) from (1, 1).
Recurrence:


C(i, j) = grid(i, j) + min C(i − 1, j), C(i, j − 1) ,

with C(1, 1) = 1, and boundary: rst row/column accumulated.

Col 1 Col 2 Col 3

Row 1 1 4 5
Row 2 2 7 6
Row 3 6 8 7

Minimum cost path: (1, 1) → (2, 1) → (2, 2) → (2, 3) → (3, 3)? Let us check:
(1, 1) → (1, 2) → (1, 3) → (2, 3) → (3, 3) = 1 + 3 + 1 + 1 + 1 = 7.
Optimal cost = 7. Path: (1, 1) → (1, 2) → (1, 3) → (2, 3) → (3, 3).

Solution to M1 (0/1 Knapsack)

Items: (w1 , v1 ) = (2, 10), (w2 , v2 ) = (3, 14), (w3 , v3 ) = (4, 18), (w4 , v4 ) = (5, 22). Capacity
W = 7.
Stages: k = 1, 2, 3, 4 (one per item).
State: sk = remaining capacity.
Decision: include item k (dk = 1) or not (dk = 0).
Recurrence:

fk∗ (s) = max fk+1

 ∗ ∗
(s), vk + fk+1 (s − wk ) if s ≥ wk , f5∗ (s) = 0.

Stage 4 (w4 = 5, v4 = 22):

s f4∗ (s) d∗4

04 0 0
57 22 1
Dynamic Programming in Optimization 25

Stage 3 (w3 = 4, v3 = 18):

s Candidates f3∗ (s) d∗3

03 skip: f4∗ 0 0
4 skip: 0; take: 18 + f4∗ (0) = 18 18 1
∗
5 skip: 22; take: 18 + f4 (1) = 18 22 0
∗
6 skip: 22; take: 18 + f4 (2) = 18 22 0
∗
7 skip: 22; take: 18 + f4 (3) = 18 22 0

Stage 2 (w2 = 3, v2 = 14):

s Candidates f2∗ (s) d∗2

02 skip: f3∗ 0 0
3 skip: 0; take: 14 + f3∗ (0) = 14 14 1
∗
4 skip: 18; take: 14 + f3 (1) = 14 18 0
∗
5 skip: 22; take: 14 + f3 (2) = 14 22 0
∗
6 skip: 22; take: 14 + f3 (3) = 14 22 0
∗
7 skip: 22; take: 14 + f3 (4) = 32 32 1

Stage 1 (w1 = 2, v1 = 10):

s Candidates f1∗ (s) d∗1

7 skip: 32; take: 10 + f2∗ (5) = 32 32 0 (or 1, tie)

Optimal value = 32.

∗ ∗
Tracing back with d1 = 0 (skip item 1): s2 = 7, d2 = 1 (take item 2): s3 = 7 − 3 = 4,
d∗3 = 1 (take item 3): s4 = 4 − 4 = 0, d∗4 = 0.

Select items 2 and 3: value = 14 + 18 = 32, weight = 3 + 4 = 7 ≤ 7. ✓

Solution to M3 (Shortest Path, 7-node network)

Stages: {1}, {2, 3}, {4, 5}, {6}, {7}.
Using backward DP with f ∗ (7) = 0:

Node Calculation f∗ d∗
7 boundary 0 
6 4+0=4 4 →7
5 → 6 : 7 + 4 = 11; → 7 : 3 + 0 = 3 3 →7
4 → 6 : 2 + 4 = 6; → 7 : 6 + 0 = 6 6 → 6 (tie)
3 → 4 : 8 + 6 = 14; → 5 : 1 + 3 = 4 4 →5
2 → 4 : 5 + 6 = 11; → 5 : 3 + 3 = 6 6 →5
1 → 2 : 4 + 6 = 10; → 3 : 2 + 4 = 6 6 →3
Dynamic Programming in Optimization 26

2 1 3
1→
− 3→
− 5→
− 7, Total cost = 2 + 1 + 3 = 6.

Solution to Q3 (Forward DP, 8-node network)

Dene g ∗ (i) = shortest distance from node 1 to node i.
∗
g (1) = 0 (boundary).

Node Calculation g∗
1 boundary 0
∗
2 g (1) + 4 = 4 4
3 g ∗ (1) + 2 = 2 2
4 min(g ∗ (2) + 5, ∗
g (3) + 8) = min(9, 10) 9
5 min(g ∗ (2) + 3, g ∗ (3) + 1) = min(7, 3) 3
6 min(g ∗ (4) + 2, g ∗ (5) + 7) = min(11, 10) 10
7 min(g ∗ (4) + 6, g ∗ (5) + 3) = min(15, 6) 6
8 min(g ∗ (6) + 1, g ∗ (7) + 4) = min(11, 10) 10

Tracing back: 8 ← 7 ← 5 ← 3 ← 1.

2 1 3 4
1→
− 3→
− 5→
− 7→
− 8, Total cost = 2 + 1 + 3 + 4 = 10.

End of Document