Dynamic Programming

Huang Shell Ying

Reference: Computer Algorithms: Introduction to Design and

Analysis, 3rd Ed, by Sara Basse and Allen Van Gelder.
Setions 10.1, 10.2 & 10.3

1
Outline
1. Concepts of dynamic programming
2. Longest common subsequence
3. Chain matrix multiplication
4. 0/1 Knapsack problem

Dynamic Programming SC2001/CX2101 2

What is Dynamic Programming?
• It is a problem solving paradigm
• To a certain extent, it is similar to divide-and-
conquer
• What do we do in divide-and-conquer?
• Divide a problem into independent subproblems
• Solve each subproblem recursively
• Combine the solutions to subproblems into a
solution for the given problem
• Example: MergeSort
Dynamic Programming SC2001/CX2101 3
 Example: MergeSort(8) The 2 half
sections of the
array in each
MergeSort(1..8)
division are
independent

MergeSort(1..4) MergeSort(5..8)

MergeSort(1..2) MergeSort(3..4)

MergeSort(5..6) MergeSort(7..8)

Dynamic Programming SC2001/CX2101 4

What is Dynamic Programming?
• Dynamic programming:
• Divide a problem into overlapping subproblems
• Solve each subproblem recursively
• Combine the solutions to subproblems into a
solution for the given problem
• Do not compute the answer to the same
subproblem more than once
• Example: computing Fibonacci numbers

Dynamic Programming SC2001/CX2101 5

Fibonacci seqence
The Fibonacci sequence is defined recursively as:
Fn = Fn-1 + Fn-2 for n  2
F0 = 0, F1 = 1
This series occurs frequently in algorithm analysis.

Divide-and-conquer: Recursive Fibonacci function

int fib(n)
{ if (n == 0 || n == 1) return n;
else return fib(n - 1) + fib(n - 2);
}
Dynamic Programming SC2001/CX2101 6
Tree of function 0
calls: each
2 1
node 0
represents a 1
function call 1
3 2
4
1 0
6
3 2 1
0
5
4 2 1
1 0
Many subproblems are 3
2 1
overlapping: a lot of
recomputation
Dynamic Programming SC2001/CX2101 7
• Example of repetition is given in the shaded nodes
• Notice that this is a full binary tree up to depth 3 (i.e.
n/2)
• The deepest level is 5 (i.e. n-1)
• The number of recursive calls R is such that
24 - 1 < R < 26 - 1
In general,
n +1
−1  R  2 −1
n
2 2

So this is an exponential time algorithm: O(2n)

Dynamic Programming SC2001/CX2101 8

• The main feature of dynamic programming is that it replaces
an exponential-time computation by a polynomial-time
computation
• It is done by this: Memorize the solutions and do not
recompute
• Recall that a DFS on a graph only explores edges to
undiscovered vertices, and it checks the other edges.
• This strategy may be applied to only solve unsolved
subproblems, and checks and retrieves solutions to the
solved subproblems

Find previous yes Has prob been solved? no Solve it

solution

Dynamic Programming SC2001/CX2101 9

 Dynamic programming (Top Down)
1. Formulate the problem P in terms of smaller versions of the
problem (recursively), say, Q1, Q2, …
2. Turn this formulation into a recursive function to solve problem P
3. Use a dictionary to store solutions to subproblems
4. In the recursive function to solve P
❖ Before any recursive call, say on subproblem Qi, check the
dictionary to see if a solution for Qi has been stored
▪ If no solution has been stored, make the recursive call
▪ Otherwise, retrieve the stored solution
❖ Just before returning the solution for P, store the solution in
the dictionary - memorization
Dynamic Programming SC2001/CX2101 10
The top-down approach
A dynamic programming version of fib(n)

int fibDP(n)
{ int f1, f2;
if (n == 0 || n == 1) { Store,
member,
store(Soln, n, n);
retrieve are all
return n; } methods of the
else { Dictionary
if (not member(Soln, n - 1))
f1 = fibDP(n - 1);
else f1 = retrieve(Soln, n - 1);

Dynamic Programming SC2001/CX2101 11

 if (not member(Soln, n - 2))
f2 = fibDP(n - 2);
else f2 = retrieve(Soln, n - 2);

f1 += f2;
store(Soln, n, f1);
return f1; }
}
• Before calling fibDP, the dictionary Soln has to be initialized.
E.g.
0 1 2 3 4 5 6
Soln -1 -1 -1 -1 -1 -1 -1

Dynamic Programming SC2001/CX2101 12

• member(Dictionary, j):
return Dictionary[j] <> -1
• store(Dictionary, j, s):
Dictionary[j] = s
• retrieve(Dictionary, j):
return Dictionary[j]

Dynamic Programming SC2001/CX2101 13

int fibDP(n) if (not member(Soln, n - 2))
{ int f1, f2; f2 = fibDP(n - 2);
if (n == 0 || n == 1) { else f2 = retrieve(Soln, n - 2);
store(Soln, n, n); f1 += f2;
return n; } store(Soln, n, f1);
else { return f1; }
if (not member(Soln, n - 1)) }
f1 = fibDP(n - 1);
Complexity: O(n)
else f1 = retrieve(Soln, n - 1);

The total computational time in each function call, excluding that

of the calls to fibDP() on subproblems is bounded by a constant.
The total computational cost is thus proportional to the number of
calls to fibDP() when solving fibDP(n) – n+1 times. So O(n).
Dynamic Programming SC2001/CX2101 14
Dynamic programming (Bottom Up)
Subproblem graphs
• For a recursive algorithm A, the subproblem graph for A is a
directed graph whose vertices are the instances for this
problem. The directed edges (I, J) for all pairs that indicate:
if A is invoked on problem I, it makes a recursive call directly
on instance J.
• E.g. the subproblem graph for fib(6):

6 5 4 3 2 1 0

Dynamic Programming SC2001/CX2101 15

 Dynamic programming (Bottom Up)
1. Formulate the problem P in terms of smaller versions of the
problem (recursively), say, Q1, Q2, …
2. Turn this formulation into a recursive function to solve problem
P
3. Draw the subproblem graph and find the dependencies among
subproblems
4. Use a dictionary to store solutions to subproblems
5. In the iterative function to solve P
❖ compute the solutions of subproblems of a problem first
❖ The solution to P is computed based on the solutions to its
subproblems and is stored into the dictionary
Dynamic Programming SC2001/CX2101 16
The subproblem graph of fib(n)

n n-1 n-2 n-3 n-4 n-5 …

• Observation 1: Since we have a sequence of subproblems

for fib(n), we will use an one-dimensional array to
memorize the solutions of subproblems. E.g. fib(6)
0 1 2 3 4 5 6
Soln
• Observation 2: Seeing the dependencies among the
solutions – fib(n) needs the solutions of fib(n-1) and fib(n-
2), we can compute the elements in this array in a correct
order.
Dynamic Programming SC2001/CX2101 17
 soln[0] = 0;
soln[1] = 1; Complexity: O(n)
for j = 2 to n
soln[j] = soln[j-1] + soln[j-2];

0 1 2 3 4 5 6
Soln 0 1 1 2 3 5 8

Dynamic Programming SC2001/CX2101 18

Longest Common Subsequence
• Given a sequence s = <s1, s2, …, sn>, a subsequence
is any sequence <si1, si2, …, sim>, with ij strictly
increasing.
Example: s = ACTTGCG
ACT, AG, ATTC, T, ACTTGC are all subsequences.
TTA, AGGC are not subsequences.
• Given two sequences x = <x1, x2, …, xn>, y = <y1, y2,
…, ym>, a common subsequence is a subsequence
of both x and y.
Dynamic Programming SC2001/CX2101 19
• A longest common subsequence (LCS) is a common
subsequence of maximum length
Example: x = AAACCGTGAGTTATTCGTTCTAGAA
y = CACCCCTAAGGTACCTTTGGTTC
Common subsequences: ACGG, CAGTTTC
LCS = ACCTAGTACTTTG (LCS may not be unique)
• LCS has many applications including document
analysis and computational biology – the similarity
between two sequences is measured by the length
of LCS

Dynamic Programming SC2001/CX2101 20

Problem definition: Given two sequences x = <x1, x2, …,
xn>, y = <y1, y2, …, ym>, compute LCS(n, m) that gives
the length of the longest common subsequence

Dynamic Programming SC2001/CX2101 21

• A trivial algorithm: find all subsequences of x (there
are up to 2n of them) and check whether they are
subsequences of y.
• What is the complexity of this trivial algorithm?
• This is an optimization problem
• Dynamic programming is a powerful tool to solve
optimization problems that satisfy the Principle of
Optimality
• A problem is said to satisfy the principle of
optimality if the subsolutions of an optimal solution
of the problem are themselves optimal solutions for
their subproblems.
Dynamic Programming SC2001/CX2101 22
• Does the LCS problem satisfy this principle?
Step 1: Formulate the problem P in terms of smaller
versions of the problem
• Consider two sequences x = <x1, x2, …, xi>, y = <y1, y2,
…, yj>. Take them as character strings. E.g.
1 2 3 4 5 when x5 = y4
x A C G A G
1 2 3 4
y A C T G
x A C G A
y A C T
+ G
LCS(5,4)
LCS(4,3)

Dynamic Programming SC2001/CX2101 23

 o If xi = yj, then this character is the last character in the
longest common subsequence. The longest common
subsequence is the longest common subsequence of <x1,
x2, …, xi-1>, and <y1, y2, …, yj-1> followed by xi.

x … … xi-1 xi … yj-2 xi-1

y … yj-1 yj … yj-2 yj-1 + xi

LCS(i,j) LCS(i-1,j-1)

LCS(i-1,j-1) is a subsolution of LCS(i,j) when xi = yj.

LCS(i-1,j-1) is an optimal solution.
Otherwise LCS(i,j) cannot be an optimal solution

Dynamic Programming SC2001/CX2101 24

 o If xi  yj, then either xi is not in the LCS or yj is not in the
LCS (or both of them are not in the LCS).
If xi is not in the LCS, we just need to find the longest
common subsequence of <x1, x2, …, xi-1> and <y1, y2, …,
yj>.
LCS(i,j) LCS(i-1,j)
… … xi-1 xi … xi-2 xi-1
… yj-1 yj … yj-1 yj
If yj is not in the LCS, we just need to find the longest
common subsequence of <x1, x2, …, xi> and <y1, y2, …,
yj-1>.
… … xi-1 xi … xi-1 xi
… yj-1 yj … yj-2 yj-1
LCS(i,j) LCS(i,j-1)
Dynamic Programming SC2001/CX2101 25
 o E.g., 1 2 3 4
x A C G G
1 2 3 4 5
y A C T G
x A C G G A max
y A C T G LCS(4,4)
1 2 3 4 5
LCS(5,4) x A C G G A
when x5  y4 y A C T

LCS(5,3)

o The dynamic programming selection rule: when given a

number of possibilities, compute all and take the best.

Dynamic Programming SC2001/CX2101 26

 Therefore, when xi  yj,
LCS(i-1,j)
… xi-2 xi-1
LCS(i,j)
… yj-1 yj max
… … xi-1 xi
… yj-1 yj … xi-1 xi
… yj-2 yj-1
LCS(i,j-1)

• LCS(i-1,j-1), LCS(i-1,j) and LCS(i,j-1) are the optimal

solutions for the respective subproblems.
Otherwise LCS(i,j) cannot be optimal – principle of
optimality.
Dynamic Programming SC2001/CX2101 27
Step 2: Turn this formulation into a recursive function
to solve the longest common subsequence problem:

LCS(i,j) = 0 if i=0 or j=0

LCS(i,j) = LCS(i-1,j-1) + 1 if i,j > 0, xi = yj
LCS(i,j) = max(LCS(i-1,j), LCS(i,j-1)) if i,j > 0, xi  yj

• The top down approach using a recursive function

will be very inefficient.

Dynamic Programming SC2001/CX2101 28

Step 3 (bottom up approach): Draw the subproblem
graph and find the dependencies among subproblems
E.g, the subproblem graph of LCS(6,5)
(0,0) (0,1) (0,2) (0,3) (0,4) (0,5)
(1,0) (1,1) (1,2) (1,3) (1,4) (1,5)
(2,0) (2,1) (2,2) (2,3) (2,4) (2,5)
(3,0) (3,1) (3,2) (3,3) (3,4) (3,5)
(4,0) (4,1) (4,2) (4,3) (4,4) (4,5)
(5,0) (5,1) (5,2) (5,3) (5,4) (5,5)
(6,0) (6,1) (6,2) (6,3) (6,4) (6,5)

Step 4: the dictionary is a n+1 by m+1 array.

Initialise row 0, column 0.
Compute from row 1 to row n, column 1 to column m within each
row.
Dynamic Programming SC2001/CX2101 29
Int LCS(n, m) Step 5
{
for i = 0 to n c[i][0] = 0;
for j = 1 to m c[0][j] = 0;
for i = 1 to n
for j = 1 to m
if x[i] == y[j]
c[i][j] = c[i-1][j-1] + 1;
else if c[i-1][j] >= c[i][j-1]
c[i][j] = c[i-1][j];
else c[i][j] = c[i][j-1];
return c[n][m];
}
Dynamic Programming SC2001/CX2101 30
Int LCS(n, m)
{ Space Complexity:
(n+1)x(m+1) array
for i = 0 to n c[i][0] = 0;
O(nm)
for j = 1 to m c[0][j] = 0;
for i = 1 to n Total no. of
for j = 1 to m iterations: nm
if x[i] == y[j]
c[i][j] = c[i-1][j-1] + 1;
Bounded by a
else if c[i-1][j] >= c[i][j-1] constant time
c[i][j] = c[i-1][j];
else c[i][j] = c[i][j-1];
return c[n][m]; Time Complexity:
} O(nm)
Dynamic Programming SC2001/CX2101 31
Example 1 1 2 3 4 5
x A C G G A
for i = 0 to n c[i][0] = 0; y A C T G
for j = 1 to m c[0][j] = 0;

A C T G
0 0 0 0 0
A 0
C 0
G 0
G 0
A 0

Dynamic Programming SC2001/CX2101 32

Example 1 1 2 3 4 5
x A C G G A
y A C T G

A C T G
for i = 1 to n
0 0 0 0 0
for j = 1 to m
A 0 1 1 1 1
if x[i] == y[j]
C 0 1 2 2 2
c[i][j] = c[i-1][j-1] + 1;
G 0 1 2 2 3
else if c[i-1][j] >= c[i][j-1]
G 0 1 2 2 3
c[i][j] = c[i-1][j];
A 0 1 2 2
3 else c[i][j] = c[i][j-1];

LCS(5,4) = 3

Dynamic Programming SC2001/CX2101 33

• To find the longest common subsequence, a hint
array is used in LCS() function to indicate for
LCS(i,j) where the optimal subsolution is from :
LCS(i-1, j-1), LCS(i-1, j) or LCS(i, j-1).

o For the hint array cell h[i][j] where i≠0 and j≠0,
▪ If we do LCS(i,j) = LCS(i-1, j-1)+1, h[i][j] = ‘\’
▪ If we do LCS(i,j) = LCS(i-1, j), h[i][j] = ‘|’
▪ If we do LCS(i,j) = LCS(i, j-1), h[i][j] = ‘—’
o First column of the hint array will be filled with ‘|’.
o First row of the hint array will be filled ‘—’.

Dynamic Programming SC2001/CX2101 34

Int LCS(n, m) // with hints to find the sequence
{
for i = 0 to n { c[i][0] = 0; h[i][0] = ‘|’; }
for j = 1 to m { c[0][j] = 0; h[0][j] = ‘—’; }
for i = 1 to n
Time Complexity:
for j = 1 to m O(nm)
if x[i] == y[j]
{ c[i][j] = c[i-1][j-1] + 1; h[i][j] = ‘\’; }
else if c[i-1][j] >= c[i][j-1]
{ c[i][j] = c[i-1][j]; h[i][j] = ‘|’; }
else { c[i][j] = c[i][j-1]; h[i][j] = ‘—’; }
return c[n][m];
}
Dynamic Programming SC2001/CX2101 35
• To obtain the longest common subsequence computed, we
start from h[n][m].
• For each element of the hint array, h[i][j],
o If h[i][j] = ‘\’, it means xi = yj and this character is the
last character of the longest common subsequence of
x1.. xi and y1..yj. This character is preceded by the
longest common subsequence of x1.. xi-1 and y1..yj-1.
o If h[i][j] = ‘|’, it means the longest common
subsequence of x1.. xi and y1..yj is the longest common
subsequence of x1.. xi-1 and y1..yj.
o If h[i][j] = ‘—’, it means the longest common
subsequence of x1.. xi and y1..yj is the longest common
subsequence of x1.. xi and y1..yj-1.
• After reaching the 1st row/column of the hint array, end

Dynamic Programming SC2001/CX2101 36

getSequence(n m) // get the LCS from hint array
{ s = empty stack; // s stores the characters in LCS
i = n; Maximum no. of
j = m; iterations: n+m.
while (i  0 and j  0) Complexity: O(n+m)

if (h[i][j] == ‘\’)
{ [Link](x[i]); i--; j--; } Bounded by a
constant time
else if (h[i][j] == ‘|’)
i--;
else j--;
pop and output from s; }
Dynamic Programming SC2001/CX2101 37
 1 2 3 4 5
Example 1
x A C G G A
A C T G
0 0 0 0 0 y A C T G
A 0 1 1 1 1
C 0 1 2 2 2
G 0 1 2 2 3 h(5,4) = ‘|’
G 0 1 2 2 3 h(4,4) = ‘\’ G
A 0 1 2 2 3 h(3,3) = ‘|’
h(2,3) = ‘—’
A C T G
h(2,2) = ‘\’ C
— — — — —
h(1,1) = ‘\’
A | \ — — —
end A
C | | \ — —
G | | | | \
G | | | | \
The sub sequence: A C G
A | \ | | |
Dynamic Programming SC2001/CX2101 38
 Example 2: x C G G T A T
y A G T T G C

A G T T G C A G T T G C
0 0 0 0 0 0 0 — — — — — — —
C 0 0 0 0 0 0 1 C | | | | | | \
G 0 0 1 1 1 1 1 G | | \ — — \ |
G 0 0 1 1 1 2 2 G | | \ | | \ —
T 0 0 1 2 2 2 2 T | | | \ \ | |
A 0 1 1 2 2 2 2 A | \ | | | | |
T 0 1 1 2 3 3 T | | | \ \ — —
3

LCS(6,6) = 3

Dynamic Programming SC2001/CX2101 39

Example 2: x C G G T A T
y A G T T G C

A G T T G C h(6,6) = ‘—’
— — — — — — — h(6,5) = ‘—’
C | | | | | | \ h(6,4) = ‘\’ T
G | | \ — — \ | h(5,3) = ‘|’
G | | \ | | \ — h(4,3) = ‘\’ T
T | | | \ \ | | h(3,2) = ‘\’
A | \ | | | | | h(2,1) = ‘|’ G
T | | | \ \ — — h(1,1) = ‘|’
h(0,1) = ‘—’
end
LCS(6,6) = 3
The subsequence: G T T
Dynamic Programming SC2001/CX2101 40
Chain Matrix Multiplication
• The Order problem . . . . . . .
. . . . . . .
Consider A1 x A2 x A3 x A4    
. . . .
30x1 1x40 40x10 10x25
2X3X4
Many possibilities. For examples,
((A1A2)A3)A4 30x1x40 + 30x40x10 + 30x10x25 =
20,700 multiplications
A1(A2(A3A4)) 40x10x25 + 1x40x25+ 30x1x25 =
11,750 multiplications
(A1A2)(A3A4) 30x1x40 + 40x10x25 + 30x40x25 =
41,200 multiplications
A1((A2A3)A4) 1x40x10 + 1x10x25 + 30x1x25 =
1,400 multiplications
Dynamic Programming SC2001/CX2101 41
Problem definition: given matrices A1, A2, ….An where
dimensions of Ai are di-1 x di (for 1 i n), what order
should the matrix multiplications be computed in order to
incur minimum cost? Cost is the number of
multiplications.

d0 d1 d2 d3 … dn-1 dn
• There are (n-1)! ways for n matrices
• Matrix multiplication is associative: (AB)C = A(BC). So
different ways give the same result
• This is an optimization problem

Step 1: formulate the matrix multiplication cost problem in

terms of smaller versions of the same problem
Dynamic Programming SC2001/CX2101 42
Consider a sequence of 6 matrices:
A1 x A2 x A3 x A4 x A5 x A6 matrices

d0xd1 d1xd2 d2xd3 d3xd4 d4xd5 d5xd6 dimensions

B1 B2
Suppose the last matrix multiplication were at A3; then
1) We need to multiply A1 x A2 x A3 to create B1, a
d0 x d3 matrix
2) We need to multiply A4 x A5 x A6 to create B2, a
d3 x d6 matrix
Cost would be the cost of (1)+(2)+ cost of(B1 x B2)

Dynamic Programming SC2001/CX2101 43

A1 x A2 x A3 x A4 x A5 x A6 matrices

d0 x d1 d1 x d2 d2 x d3 d3 x d4 d4 x d5 d5 x d6 dimensions

The last multiplication may be at each of the 5 matrices.

Cost((A1A2A3A4 A5)(A6)) = Cost(A1A2A3A4A5) + Cost(A6)
+ d0 x d5 x d6
Cost((A1A2A3A4)(A5A6)) = Cost(A1A2A3A4) + Cost(A5 A6)
+ d0 x d4 x d6
Cost((A1A2A3)(A4A5A6)) = Cost(A1A2A3) + Cost(A4A5A6)
+ d0 x d3 x d6
Cost((A1A2)(A3A4A5A6)) = Cost(A1A2) + Cost(A3A4A5A6)
+ d0 x d2 x d6
Cost((A1)(A2A3A4A5A6)) = Cost(A1) + Cost(A2A3A4A5A6)
+ d0 x d1 x d6
Dynamic Programming SC2001/CX2101 44
A1 x A2 x A3 x A4 x A5 x A6 matrices

d0 x d1 d1 x d2 d2 x d3 d3 x d4 d4 x d5 d5 x d6 dimensions
The dynamic programming selection rule: when given a
number of possibilities, compute all and take the best.
The optimal cost of multiplying the 6 matrices:
OptCost(A1A2A3A4A5A6) = Min(
OptCost(A1A2A3A4A5) + OptCost(A6) + d0 x d5 x d6,
OptCost(A1A2A3A4) + OptCost(A5A6) + d0 x d4 x d6,
OptCost(A1A2A3) + OptCost(A4A5A6) + d0 x d3 x d6,
OptCost(A1A2) + OptCost(A3A4A5A6) + d0 x d2 x d6,
OptCost(A1) + OptCost(A2A3A4A5A6) + d0 x d1 x d6 )
OptCost(A) = 0
Dynamic Programming SC2001/CX2101 45
Step 2: Turn this formulation into a recursive function to
solve the chain matrix multiplication problem.
Suppose we use array d to store the dimensions of the
matrices.
d0 d1 d2 …

Let OptCost(i,j) be the optimal cost of multiplying matrices

with dimensions di x di+1, di+1 x di+2, …, dj−1 x dj.
OptCost(i, j) = 0 if j-i=1
OptCost(i, j)
= min OptCost(i,k) + OptCost(k, j) + di x dk x dj
𝑖+1≤𝑘≤𝑗−1
if j-i>1
The optimal cost of multiplying n matrices is OptCost(0, n).
Dynamic Programming SC2001/CX2101 46
• The chain matrix multiplication problem satisfies
the principle of optimality
o OptCost(i, k) and OptCost(k, j) for k = i+1, …, j-1
are the subsolutions of OptCost(i, j)
o They are the optimal solutions for the
subproblems
o Proof by contradiction

Dynamic Programming SC2001/CX2101 47

 Example: A1x A2x A3xA4xA5xA6
(i,j) represents
(A1A2A3A4A5A6) OptCost(i, j)
(0,6)

(A1)(A2...A6) (A1 A2)(A3...A6) (A1... A3)(A4...A6) (A1... A4)(A5A6)

(0,1)(1,6) (0,2)(2,6) (0,3)(3,6) (0,4)(4,6)

(A1... A5)(A6)
(A2)(A3...A6) (A2 A3)(A4...A6) (A2... A4)(A5A6) (0,5)(5,6)
(1,2)(2,6) (1,3)(3,6) (1,4)(4,6)
(A2... A5)(A6)
(1,5)(5,6)
(A3)(A4...A6) (A3 A4)(A5A6) (A3... A5)(A6)
(2,3)(3,6) (2,4)(4,6) (2,5)(5,6)

Dynamic Programming SC2001/CX2101 48

 Step 3: Draw the subproblem graph and find the
dependencies among subproblems

(0,1) (0,2) (0,3) (0,4) (0,5) (0,6)

(1,2) (1,3) (1,4) (1,5) (1,6)

(2,3) (2,4) (2,5) (2,6)

Every node calls all the nodes (3,4) (3,5) (3,6)

on its left in the same row and
all the nodes below it in the (4,5) (4,6)
same column.
The number of nodes is O(n2). (5,6)

Dynamic Programming SC2001/CX2101 49

 Step 4: Dictionary: cost[n+1][n+1]

0 1 2 3 4 5 6
0
1
cost 2
3
4
5
6

Not computed

Dynamic Programming SC2001/CX2101 50

 Step 5
Order to solve the subproblems
0 1 2 3 4 5 6
0 0
1 0
2 0
cost
3 0
4 0
5 0
6

Not computed

Use another array, last[n+1][n+1] to represent the index

of the last multiplication to be done for a subproblem
Dynamic Programming SC2001/CX2101 51
Find the pattern
0 1 2 3 4 5 6
0 0
1 0
2 0
cost 3 0
4 0
5 0
6

Row number and column number differ by 2, row goes

from 0 to 4
Row number and column number differ by 3, row goes
from 0 to 3
Row number and column number differ by 4, row goes
from 0 to 2
Dynamic Programming SC2001/CX2101 52
Find the pattern
0 1 2 3 4 5 6
0 0
1 0
2 0
cost 3 0
4 0
5 0
6

Row number and column number differ by 5, row goes

from 0 to 1
Row number and column number differ by 6, row goes
from 0 to 0
Thus, row number and column number differ by 2 to 6, within
each difference, row goes from 0 to n minus this difference
Dynamic Programming SC2001/CX2101 53
int matrixOrder(int [] d, int n)
{ for i = 0 to n-1 cost[i][i+1] = 0;
for l = 2 to n
for i = 0 to n-l min ሺOptCost(i,k) + OptCost(k,
𝑖+1≤𝑘≤𝑗−1
j = i + l; j) + di x dk x djሻ
cost[i][j] = ;
for k = i+1 to j-1
c = cost[i][k] + cost[k][j] + d[i]*d[k]*d[j];
if (c < cost[i][j])
cost[i][j] = c; last[i][j] = k;
}
Dynamic Programming SC2001/CX2101 54
int matrixOrder(int [] d, int n)
Complexity of
{ for i = 0 to n-1 cost[i][i+1] = 0; computing the
optimal order:
for l = 2 to n
O(n3)
for i = 0 to n-l
j = i + l;
Repeated O(n2) times
cost[i][j] = ;
for k = i+1 to j-1 Repeated O(n3) times

c = cost[i][k] + cost[k][j] + d[i]*d[k]*d[j];

if (c < cost[i][j])
cost[i][j] = c; last[i][j] = k;
}
Dynamic Programming SC2001/CX2101 55
 Example
A1 x A2 x A3 x A4

30x1 1x40 40x10 10x25

Array d
30 1 40 10 25

0 1 2 3 4

Call to matrixOrder(d, 4)

Dynamic Programming SC2001/CX2101 56

 d 30 1 40 10 25
0 1 2 3 4

cost
0 1 2 3 4
0 0
1 0 for i = 0 to n-1
2 0 cost[i][i+1] = 0;
3 0
4

Dynamic Programming SC2001/CX2101 57

 d 30 1 40 10 25
0 1 2 3 4
cost
0 1 2 3 4
for l = 2 to n k=1:
0 0 1200 Cost[0][1]+
for i = 0 to n-l Cost[1][2] + 1200
1 0
2 0
j = i + l;
3 0 cost[i][j] = ;
4 for k = i+1 to j-1
0 1 2 3 4
c = cost[i][k] + cost[k][j]
0 1 + d[i]*d[k]*d[j];
1 if (c < cost[i][j])
2 cost[i][j] = c;
3
last[i][j] = k;
4

last l=2, i=0, j=2, k=1

Dynamic Programming SC2001/CX2101 58
 d 30 1 40 10 25
0 1 2 3 4
cost
0 1 2 3 4
for l = 2 to n k=2:
0 0 1200 Cost[1][2]+
for i = 0 to n-l Cost[2][3] + 400
1 0 400
2 0
j = i + l;
3 0 cost[i][j] = ;
4 for k = i+1 to j-1
0 1 2 3 4
c = cost[i][k] + cost[k][j]
0 1 + d[i]*d[k]*d[j];
1 2 if (c < cost[i][j])
2 cost[i][j] = c;
3
last[i][j] = k;
4

last l=2, i=1, j=3, k=2

Dynamic Programming SC2001/CX2101 59
 d 30 1 40 10 25
0 1 2 3 4
cost
0 1 2 3 4
for l = 2 to n k=3:
0 0 1200 Cost[2][3]+
for i = 0 to n-l Cost[3][4] + 10000
1 0 400
2 0 10000
j = i + l;
3 0 cost[i][j] = ;
4 for k = i+1 to j-1
0 1 2 3 4
c = cost[i][k] + cost[k][j]
0 1 + d[i]*d[k]*d[j];
1 2 if (c < cost[i][j])
2 3 cost[i][j] = c;
3
last[i][j] = k;
4

last l=2, i=2, j=4, k=3

Dynamic Programming SC2001/CX2101 60
 d 30 1 40 10 25
0 1 2 3 4
cost k=1:
0 1 2 3 4 Cost[0][1]+
for l = 2 to n Cost[1][3] + 300
0 0 1200 700
for i = 0 to n-l k=2:
1 0 400 Cost[0][2]+
2 0 10000
j = i + l; Cost[2][3] + 12000
3 0 cost[i][j] = ;
4 for k = i+1 to j-1
0 1 2 3 4
c = cost[i][k] + cost[k][j]
0 1 1 + d[i]*d[k]*d[j];
1 2 if (c < cost[i][j])
2 3 cost[i][j] = c;
3
last[i][j] = k;
4

last l=3, i=0, j=3, k=1,2

Dynamic Programming SC2001/CX2101 61
 d 30 1 40 10 25
0 1 2 3 4
cost k=2:
0 1 2 3 4 Cost[1][2]+
for l = 2 to n Cost[2][4] + 1000
0 0 1200 700
for i = 0 to n-l k=3:
1 0 400 650 Cost[1][3]+
2 0 10000
j = i + l; Cost[3][4] + 250
3 0 cost[i][j] = ;
4 for k = i+1 to j-1
0 1 2 3 4
c = cost[i][k] + cost[k][j]
0 1 1 + d[i]*d[k]*d[j];
1 2 3 if (c < cost[i][j])
2 3 cost[i][j] = c;
3
last[i][j] = k;
4

last l=3, i=1, j=4, k=2,3

Dynamic Programming SC2001/CX2101 62
 d 30 1 40 10 25
0 1 2 3 4
cost k=1:
0 1 2 3 4 Cost[0][1]+
for l = 2 to n Cost[1][4] + 750
0 0 1200 700 1400 k=2:
for i = 0 to n-l Cost[0][2]+
1 0 400 650
Cost[2][4] + 30000
2 0 10000
j = i + l; k=3:
3 0 cost[i][j] = ; Cost[0][3]+
Cost[3][4] + 7500
4 for k = i+1 to j-1
0 1 2 3 4
c = cost[i][k] + cost[k][j]
0 1 1 1 + d[i]*d[k]*d[j];
1 2 3 if (c < cost[i][j])
2 3 cost[i][j] = c;
3
last[i][j] = k;
4

last l=4, i=0, j=4, k=1,2,3

Dynamic Programming SC2001/CX2101 63
 0 1 2 3 4
0 1 1 1
1 2 3
2 3
(0,4) 3
last[0][4] = 1 *
4
(1,4) last
A1 * last[1][4] = 3
(0,1) (1,3)
last[1][3] = 2 * A4 (3,4)

(1,2) A A3 (2,3)
2
So the best sequence is
(A1 x ((A2 x A3 ) x A4 ))

Dynamic Programming SC2001/CX2101 64

0/1 Knapsack problem
Problem definition: We have a knapsack of capacity
weight C (a positive integer) and n objects with weights
w1, w2, …wn and profits p1, p2, …pn (all wi and all pi are
positive integers), find the largest total profit of any
subset of the objects that fits in the knapsack.

• We have to take whole objects.

• There are 2n subsets of n objects: examining all

subsets takes O(2n) time
E.g. application: C is amount of money to invest,
weights, w1,… are investment amounts and profit
is the expected return on investment.
Dynamic Programming SC2001/CX2101 65
• Step 1: formulate the 0/1 knapsack problem in terms
of smaller versions of the same problem
o Consider the last object of the n objects with
weights w1, w2, …wn.
o If we include it in the knapsack, the available
weight capacity in the knapsack will be reduced by
wn. Then our profit will be pn, plus the maximum we
can get from solving the subproblem of n-1 objects
and capacity of C- wn.
o If we do not include it in the knapsack, our profit will
be the maximum we can get from solving the
subproblem of n-1 objects and capacity of C.
o The dynamic programming selection rule: when given a
number of possibilities, compute all and take the best.

Dynamic Programming SC2001/CX2101 66

 For example, a knapsack of capacity 10 and 4 objects

(10, 4) Maximum of the two choices

Include the 4th object Do not include the 4th object

(10-w4, 3) +p4 (10, 3)

Include the 3rd object Do not include
the 3rd object
(10-w3, 2) +p3 (10, 2)
(10-w4-w3, 2) +p4+p3 (10-w4, 2) +p4

……

Dynamic Programming SC2001/CX2101 67

 Step 2: Turn this formulation into a recursive function
to solve the 0/1 knapsack problem
Let P(C, j) be the maximum profit that can be made by
selecting a subset of the j objects with knapsack
capacity of C.
P(C, 0) = P(0, j) = 0
P(C, j) = max(P(C, j-1), pj + P(C-wj, j-1))
• Step 3: Draw the subproblem graph and find the
dependencies among subproblems
For example, C = 20

1 2 3 4
wi 4 6 8 6
pi 7 6 9 5
Dynamic Programming SC2001/CX2101 68
 1 2 3 4
wi 4 6 8 6
pi 7 6 9 5

(0,1)
P(C, j) = max(P(C, j-1), pj +
P(C-wj, j-1))
(2,0)
(4,0)
(6,0) (6,1) (6,2)
(8,0) (8,1)
(10,0) (i,j) represents
P(i, j)
(12,0) (12,1) (12,2)
(14,0) (14,1) (14,2) (14,3)
(16,0)
(20,0) (20,1) (20,2) (20,3) (20,4)

Dynamic Programming SC2001/CX2101 69

Step 4 :Dictionary: profit[C+1][n+1]

0 1 2 … n
0
1
2
3
4
5
6
7
…
C

Dynamic Programming SC2001/CX2101 70

int knapsack(int [] w, int [] p, int C, int n) Step 5

{ for c = 0 to n profit[0][c] = 0; Complexity :

O(nC)
for r = 1 to C profit[r][0] = 0;
for r = 1 to C P(C, j) = max(P(C, j-1), pj +
for c = 1 to n P(C-wj, j-1))

profit[r][c] = profit[r][c-1];
if (w[c] <= r)
if (profit[r][c] < profit[r-w[c]][c-1] + p[c])
profit[r][c] = profit[r-w[c]][c-1] + p[c];
}
Dynamic Programming SC2001/CX2101 71
 1 2 3 4
Example 1: wi 4 6 8 6
C = 20 pi 7 6 9 5
0 1 2 3 4
0 0 0 0 0 0 for c = 0 to n
2 0 profit[0][c] = 0;
4 0 for r = 1 to C
6 0 profit[r][0] = 0;
8 0
10 0
12 0 Not all rows
14 0 are shown
16 0
20 0

Dynamic Programming SC2001/CX2101 72

 1 2 3 4
Example 1: wi 4 6 8 6
C = 20 pi 7 6 9 5
0 1 2 3 4
0 0 0 0 0 0 for r = 1 to C
1 0 0 0 0 0 for c = 1 to n
2 0 0 0 0 0 profit[r][c] = profit[r][c-1];
3 0 0 0 0 0
if (w[c] <= r)
4 0 7 7 7 7
if (profit[r][c] <
5 0 7 7 7 7
6 0 7 7 7 7
profit[r-w[c]][c-1] + p[c])
8 0 7 7 9 9 profit[r][c] =
9 0 7 7 9 9 profit[r-w[c]][c-1]
10 0 7 13 13 13 + p[c]
11 0 7 13 13 13

Dynamic Programming SC2001/CX2101 73

 1 2 3 4
Example 1: wi 4 6 8 6
C = 20 pi 7 6 9 5
0 1 2 3 4
10 0 7 13 13 13 for r = 1 to C
11 0 7 13 13 13 for c = 1 to n
12 0 7 13 16 16 profit[r][c] = profit[r][c-1];
13 0 7 13 16 16
if (w[c] <= r)
14 0 7 13 16 16
if (profit[r][c] <
15 0 7 13 16 16
16 0 7 13 16 18
profit[r-w[c]][c-1] + p[c])
17 0 7 13 16 18 profit[r][c] =
18 0 7 13 22 22 profit[r-w[c]][c-1]
19 0 7 13 22 22 + p[c]
20 0 7 13 22
22
Dynamic Programming SC2001/CX2101 74
 1 2 3
Example 2: wi 1 2 3
C=3 pi 1 4 6

for c = 0 to n
0 1 2 3 profit[0][c] = 0;
0 0 0 0 0 for r = 1 to C
1 0 profit[r][0] = 0;
2 0
3 0

Dynamic Programming SC2001/CX2101 75

 1 2 3
Example 2: wi 1 2 3
C=3 pi 1 4 6

for r = 1 to C
0 1 2 3 for c = 1 to n
0 0 0 0 0 profit[r][c] = profit[r][c-1];
1 0 1 1 1 if (w[c] <= r)
2 0 1 4 4 if (profit[r][c] <
3 0 1 5 profit[r-w[c]][c-1] + p[c])
6
profit[r][c] =
profit[r-w[c]][c-1]
+ p[c]

Dynamic Programming SC2001/CX2101 76

• The dynamic programming algorithm has a
complexity of O(nC).
• An algorithm is polynomial time if it is a
polynomial function of the size of the input.
E.g. there are n weight numbers and n profit
numbers
• An algorithm is pseudo-polynomial time if it is a
polynomial function of the value of the input.
E.g. there is only one number specifying C
• So the dynamic programming algorithm for
knapsack problem is pseudo-polynomial.

Dynamic Programming SC2001/CX2101 77