Dynamic Programming

ING3– IA
Computing Faculty - USTHB
Academic year : 2025-26
Dr Daoudi Mourad
[Link]

1.1 Conceptual definition

Dynamic Programming (DP) is an algorithmic design technique based on

the principle of optimality :
“An optimal solution to a global problem can be obtained from the
optimal solutions of its subproblems.”

DP is introduced by Richard Bellman (1957), and revolutionized scientific

computing, operations research, and later artificial intelligence.

DP applies when a problem:

• can be decomposed into recursive subproblems,
• exhibits overlapping subproblems,
• has an optimal substructure (the global optimum can be built from
local optima).
1.2 Bellman’s Principle

If a problem can be expressed in terms of states and decisions, the

optimal value V(s) of a state s satisfies :

V(s) = max a∈A(s) {r(s,a)+V(f(s,a))}

Where:
• A(s): set of actions available in state s
• f(s,a): transition function
• r(s,a): immediate reward or cost
2. Characteristics of Dynamic problems
• The problem can be divided into stages with a policy decision required at each stage.

• Each stage has a number (finite or infinite) of states associated with it.

• The effect of the policy decision at each stage is to transform the current state into a state
associated with the next stage.

• Given the current state, an optimal policy for the remaining stage is independent of the
policy adopted in previous stages ( “ principle of optimality “).

• The solution procedure begins by finding the optimal policy for each state of the last stage.

• A recursive relationships that identifies the optimal policy for each state at stage n is
available, given the optimal policy for each state at stage (n + 1).

• The precise form of the recursive relationship differs somewhat among dynamic problems

• Let : xn be the decision variable at stage n (n=1, 2, … N) , and fn(s, xn) be the
maximizing/minimizing value of the objective function, given that system starts in state s at
stage n and xn is selected,
The recursive relationship will be of the form:
fn*(s) = maxxn / minxn {fn(s, xn)}
where fn(s, xn) would be written in terms of s, xn, fn+1* (.)

• Using the recursive relationship, the solution procedure moves backwards stage by stage.
 Prototype example
Consider the following shortest route problem :

Dynamic Programming starts with a small portion of the problem and finds
the optimal solution for this smaller problem.
It then gradually enlarges the problem, finding the current optimal solution
from the previous one, until the original problem is solved in its entirety.
Let’s characterize : xn, fn(s, xn) , xn* , fn*(s) , n=1, 2, 3, 4

• the decision variable xn, (n=1, 2, 3, 4) , represents the immediate destination on

stage n.
The route selected would be : 1→ x1 → x2 → x3 → x4 ; x4 =10.
• fn(s, xn) is the total cost of the best overall policy for the remaining stages, given
that we are in state s and xn is selected as the immediate destination.
• Given s and n, let xn* denote the value of xn that minimizes fn (s, xn), and let
fn*(s) = min fn(s, xn)
We have: fn*(s) = fn(s, xn*)

The objective is to find successively f4*(s), f3*(s), f2*(s) , f1*(s) and the corresponding
policy.

For the nth stage problem we’ll use the following table:
The one stage problem: s f4*(s) x4*
The two stage problem:
The three stage problem:
The for stage problem:
Summary:

Finally the optimal policy : 1 → 3 → 5 → 8 → 10 with cost : 11

An other optimal policy : 1 → 4 → 5 → 8 → 10 with cost : 11
An other optimal policy : 1 → 4 → 6 → 9 → 10 with cost : 11
 Example 2

• Five medical teams are available to allocate among three countries to improve their medical
care. The measure of effectiveness being used is additional man-years of life (table below) :
• t

Thousands of additional
man-years of life
Nb of medical Country
teams 1 2 3
0 0 0 0
1 45 20 50
2 70 45 70
3 90 75 80
4 105 110 100
5 120 150 130

Problem: Determine how many teams to allocate to each of these countries to maximize the
total effectiveness of the five teams (use a dynamic programming formulation).
• Stages:
Let the stage n defined by the country n (n=1, 2, 3), to have three interrelated
decisions: how many medical teams to allocate to each of the three countries.

• Decision variables xn :
Let xn (n=1,2,3) be the number of teams to allocate to stage (country) n.

• States:
To define the different states, we have to ask questions such as:
– What is that changes from one stage to another ?
– Given that the decisions have been made at the previous stages, how to describe the status of the
situation at the current stage ?
– What information about the current state is necessary to determine the optimal policy hereafter ?
We define the state of the system as the number of medical teams not already
allocated at previous stages.
The recursive relationship
• Let pi(xi) be the effectiveness from allocating xi medical teams to country i.
The problem is: Max ∑ pi(xi)
∑ xi = 5
We have: For n = 1, 2,xi3 ≥ 0 , integers , i=1,2,3 3
fn(s, xn) = pn(xn) + max ∑ pi(xi) ,
i=n+1
3
st : ∑ xi = s
i=n
xi ≥ 0 , integers , i=1,2,3

In addition: fn*(s) = max fn(s, xn)

xn = 0, 1, …., s

Therefore : fn(s, xn) = pn(xn) + fn+1*(s - xn) , with f4* = 0

Summary: The recursive relationship is

fn*(s)= max {pn(xn) + fn+1*(s - xn) }, n= 1, 2

xn = 0, 1, …, s

For n = 3: f3*(s)= max {p3(x3) }

x3 = 0, 1, …, s
n=3
The optimal solution :
x1* = 1, which makes s = 5-1 = 4 for n=2,
so x2* = 3, which makes s = 4-3 = 1 for n=1.

(1, 3, 1) allocation is optimal with f1*(5)=170