Chapter Four

Dynamic Programming

Elias Debelo
[Link]@[Link]
Click to edit Master subtitle style

Haramaya University
Click to edit Master subtitle style
Dynamic Programming (DP)?
▪ “Programming” in this context refers to a tabular method, not to writing
computer code.
▪ Dynamic programming is an algorithm design method that can be used when
the solution to a problem can be viewed as the result of a sequence of
decisions.
▪ For some of the problems that may be viewed in this way, an optimal
sequence of decisions can be found by making the decisions one at a time
and never making an erroneous decision.

▪ This is true for all problems solvable by the greedy method. For many
problems it is not possible to make stepwise decisions in such a manner that
the sequence of decisions made is optimal.

7/18/2022 Dynamic Programming 2

DP Cont.
▪ One way to solve problems for which it is not possible to make a sequence
of stepwise decisions leading to an optimal decision sequence is to try all
possible decision sequences.

▪ We could enumerate all decision sequences and then pick out the best.
But the time and space requirements may be prohibitive.

▪ Dynamic programming often drastically reduces the amount of

enumeration by avoiding the enumeration of some decision sequences that
cannot possibly be optimal.

▪ In dynamic programming an optimal sequence of decisions is obtained by

making explicit appeal to the principle of optimality.
7/18/2022 Dynamic Programming 3
DP Cont.
▪ Principle of Optimality
States that an optimal sequence of decisions has the
property that whatever the initial state and decisions are,

the remaining decisions must constitute an optimal decision

sequence with regard to the state resulting from the first decision.

▪ No erroneous decicions

7/18/2022 Dynamic Programming 4

DP Cont.
▪ A dynamic-programming algorithm solves each sub-subproblem just once
and then saves its answer in a table, thereby avoiding the work of
recomputing the answer every time it solves each sub-subproblem.

▪Dynamic programming applies when the subproblems

overlap-that is, when subproblems share sub-subproblems.

▪ It takes advantage of overlapping subproblems by solving each subproblem

once and then storing the solution in a table where it can be looked up when
needed, using constant time per lookup.

7/18/2022 Dynamic Programming 5

DP Cont.
▪ When we think about a dynamic-programming problem, we should
understand the set of subproblems involved and how subproblems depend on
one another.

▪ The two key ingredients that an optimization problem must have in order for
dynamic programming to apply: optimal substructure and overlapping
subproblems.

▪ The first step in solving an optimization problem by dynamic programming is

to characterize the structure of an optimal solution. Whenever a problem
exhibits optimal substructure, we have a good clue that dynamic
programming might apply.

7/18/2022 Dynamic Programming 6

DP Cont.
▪Overlapping subproblems: the space of subproblems must be
“small” in the sense that a recursive algorithm for the problem
solves the same subproblems over

and over, rather than always generating new subproblems.

▪ When a recursive algorithm revisits the same problem repeatedly, we say

that the optimization problem has overlapping subproblems.

7/18/2022 Dynamic Programming 7

E.g., Fibonacci Numbers
Algorithm Fib(n)
{
if n<=2 then return 1;
else return Fib(n-1) + Fib(n-2);
}
▪ Fib(5) = 5th Fibonacci number = 5

▪ Exercise: Draw tree for Fib(8)

7/18/2022 Dynamic Programming 8

Cont.
▪ We need to avoid computing the same subproblems again and again;
▪ If we re-use Fib(1), Fib(2) and Fib(3)
Instead or re-computing we can reduce
the computation time from O(2n) to
O(n), linear time.
How many function call, for n=5, 10, 100?
▪
Store the results for latter use;
n = 1 2 3 4 5
A[n] = 1 1 2 3 5

7/18/2022 Dynamic Programming 9

Generally,
▪When developing a dynamic-programming algorithm, we follow a
sequence of four steps:
1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution, typically in a bottom-
up fashion.
4. Construct an optimal solution from computed information.
▪ In greedy methods, we must follow optimal predefined procedures to get
optimal solution.
▪ In daynamic programming, try all possible solution (all feasible solutions)
and pick the best. It uses tabulation technique to avoid over computing.

7/18/2022 Dynamic Programming 10

Multistage Graph
▪Multistage graph G = (V, E) is a directed graph in which the
vertices are partitioned into k>=2 disjoint sets Vi, 1<=i<=k. If
(u, v) is an edge in E, then u ε Vi and v ε Vi+1 for some i, 1<=i<k.

▪ The sets V1 and Vk are such that | V1|=|Vk|=1; meaning that,

Let s and t be the vertex in V1 and Vk respectively, then vertex s
is the source, and t the sink.

▪ Let c(i, j) be the cost of edge (i, j).The cost of a path from s to
t is the sum of the costs of the edges on the path.

7/18/2022 Dynamic Programming 11

Cont.
▪The multistage graph problem is to find a minimum-cost path
from s to t. Each set Vi defines a stage in the graph.

▪ Because of the constraints on E, every path from s to t starts in

stage 1, goes to stage 2, then to stage 3, etc., and eventually
terminates in stage k.

7/18/2022 Dynamic Programming 12

Cont.
▪ A dynamic programming formulation for a k-stage graph problem is
obtained by using the principle of optimality.

▪ According to this principle, a path (i, k) is said to be optimal if and only

if the intermediate paths (i, j) and (j, k) are also optimal.

▪ The multistage graph problem has two approaches namely, forward and
backward.

▪ By using the forward approach, we obtain the cost of a path (i, j) which is
given by the following equation:

7/18/2022 Dynamic Programming 13

Cont.

▪ Here cost (i, j) means i th level and the cost of edge from j th vertex to the
last vertex.
▪ Forward approach and backward approach:
✓ Note that if the recurrence relations are formulated using the forward
approach then the relations are solved backwards. i.e., beginning with the
last decision.
✓ On the other hand if the relations are formulated using the backward
approach, they are solved forwards.

7/18/2022 Dynamic Programming 14

E.g., Forward Approach
Cost of the last stage, the sink is:
Cost(5,9) = 0, then,
4th stage
Cost(4,7)=min{cost(5,9)+c(7,9)}
=0+7 = 7
Cost(4,8)=min{cost(5,9)+c(8,9)}
=0+3 = 3

5 stage graph

7/18/2022 Dynamic Programming 15

E.g., Forward Approach
3rd stage
1. Cost(3,4)
= min{cost(4,7)+c(4,7), cost(4,8) +c(4,8)}
= {7+1, 3+4}=7
2. Cost(3,5)
=min{cost(4,7)+c(5,7),cost(4,8)+c(5,8)}
={7+6, 3+2}=5
3. Cost(3,6)
=min{cost(4,7)+c(6,7),cost(4,8)+c(6,8)}
={7+6, 3+2}=5

7/18/2022 Dynamic Programming 16

E.g., Forward Approach
2th stage
1. Cost(2, 2)
=min{cost(3,4)+c(2,4),cost(3,6)+c(2,6)}
={7+3, 5+3}=8

2. Cost(2,3)
=min{cost(3,4)+c(3,4), cost(3, 5)+c(3,5),
cost(3,6)+c(3,6)} = {7+6, 5+5, 5+8}=10

7/18/2022 Dynamic Programming 17

E.g., Forward Approach
1st stage
Lastly, Cost(1, 1)
=min{cost(2, 2)+c(1,2), cost(2, 3)+c(1, 3)}
= {8+5, 10+2}=12

Therefore, a minimum cost path in

forward approach is via 1, 3, 5, 8, 9 with
cost 12

7/18/2022 Dynamic Programming 18

E.g., Backward Approach;
▪ Let bp(i, j) be a minimum-cost path from vertex s to a vertex j in
Vi. let bcost(i, j) be the cost of bp(i, j). From the backward
approach we obtain:
bcost(i, j) = min {bcost(i-1, l) + c(l, j)}
l Є Vi-1 and <l, j> Є E
▪ Since bcost(2, j) = c(1, j) if (1, j) Є E and bcost(2, j) = ∞
if (1, j) ∉ E.
▪Now, bcost(i, j) can be computed from the above formula, by
computing bcost for i=3, then i=4 and so on.

7/18/2022 Dynamic Programming 19

E.g., Backward Approach
2th stage
1. bcost(2, 2) = c(1, 2) = 5
2. bcost(2, 3) = c(1, 3) = 2
Now, calculate next stage, third, i=3
1. bcost(3,4) = min{bcost(2, 2) + c(2,
4), bcost(2, 3) + c(3, 4)} = {5+3,
2+6}=8
2. bcost(3, 5)=min{bcost(2, 3)+c(3,5)}
= {2+5} = 7

7/18/2022 Dynamic Programming 20

E.g., Backward Approach
3. bcost(3, 6)=min{bcost(2, 2)+c(2, 6),
bcost(2, 3)+c(3, 6)} = {2+8, 5+3} = 8
4th stage
1. bcost(4, 7)=min{bcost(3, 4)+c(4, 7),
bcost(3, 5)+c(5, 7), bcost(3, 6)+c(6,
7)} ={8+1, 7+6, 8+6} = 9
2. bcost(4, 8)=min{bcost(3,4)+c(4, 8),
bcost(3, 5)+c(5, 8), bcost(3, 6)+c(6,
8)}= {8+4, 7+2, 8+2} = 9

7/18/2022 Dynamic Programming 21

E.g., Backward Approach
5th stage
1. bcost(5, 9) = min{bcost(4, 7)+c(7, 9),
bcost(4, 8)+c(8, 9)}
= {9+6, 9+3} = 12
 Backward minimum-cost from source
to destination is 12, via 1, 3, 5, 8, 9
 The backward and forward may not be
the same, in some cases. In
bidirectional graph if each edge have
different edge-cost.

7/18/2022 Dynamic Programming 22

The Travelling Salesperson Problem (TSP)
▪Let G = (V, E) be a directed graph with edge costs Cij, the
variable Cij is defined such that Cij >0 for all i and j and Cij = ∞
if (i, j) ∉ E. (no path)
▪Let |V|=n and assume n>0.
▪A tour is the sum of the cost of the edges on the tour.
The traveling salesperson problem is to find a tour of
minimum costs. E.g.,
Postal van pick up mail from mail boxes located at n different sites. An n + 1
vertex graph can be used to represent the situation. One vertex represents the post
office from which the postal van starts and to which it must return. Edge (i, j) is
assigned a cost equal to the distance from site i to site j. The route taken by the
postal van is a tour, and we are interested in finding a tour of minimum length.
7/18/2022 Dynamic Programming 23
Cont.
▪A tour to be a simple path that starts and ends at vertex 1.
▪ Every tour consists of an edge (1, k) for some k Є V-{1} and a
path from vertex k to vertex 1.

▪ The path from vertex k to vertex 1 goes through each vertex in

V-{1, k} exactly once. The principle of optimality holds, if
the tour is optimal.

▪ Now, let g(i, S) be the length of the shortest path starting

at vertex i, going through all vertices in S, and terminating
at vertex 1.
7/18/2022 Dynamic Programming 24
Cont.
▪ The function g(1, V-{1}) is the length of an optimal salesperson
tour. From principle of optimality is follows that;
g(1, V-{1}) = min{C1k + g(k, V-{1, k})}, 2<=k<=n
▪ Equation above can be generalized, when i ∉ S,
g(i, S) = min{Cij + g(j, S-{j})}, j Є S
▪ From above g(i, Ø) = Ci1, 1<=i<=n. Hence we can use second
equation to obtain g(i, S) for all S of size 1. Then we can obtain
g(i, S) for S with |S|=2 and so on.
▪ When |S| < n-1, the value of i and S for which the g(i, S) is
needed are such that; i ≠ 1, 1 ∉ S and i ∉ S.

7/18/2022 Dynamic Programming 25

Meaning:
▪ Let S = V = {A, B, C, D} be set of vertices
g(i, S) = min{Cij + g(j, S-{j})}, j Є S
▪ If we start from A, we will visit all vertices other
than A, that is {A, B, C, D} – {A} or S-{A} then 7
2
we will come back to A, making a cycle.
6

▪ g(A, {B, C, D}) = min{CAB + g(B, {C, D}), CAC + g(C, {B, D}),
CAD + g(D, {B, C})}
Remember: CAC = CAD = ∞ because no edge between A to D & C, so reject
CAC + g(C, {B, D} & CAD + g(D, {B, C}) path because it is not minimum.
7/18/2022 Dynamic Programming 26
Cont.
▪g(A, {B, C, D}) = min{CAB + g(B, {C, D})}
Now, we can expand each and decide which rout we
should take.
▪ g(B, {C, D}) = min{CBC + g(C, {D}), CBD + g(D, {C})}
▪ g(C, {D}) = min{CCD + g(D, Ø)}
▪ g(D, Ø) = CDA = 5 (base case for g(B, {C, D})
▪What will happen to g(D, {B, C})?
Rejected, because no edge CDB = CDC = ∞, g(D, {B, C}) is
going to be infinite again.

7/18/2022 Dynamic Programming 27

TSP Example

7/18/2022 Dynamic Programming 28

Cont.
▪The base cases, that connect every other to A are;
g(2, Ø), g(3, Ø), and g(4, Ø).
▪ g(2, Ø) = C21 = 5, g(3, Ø)= C31 = 6, g(4, Ø) = C41 = 8

▪ Now, we calculate when a set size is one, |S|=1.

1. g(2, {3}) = C23 + g(3, Ø) = 9+6 = 15
2. g(2, {4}) = C24 + g(4, Ø) = 10+8 = 18
3. g(3, {2}) = C32 + g(2, Ø) = 13+5 = 18
4. g(3, {4}) = C34 + g(4, Ø) = 12+8 = 20
5. g(4, {2}) = C42 + g(2, Ø) = 8+5 = 13
6. g(4, {3}) = C43 + g(3, Ø) = 9+6 = 15
7/18/2022 Dynamic Programming 29
Cont.
▪Next, we compute g(i, S) with |S| = 2, i ≠ 1, 1 ∉ S and i ∉ S.
1. g(2, {3, 4}) = min{C23 + g(3, {4}), C24+g(4, {3})} = {9+20, 10+15}=25
2. g(3, {2, 4}) = min{C32 + g(2, {4}), C34+g(4,{2})} = {13+18, 12+13}=25
3. g(4, {2, 3}) = min{C42 + g(2, {3}), C43+g(3, {2})} = {8+15, 9+18}=23

One last step when the size of the set is |V|-1 or |S| = 3; that is
g(1, {2, 3, 4}) = min{C12 + g(2, {3, 4}), C13 + g(3, {2, 4}),
C14 + g(4, {2, 3})}
= min{10 + 25, 15 + 25, 20 + 23} = min{35, 40, 43} = 35
▪ The tour it through vertices 1, 2, 4, 3, 1 and edges C12, C24, C43, C31
The complexity of tour is n22n this is still better than
enumerating all n!
7/18/2022 Dynamic Programming 30
String Editing: Using DP
▪We are given two strings X=x1, x2, x3… xk and Y=y1, y2, y3,
… ym where xk, 1<=i=< n, and yj, 1<=j=< m, are members of a
finite set of symbols known as the alphabet.
▪ We want to transform X into Y using a sequence of edit
operations on X.
▪ The permissible edit operations are insert, delete, and change
(symbol of X into another),and there is a cost associated with
performing each.
▪The cost of a sequence of operations is the sum of the costs of the
individual operations in the sequence.
▪The problem of string editing is to identify a minimum-cost
sequence of edit operations that will transform X into Y.
7/18/2022 Dynamic Programming 31
Cont.
▪ Let D(xi) be cost of deleting symbol xi from X, I(yj) be cost of inserting
symbol yj into X, and C(xi, yj) be cost of changing symbol xi of X into yj.
E.g., X=(x1, x2, x3, x4, x5)=(a, a, b, a, b) and Y=(y1, y2, y3, y4)=(b, a, b, b)

▪ And let cost associated with insertion and deletion be 1 and cost of
changing any symbol to another symbol be 2.
▪ Some of possible ways of transforming X to Y are:
1. Delete all X, and insert all Y. Which costs 5 (deletion) + 4
(insertion)=9.
2. Delete X1 and X2, and insert Y4 at the end of X. Costs 2+1 = 3
3. Change X1 to Y1, and Delete X4. Costs 2 (for changing)+1 = 3

7/18/2022 Dynamic Programming 32

Cont.
▪ So, our aim is to find minimum sum of cost of
transformation.

▪It can be solved by dynamic programming because

solution to string editing problem consists of sequence
of decisions, one for each edit operation.

7/18/2022 Dynamic Programming 33

Cont.
▪ Cost(i, j) be the minimum cost of any edit sequence for transforming x1, x2,
…, xi to y1, y2, …, yj, for 0<=i<=n and 0<=j<=m.
▪ After computing cost(i, j) for each i and j, then, cost(n, m) is the cost of an
optimal edit sequence.
▪ Now, if
1. i = j = 0, cost(i, j) = 0, the two sequence are equal and empty.
2. j=0 and i > 0, transform X to Y by sequence of delete
operation only. Thus, cost(i, j) = cost(i-1, 0) + D(Xi).
3. j > 0 and i=0, transform X to Y by sequence of insert. Thus,
cost(0, j) = cost(0, j-1) + I(Yj).
4. j ≠ 0 and i ≠ 0, the sequence of transformation could be one
of the following three ways.

▪ 7/18/2022 Dynamic Programming 34

Cont.
▪ When j ≠ 0 and i ≠ 0, cost of transforming X to Y using minimum-cost
edit sequence could be:
1. Delete Xi, corresponds to cost(i-1, j) + D(Xi).
2. Changing symbol Xi to Yj, which corresponds to cost(i-1, j-1) + C(Xi, Yj)
3. Insert Yj, this corresponds to cost(i, j-1) + I(Yj).
▪ The minimum-cost edit of any edit sequence that transform X to Y, in the
above, where both are nonempty is minimum cost according to principle of
optimality. The recurrence equation is:

7/18/2022 Dynamic Programming 35

Cont.
▪To compute cost(i, j) for all i and j, where 0<=i<=n and
0<=j<=m. There are (n+1)(m+1) such values.

▪ This can be computed in the form of table, M. Where each

row of M corresponds to particular value of i and each
column of corresponds to specific value of j. So, M(i, j) store
value of cot(i,j).

▪ Zeroth row computed first as it perform a series of

insertions. Likewise, zero column performs a series of
deletions.
7/18/2022 Dynamic Programming 36
Cont.
▪ Then start computing either column-major or row-
major order. The latter, starts computing cost(1,1), cost(1,
2), …, cost(n, m).

▪ Now, let us consider row-major order, along increasing

of column numbers.

7/18/2022 Dynamic Programming 37

To Simplify;
▪ C(Xi,Yj) = 0, if Xi=Yj (same symbol), means that no modification. If not
equal, you will take the cost of operation (given).
For example in our example the cost of changing Xi to Yj is 2, C(Xi,
Yj) = 2. Likewise, D(Xi) = I(Yj) = 1.
▪ The recurrence equation above is ordered as Delete, Change and Insert.
▪ Or cost(i, j) = min{cost of Delete, cost of change, cost of insert}
---------------------------------------------------------------------------------------

7/18/2022 Dynamic Programming 38

Cont.
▪ cost(1, 3)=min{cost(0, 3)+D(x1),
cost(0, 2)+C(x1, y3), cost(1, 2)+I(y3)}
= min{3+1, 2+2, 1+1} = 2
▪ cost(1, 4)=min{cost(0, 4)+D(x1),
cost(0, 3)+C(x1, y4), cost(1, 3)+I(y4)}
= min{4+1, 3+2, 2+1} = 3
Second Row
▪ Cost(2, 1) )=min{cost(1, 1)+D(x2),
cost(1, 0)+C(x2, y1), cost(1, 3)+I(y4)}
= min{2+1, 1+2, 2+1} = 3

7/18/2022 Dynamic Programming 39

Cont.
▪ Last cost, cost(n, m) = cost(5, 4) is the final answer.
▪ After computing all entries of M, the minimum edit sequence can be found
by backward tracing from cost(n, m).
▪ This backward trace enabled by recording which of the three options
(delete, change, insert) for i>0 and j>0 yielded the minimum cost for each i
and j.
▪ For example: cost(5, 4)
is from cost(5, 3) which yield insertion of Y4
at end of X.
Then, following the path, cost(2, 0) comes
from cost(1, 0)+D(x2), where cost(1, 0) is
In turn D(x1).
▪ Sequence is D(x1), D(x2) and I(Y4) = 3
7/18/2022 Dynamic Programming 40
Cont.
▪ Each operation can be performed O(1) times.
▪ Thus, there are (n+1)(m+1) possible values of i and j, String editing could
take O(mn) time.

7/18/2022 Dynamic Programming 41

E.g. 2
▪ Find a minimum-cost edit sequence for transforming string X to Y.
And also show sequence of operations performed.
▪ X=(x1, x2, x3) = (A, A, B) and
▪ Y=(y1, y2, y3) = (A, B, A)
-------------------------------------------------------------------------------------------
Cost(1, 1) =

7/18/2022 Dynamic Programming 42

 End of Chapter
Click to edit Master subtitle style

Click to edit Master subtitle style