DYNAMIC

PROGRAMMING
Principles
Identify small number of sub-problems
solve them
Assumption: solution to subproblem is sufficient to compute solution to larger
sub-problem

Can now solve larger sub-problems (given the solutions of smaller sub-
problems)

Finally, we arrive at the final solution to the problem.

The relationship between the larger and smaller is expressed as a recursive

relationship

This leads to a table filling algorithm, where each entry in table corresponds
to the optimal solution to the sub-problem
• Key is to get/identify the sub-problems right
Steps in Dynamic Programming
1. Characterize structure of an optimal solution.
2. Define value of optimal solution recursively.
3. Compute optimal solution values either top-down with
caching or bottom-up in a table.
4. Construct an optimal solution from computed values.
Dynamic Programming..
• DP reduces computation by
• Solving subproblems in a bottom-up fashion.
• Storing solution to a subproblem the first time it is
solved.
• Look-up the solution when subproblem is encountered
again.
• Key: determine structure of optimal solutions
Finding Cost to convert a substring to another
Levenshtein distance

Operations (cost)
Insert m[i, j-1] + 1

Delete m[i-1, j] + 1

Replace m[i-1, j-1] + 1

Copy m[i-1, j-1], s1[i]=s2[j]

C[i,j] = min {m[i, j-1] + 1, m[i-1, j] + 1, m[i-1, j-1] + 1} if s1[i]≠s2[j]

min {m[i, j-1] + 1, m[i-1, j] + 1, m[i-1, j-1] } if s1[i]=s2[j]
 7

Levenshtein distance: Algorithm

7
Levenshtein distance: Algorithm

8
Levenshtein distance: Algorithm

9
Levenshtein distance: Algorithm

10
Levenshtein distance: Algorithm

11
Creating change using Dynamic Programming
Suppose we have denominations Re1, Rs 4, Rs 5.
We want to pay Rs 8
Pay using greedy approach which picks up the maximum feasible
denomination at every iteration.

How many coins do you require using this approach?

But optimal solution is two coins <4, 4>.

Constructing the Optimal solution
• We want minimum coins as possible:
C[i, j] = min {C[i – 1, j] , 1 + C[i, j – di]}
Constructing the Optimal solution
C[i, j] = 1 + C[1, j – d1] if i=1
, 1 + C[i, j – di] if di = j
, C[i-1, j] if j<di
,min {C[i – 1, j] , 1 + C[i, j – di]} otherwise
Example
Total to be paid: Rs 8. Denominations: 1,4,6

j= 0 j=1 2 3 4 5 6 7 8

i=0 0 0 0 0 0 0 0 0 0
i=1 d1 0 1 2 3 4 5 6 7 8
i=2 d4 0 1 2 3 1 2 3 4 2
i=3 d6 0 1 2 3 1 2 1 2 2
0/1 Knapsack Problem: Formal description

(of items to take)

0/1 Knapsack: Solution
• Let i be the highest-numbered item in an optimal solution
S for W pounds. Then S’ = S - {i} is an optimal solution for
W - wi pounds and the value to the solution S is Vi plus the
value of the subproblem.
• We can express this fact in the following formula: define
c[i, j] to be the solution for items 1,2, . . . , i and maximum
weight w. Then
0 if i = 0 or j = 0
c[i,j] = c[i-1, j ] if j<wi
max [vi + c[i-1, j-wi], c[i-1, j]} if i>0 and
j ≥ wi
0/1 Knapsack: Solution
• This says that the value of the solution to i items either
include ith item,
• in which case it is vi plus a subproblem solution for (i - 1) items and
the weight excluding wi, or
• does not include ith item, in which case it is a subproblem's solution
for (i - 1) items and the same weight.
• That is, if the thief picks item i, thief takes vi value, and
thief can choose from items j - wi, and get c[i - 1, j- wi]
additional value.
• On other hand, if thief decides not to take item i, thief can
choose from item 1,2, . . . , i- 1 upto the weight limit j, and
get c[i - 1, j] value. The better of these two choices should
be made.
Activity
Solve the problems given to you and arrive at the optimal
solution
e.g. For three items: W= {2,3,4}, V={4,5,6}
M (knapsack capacity)= 7
wi vi j= 0 j=1 2 3 4 5 6 7

i=0 0 0 0 0 0 0 0 0
i=1 w1 = 2 v1 = 4 0

i=2 w2 = 3 v2 = 5 0
i=3 w3 = 4 v3 = 6 0
Activity
Solve the problems given to you and arrive at the optimal
solution
e.g. For three items: W= {2,3,4}, V={4,5,6}
M (knapsack capacity)= 7
wi vi j= 0 j=1 2 3 4 5 6 7

i=0 0 0 0 0 0 0 0 0
i=1 w1 = 2 v1 = 4 0

i=2 w2 = 3 v2 = 5 0
i=3 w3 = 4 v3 = 6 0
Activity
Solve the problems given to you and arrive at the optimal
solution
e.g. For three items: W= {2,3,4}, V={4,5,6}
M (knapsack capacity)= 7
wi vi j= 0 j=1 2 3 4 5 6 7

i=0 0 0 0 0 0 0 0 0
i=1 w1 = 2 v1 = 4 0

i=2 w2 = 3 v2 = 5 0
i=3 w3 = 4 v3 = 6 0

max vi + c[i-1, j-wi] OR c[i-1, j] if i>0 and

j ≥ wi
weight excluding wi do not select
Example
Solve the problems given to you and arrive at the optimal
solution
e.g. For three items: W= {2,3,4}, V={4,5,6}
M (knapsack capacity)= 7
wi vi j= 0 j=1 2 3 4 5 6 7

i=0 0 0 0 0 0 0 0 0
i=1 w1 = 2 v1 = 4 0 0

i=2 w2 = 3 v2 = 5 0 0
i=3 w3 = 4 v3 = 6 0 0

max vi + c[i-1, j-wi] OR c[i-1, j] if i>0 and

j ≥ wi
weight excluding wi do not select
Example
Solve the problems given to you and arrive at the optimal
solution
e.g. For three items: W= {2,3,4}, V={4,5,6}
M (knapsack capacity)= 7
wi vi j= 0 j=1 2 3 4 5 6 7

i=0 0 0 0 0 0 0 0 0
i=1 w1 = 2 v1 = 4 0 0

i=2 w2 = 3 v2 = 5 0 0
i=3 w3 = 4 v3 = 6 0 0

Tracing Back: Problem Size j=7

i=3 and j=7
Dynamic-0-1-knapsack (v, w, n, W)
for w  0 to W
do c[0, w]  0
for i1 to n
do c[i, 0]  0
for w1 to W
do if wi ≤ w
then if vi + c[i-1, w-wi] > c[i-1, w]
then c[i, w]  vi + c[i-1, w-wi]
keep[i,w]  1
else c[i, w]  c[i-1, w]
keep[i,w] 0
else c[i, w] = c[i-1, w]
keep[i,w]  0
Analysis
• This dynamic-0-1-kanpsack algorithm takes θ(nw) times,
broken up as follows: θ(nw) times to fill the c-table, which
has (n +1).(w +1) entries, each requiring θ(1) time to
compute. O(n) time to trace the solution, because the
tracing process starts in row n of the table and moves up
1 row at each step.
ALL PAIRS SHORTEST
PATH (FLOYD-
WARSHALL)
The Floyd Warshall Algorithm is an all pair shortest path algorithm
Dijkstra and Bellman Ford: are single source shortest path algorithms.

It is an optimization problem that can be solved using dynamic programming.

Principle of optimality
If k is the node on the shortest path from i to j, then the path from i to k and k to j,
must also be shortest.

In the following figure, the optimal path from i to j is either

p
or
summation of p1 and p2.
 How many intermediate nodes?
• The shortest path between i to j will have some k number
of intermediate nodes.

• floyd warshall algorithm, treats each and every vertex

from 1 to N as an intermediate node one by one.
Optimal Solution
Let G = <V, E> be a directed graph, where V is a set of vertices ad

E is a set of edges with nonnegative length.

Construct a matrix L
L = Matrix, which gives the length of each edge

L[i, j] = 0, if i == j // Distance of node from itself is zero

L[i, j] = ∞ , if i ≠ j and (i, j) ∉ E // There is no edge

L[i, j] = w (i, j), if i ≠ j and (i, j) ∈ E // w(i, j) is the weight of the edge (i, j)
Example
Graph G(V,E)

2 Construct L
1
2

3 7

1
3 4

6
Example
Optimal Solution: Updating the matrix
While considering kth vertex as intermediate vertex, there are two possibilities :

If k is not part of shortest path from i to j, we keep the distance D[i, j] as it is.

If k is part of shortest path from i to j, update distance D[i, j] as

D[i, k] + D[k, j].

Optimal sub structure of the problem is given as :

Dk [i, j] = min{ Dk – 1 [i, j], Dk – 1 [i, k] + Dk – 1 [k, j] }

Dk = Distance matrix after kth iteration

Example
Graph G(V,E)

2 Construct L
1
2

3 7

1
3 4

Solution:
Optimal substructure formula for Floyd’s algorithm,

Dk [i, j] = min { Dk – 1 [i, j], Dk – 1 [i, k] + Dk – 1 [k, j] }

 Dk [i, j] = min { Dk – 1 [i, j], Dk – 1 [i, k] + Dk – 1 [k, j] }

Iteration 1 : k = 1 :
D1[1, 2] = min { Do [1, 2], Do [1, 1] + Do [1, 2] }
= min {∞, 0 + ∞}
= ∞

D1[1, 3] = min { Do [1, 3], Do [1, 1] + Do [1, 3] }

= min {3, 0 + 3}
=3

D1[1, 4] = min { Do [1, 4], Do [1, 1] + Do [1, 4] }

= min {∞, 0 + ∞}
= ∞
 Dk [i, j] = min { Dk – 1 [i, j], Dk – 1 [i, k] + Dk – 1 [k, j] }
Iteration 1 : k = 1 :

D1[2, 1] = min { Do [2, 1], Do [2, 1] + Do [1, 1] }

= min {2, 2 + 0}
=2

D1[2, 3] = min { Do [2, 3], Do [2, 1] + Do [1, 3] }

= min {∞, 2 + 3}
=5

D1[2, 4] = min { Do [2, 4], Do [2, 1] + Do [1, 4] }

= min {∞, 2 + ∞}
=∞
D1[3, 1] = min { Do [3, 1], Do [3, 1] + Do [1, 1] }
= min {∞, ∞ + 0}
=∞

D1[3, 2] = min { Do [3, 2], Do [3, 1] + Do [1, 2] }

= min {7, ∞ + ∞}
=7

D1[3, 4] = min { Do [3, 4], Do [3, 1] + Do [1, 4] }

= min {1, ∞ + ∞}
=1
D1[4, 1] = min { Do [4, 1], Do [4, 1] + Do [1,
1] }
= min {6, 6 + 0}
=6

D1[4, 2] = min { Do [4, 2], Do [4, 1] + Do [1,

2] }
= min {∞, 6 + ∞}
=∞

D1[4, 3] = min { Do [4, 3], Do [4, 1] + Do [1,

3] }
= min {∞, 6 + 3}
=9
Update Matrix

Note : Path distance for highlighted cell is improvement over original matrix.
Iteration 2 (k = 2) :

D2[1, 2] = min { D1 [1, 2], D1 [1, 2] + D1 [2, 2] }

= min {∞, ∞ + 0}
= ∞

D2[1, 3] = min { D1 [1, 3], D1 [1, 2] + D1 [2, 3] }

= min {3, ∞ + 5}
=3

D2[1, 4] = min { D1 [1, 4], D1 [1, 2] + D1 [2, 4] }

= min {∞, ∞ + ∞}
=∞
Iteration 2 (k = 2) :

D2[2, 1] = min { D1 [2, 1], D1 [2, 2] + D1 [2, 1] }

= min {2, 0 + 2}
=2

D2[2, 3] = min { D1 [2, 3], D1 [2, 2] + D1 [2, 3] }

= min {5, 0 + 5}
=5

D2[2, 4] = min { D1 [2, 4], D1 [2, 2] + D1 [2, 4] }

= min {∞, 0 + ∞}
= ∞
Iteration 2 (k = 2) :

D2[3, 1] = min { D1 [3, 1], D1 [3, 2] + D1 [2,

1] }
= min {∞, 7 + 2}
=9

D2[3, 2] = min { D1 [3, 2], D1 [3, 2] + D1 [2,

2] }
= min {7, 7 + 0}
= 7

D2[3, 4] = min { D1 [3, 4], D1 [3, 2] + D1 [2,

4] }
= min {1, 7 + ∞}
=1
Iteration 2 (k = 2) :

D2[4, 1] = min { D1 [4, 1], D1 [4, 2] + D1 [2, 1] }

= min {6, ∞ + 2}
=6

D2[4, 2] = min { D1 [4, 2], D1 [4, 2] + D1 [2, 2] }

= min {∞, ∞ + 0}
=∞

D2[4, 3] = min { D1 [4, 3], D1 [4, 2] + D1 [2, 3] }

= min {9, ∞ + 5}
=9
Update Matrix
Iteration 3 (k = 3) :
D3[1, 2] =
min { D2 [1, 2], D2 [1, 3] + D2 [3, 2] }
= min {∞, 3 + 7}
= 10

D3[1, 3] =
min { D2 [1, 3], D2 [1, 3] + D2 [3, 3] }
= min {3, 3 + 0}
= 3

D3[1, 4] =
min { D2 [1, 4], D2 [1, 3] + D2 [3, 4] }
= min {∞, 3 + 1}
=4
Iteration 3 (k = 3) :
D3[2, 1]
= min { D2 [2, 1], D2 [2, 3] + D2 [3, 1] }
= min {2, 5 + 9}
=2

D3[2, 3]
= min { D2 [2, 3], D2 [2, 3] + D2 [3, 3 }
= min {5, 5 + 0}
=5

D3[2, 4] = min { D2 [2, 4], D2 [2, 3] + D2 [3, 4] }

= min {∞, 5 + 1}
=6
Iteration 3 (k = 3) :
D3[3, 1]
= min { D2 [3, 1], D2 [3, 3] + D2 [3, 1] }
= min {9, 0 + 9}
=9

D3[3, 2]
= min { D2 [3, 2], D2 [3, 3] + D2 [3, 2] }
= min {7, 0 + 7}
=7

D3[3, 4] = D2 [3, 4] = 1
= min { D2 [3, 4], D2 [3, 3] + D2 [3, 4] }
= min {1, 0 + 1}
=1
Iteration 3 (k = 3) :
D3[4, 1]
= min { D2 [4, 1], D2 [4, 3] + D2 [3, 1] }
= min {6, 9 + 9}
=6

D3[4, 2]
= min { D2 [4, 2], D2 [4, 3] + D2 [3, 2] }
= min {∞, 9 + 7}
= 16

D3[4, 3]
= min { D2 [4, 3], D2 [4, 3] + D2 [3, 3] }
= min {9, 9 + 0}
= 9
Update Matrix
Iteration 4 (k = 4) :

D4[1, 2]
= min { D3 [1, 2], D3 [1, 4] + D3 [4, 2] }
= min {10, 4 + 16}
= 10

D4[1, 3]
= min { D3 [1, 3], D3 [1, 4] + D3 [4, 3] }
= min {3, 4 + 9}
=3

D4[1, 4] =
= min { D3 [1, 4], D3 [1, 4] + D3 [4, 4] }
= min {4, 4 + 0}
=4
Iteration 4 (k = 4) :
D4[2, 1]
= min { D3 [2, 1], D3 [2, 4] + D3 [4, 1] }
= min {2, 6 + 6}
=2

D4[2, 3]
= min { D3 [2, 3], D3 [2, 4] + D3 [4, 3] }
= min {5, 6 + 9}
=5

D4[2, 4]
= min { D3 [2, 4], D3 [2, 4] + D3 [4, 4] }
= min {6, 6 + 0}
= 6
Iteration 4 (k = 4) :
D4[3, 1]
= min { D3 [3, 1], D3 [3, 4] + D3 [4, 1] }
= min {9, 1 + 6}
=7

D4[3, 2]
= min { D3 [3, 2], D3 [3, 4] + D3 [4, 2] }
= min {7, 1 + 16}
=7

D4[3, 4]
= min { D3 [3, 4], D3 [3, 4] + D3 [4, 4] }
= min {1, 1 + 0}
= 1
Iteration 4 (k = 4) :
D4[4, 1]
= min { D3 [4, 1], D3 [4, 4] + D3 [4, 1] }
= min {6, 0 + 6}
=6

D4[4, 2]
= min { D3 [4, 2], D3 [4, 4] + D3 [4, 2] }
= min {16, 0+ 16}
= 16

D4[4, 3]
= min { D3 [4, 3], D3 [4, 4] + D3 [4, 3] }
= min {9, 0+ 9}
= 9
Final distance matrix
is,

1 2 3
1
4
2

4
Complexity
• For G(V,E) having n vertices, Complexity is n3

• Advantages: Easy to implement

for (int k = 0; k < n; k++) {

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != 9999 && dist[k][j] != 9999 &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j]; }
} }}

• Disadvantage: Its Complexity

Problem: Obtain all pair shortest path using Floyd’s Algorithm for given
weighted graph