CSE 317: Design and Analysis of Algorithms

Dynamic Programming

Shahid Hussain
Spring 2026
SMCS, IBA-Karachi
Dynamic Programming

• The idea of dynamic programming is the following

• For a given problem, we define the notion of a subproblem and an ordering of
subproblems from “smallest” to “largest”.
• (i) the number of subproblems is polynomial, and
• (ii) the solution of a subproblem can be easily (in polynomial time) computed
from the solution of smaller subproblems
• If (i) and (ii) then we can design a polynomial algorithm for the initial problem

1
Shortest Paths in DAGS

• A graph G is called a directed acyclic graph (DAG) if it has no directed cycles

• For a given DAG G we can perform a topological sort of the vertices of G
(linearization of G)

6
b d
1 2 3

a 4 1 f 2 4 6 1 1
2 1 a c b d e f

3 1 2
c e

2
Longest Increasing Subsequences (LIS)

• Given a sequence of numbers ⟨a1 , a2 , . . . , an ⟩

• A subsequence is a sequence of numbers ⟨ai1 , ai2 , . . . , aik ⟩ where
1 ≤ i1 < i2 < · · · < ik ≤ n
• A subsequence is increasing subsequence if ai1 < ai2 < · · · < aik
• For example, given sequence ⟨5, 2, 8, 6, 3, 6, 9, 7⟩, the LIS is ⟨2, 3, 6, 9⟩
• Following graph G = (V, E) is a DAG

5 2 8 6 3 6 9 7

3
Longest Increasing Subsequences (LIS)

Algorithm: LIS
Input: A sequence of numbers ⟨a1 , a2 , . . . , an ⟩
Output: The length of the longest increasing subsequence

1. G(V, E) ← create-dag(a1 , a2 , . . . , an ) // G is the DAG for the input sequence

2. for j ∈ {1, 2, . . . , n}
3. L(j) = 1 + max{L(i) : (i, j) ∈ E}
4. return max{L(j) : j ∈ {1, 2, . . . , n}}

4
Longest Common Subsequence

• Let Σ be some fixed and finite alphabet

• A string X over Σ is a sequence of symbols from Σ i.e., X = x1 x2 . . . xn , n ≥ 0
• Let X be a sequence of length n over Σ
• We say that a subsequence of length k of X is a sequence xi1 xi2 . . . xik such that
i1 < i2 < · · · < ik
• Given two sequences X and Y lengths n and m, respectively
• A common subsequence of sequences X and Y is any sequence such that is
common to both X and Y
• The problem longest common subsequence is to find such a common subsequence
of maximum length

5
Longest Common Subsequence: Bruteforce approach

• A brute-force approach to solve such a problem would require to enumerate all

subsequences of X and check if they are also common to Y
• We can see that there are Θ(2n ) subsequences of the sequence X and we can
check whether it is also a subsequence in Y in linear time i.e, Θ(m)
• Hence, brute-force algorithm would require Θ(m · 2n ) time.

6
Longest Common Subsequence: Dynamic Programming

• We can solve this problem very efficiently using dynamic programming

• We can define the problem of finding the longest common subequence of X and
Y of lengths n and m, respectively, as LCS(n, m)
• We can define a subproblem as LCS(i, j) which finds the longest common
subsequence of sequences ending at xi and yj i.e., between x1 x2 . . . xi and
y1 y2 . . . yj , for 0 ≤ i ≤ n and 0 ≤ j ≤ m
• It is clear that i = 0 or j = 0 represent an empty sequence (correspondingly)
• So, we know that LCS(i, 0) = 0 as well as LCS(0, j) = 0 for all i and j

7
Longest Common Subsequence: Dynamic Programming

• We observe that there are two possible situations when comparing x1 x2 . . . xi and
y1 y2 . . . yj , that is either xi = yj or xi ̸= yj
• When xi = yj these two characters must be included in any common
subsequences that we may have found between x1 x2 . . . xi−1 and y1 y2 . . . yj−1 ,
otherwise we need to check the longest common subsequences between
x1 x2 . . . xi−1 and y1 y2 . . . yj and between x1 x2 . . . xi and y1 y2 . . . yj−1
• Therefore,

 0
 if i = 0 or j = 0,
LCS(i, j) = LCS(i − 1, j − 1) + 1 if i > 0 and j > 0 and ai = bj ,

max{LCS(i − 1, j), LCS(i, j − 1)} if i > 0 and j > 0 and ai ̸= bj .


8
Longest Common Subsequence: Dynamic Programming

Algorithm: TCS
Input: Two sequences X and Y of lengths n and m, respectively
Output: The length of the longest common subsequence of X and Y

1. for i = 0 to n: L(i, 0) = 0
2. for j = 0 to m: L(0, j) = 0
3. for i = 1 to n
4. for j = 1 to m
5. if ai = bj then L(i, j) = L(i − 1, j − 1) + 1
6. else L(i, j) = max{L(i, j − 1), L(i − 1, j)}
7. return L(n, m)

9
Longest Common Subsequence: Dynamic Programming

Theorem
An optimal solution to the longest common subsequence problem can be found in
Θ(nm) time and Θ(min{n, m}) space.

10
Longest Common Subsequence: Example

• Let X = ABCBDAB and Y = BDCABAB

• The subsequence BCBAB is common to both
• We can create following table:
- B D C A B A B
- 0 0 0 0 0 0 0 0
A 0 0 0 0 1 1 1 1
B 0 1 1 1 1 2 2 2
C 0 1 1 2 2 2 2 2
B 0 1 1 2 2 3 3 3
D 0 1 2 2 2 3 3 3
A 0 1 2 2 3 3 4 4
B 0 1 2 2 3 4 4 5
11
Matrix Chain Multiplication

• Let us consider matrices, A, B, and C of dimensions n × 1, 1 × n, and n × n,

respectively
• The dimensions of the product AB is n × n
• So, the product (AB)C requires n2 + n3 multiplications
• The dimensions of the product BC is 1 × n
• Therefore, the product A(BC) requires n2 + n2 = 2n2 multiplications
• Which clearly means computing (AB)C is more expensive than A(BC)

12
Matrix Chain Multiplication

• Let us consider matrices A1 , A2 , . . . An with dimensions, m0 × m1 , m1 × m2 , . . .,

mn−1 × mn , respectively
• The problem is to find the optimal parenthesization of the product A1 A2 · · · An
that minimizes the number of scalar multiplications
• The brute-force approach would require to enumerate all possible
parenthesizations and compute the number of scalar multiplications
• For n matrices, there are 2n−1 possible parenthesizations
• We will use dynamic programming to solve this problem

13
Matrix Chain Multiplication: Dyanmic Programming

• Let us define the subproblem as follows

• Let Ai Ai+1 · · · Aj be a subsequence of matrices Ai Ai+1 · · · Aj
• Let B(i, j) denotes the subproblem of multiplying the matrices Ai Ai+1 · · · Aj for
1≤i≤j≤n
• The problem B(1, n) represents the original problem
• Let us denote C(i, j) as the number of scalar multiplications required to compute
the matrix Ai Ai+1 · · · Aj

14
Matrix Chain Multiplication: Dyanmic Programming

• We can see that C(i, j) = 0 if i = j

• For j > i, we can see that

C(i, j) = min {C(i, k) + C(k + 1, j) + mi−1 · mk · mj }

i≤k<j

• If the last operation of matrix multiplication divides the product Ai Ai+1 · · · Aj

into two subproducts (Ai Ai+1 · · · Ak )(Ak+1 Ak+2 · · · Aj ) then to obtain the
minimum number of element multiplications in the both subproducts and
mi−1 · mk · · · mj element multiplications to multiply the two subproducts
• We choose the k for which it minimizes the number of scalar multiplications
• Since there are O(n2 ) subproblems and each require O(n) time to solve, the total
time complexity is O(n3 )

15
Edit Distance

• Suppose we two strings X and Y over some fixed and finite alphabet Σ
• A natural measure of a distance between these strings is the degree to which they
can be aligned, or matched up
• An alignment is a way of writing the strings one above the other.
• Let us consider two possible alignments of strings SNOWY and SUNNY.
• The symbol ‘‘ ’’ indicates a “gap”. Any number of gaps can be added to each
string
• The cost of an alignment is the number of columns in which the letters differ.
The edit distance between two strings is the cost of the best alignment
S N O W Y S N O W Y
S U N N Y S U N N Y

16
Edit Distance

• In the first alignment the cost is equal to 3

• And in the second alignment the cost is equal to 5
• In other words, the edit distance is the minimum number of insertions, deletions
and substitutions of characters (letters) needed to transform the first string into
the second one
• In the first example we insert U, substitute O → N and delete W

17
Edit Distance

• Let X = x1 , . . . , xm and Y = y1 , . . . , yn
• For each i ∈ {0, 1, . . . , m} and j ∈ {0, 1, . . . , n}, we consider the problem of
finding the edit distance between x1 , . . . , xi and y1 , . . . , yj , and denote by E(i, j)
the considered distance
• If i = 0, the word x1 , . . . , xi is the empty word ϵ. The same situation is for the
case j = 0. It is clear that E(i, 0) = i and E(0, j) = j since the edit distance
between the empty word ϵ and a nonempty word α of the length t is equal to t
• Let us consider the best alignment for x1 , . . . , xi and y1 , . . . , yj where i > 0 and
j > 0. It is clear that in the rightmost column we can have one of the following
three things:
xi xi
yj yj

18
Edit Distance

• In the first case, E(i, j) = 1 + E(i − 1, j). In the second case,

E(i, j) = 1 + E(i, j − 1), and in the third case,
E(i, j) = diff(i, j) + E(i − 1, j − 1), where diff(i, j) = 0 if xi = yj and
diff(i, j) = 1 if xi ̸= yj . Therefore,

E(i, j) = min{1 + E(i − 1, j), 1 + E(i, j − 1), diff(i, j) + E(i − 1, j − 1)}

• We have (m + 1) × (n + 1) subproblems. If we know E(i − 1, j), E(i, j − 1), and

E(i − 1, j − 1) then to compute the value E(i, j) it is necessary to make 3
operations of comparisons of numbers (1 to find the value diff(i, j), and 2 to find
min) and 3 operations of addition
• So, the considered algorithm makes O(mn) operations of addition and
comparison of numbers
19
Edit Distance

• To find the value E(m, n) we should fill the table with m + 1 rows labeled with
numbers 0, 1, . . . , m, and n + 1 columns labeled with numbers 0, 1, . . . n
• At the intersection of i-th row and j-th column we should have the number E(i, j)
• At the beginning, we can fill values E(i, 0) = i and E(0, j) = j, and after that
row by row, from the left to the right we can fill out the table
• Note that it is not necessary to have the whole table in the memory: to fill the
i-th row, i > 0, it is enough to know values in the row i − 1

20
Edit Distance

• Now we can find the optimal alignment if the considered table is filled
• If E(m, n) = 1 + E(m − 1, n), then in the optimal alignment the last column is
xm

−
• If E(m, n) = 1 + E(m, n − 1), then in the optimal alignment the last column is yn
• If E(m, n) = diff(m, n) + E(m − 1, n − 1), then in the optimal alignment the last
column is xym
n

• To find the next column we should consider: In the first case—the subproblem
E(m − 1, n). In the second case—the subproblem E(m, n − 1) and in the third
case - the subproblem E(m − 1, n − 1), etc

21
Edit Distance: Example

S U N N Y
0 1 2 3 4 5 xi xi
S 1 0 1 2 3 4 yj
N 2 1 1 1 2 3 i − 1, j − 1 i − 1, j
O 3 2 2 2 2 3 i, j − 1 i, j
W 4 3 3 3 3 3 yj i, j − 1 i, j
Y 5 4 4 4 4 3

S N O W Y S N O W Y S N O W Y
S U N N Y S U N N Y S U N N Y

22
Shortest Path: Floyd-Warshall Algorithm

• Let G be a complete directed graph with n vertices v1 , v2 , . . . , vn

• Each edge (vi , vj ) has a label dij ∈ R ∪ {+∞}
• We say that dij is the length of the edge (vi , vj ). Clearly, dii = 0 for i = 1, . . . , n
• The length of a directed path from vi to vj is equal to +∞ if the length of at
least one edge in the path is equal to +∞
• It is possible to have negative lengths i.e., dij < 0 however there is no directed
cycle with negative length (no negative cycles)

23
Shortest Path: Floyd-Warshall Algorithm

• The minimum distance d∗ij from vi to vj is equal to the minimum length of a

directed path from vi to vj
• For a given n × n matrix D = [dij ] of lengths of edges, we should construct the
matrix D∗ = [d∗ij ] of minimal distances
• For any i, j ∈ {1, . . . , n} and k ∈ {0, 1, . . . , n} let us consider the following
(k)
subproblem to compute dij which is the length of the shortest path from vi to vj
in which only vertices v1 , . . . , vk can be used as intermediate vertices. If k = 0
(0)
then dij = dij

24
Shortest Path: Floyd-Warshall Algorithm

(k)
• Let D(k) = [dij ]. Then D(0) = D and D(n) = D∗ , we will sequentially compute
D(1) , D(2) , . . ., D(n) . Let us prove that for every i, j and k > 0
n o
(k) (k−1) (k−1) (k−1)
dij = min dij , dik + dkj .

• All directed paths from vi to vj that use only v1 , . . . , vk as intermediate vertices

can be divided into two sets A and B which do not pass through vk and which
pass through vk , respectively
(k−1)
• The minimum length of path from A is equal to dij . Since there are no
negative cycles in G, there exists a shortest path τ from B which passes through
vk exactly once.

25
Shortest Path: Floyd-Warshall Algorithm

• So τ can be divided into two paths: a path from vi to vk which use only vertices
(k−1)
v1 , . . . , vk−1 (the minimum length of such a path is equal to dik and a path
from vk to vj which uses only vertices v1 , . . . , vk−1 (the minimum length of such
(k−1)
a path is equal to dkj
(k−1) (k−1)
• Therefore, the length of τ is equal to dik + dkj and the considered equality
holds
• If we know D(k−1) then to compute D(k) it is enough to make n2 operations of
additions and n2 operations of comparisons of numbers
• Therefore, to compute D(n) = D∗ it is enough to make O(n3 ) operations of
addition and comparisons

26
Shortest Path: Floyd-Warshall Algorithm: Example

2 1
+∞ −1

4
1 3

−2

27
Shortest Path: Floyd-Warshall Algorithm: Example

For this example

n we compute the shortest
o path as following: for every i, j and k > 0,
(k) (k−1) (k−1) (k−1) (k) (k−1)
dij = min dij , dik + dkj . If i = k or j = k, then dij = dij .

1 2 3 1 2 3
1 0 +∞ −2 1 0 +∞ −2
D(0) = , D(1) =
2 2 0 −1 2 2 0 -1
3 4 1 0 3 4 1 0

1 2 3 1 2 3
1 0 +∞ -2 1 0 -1 −2
D(2) = , D(3) = = D∗
2 2 0 −1 2 2 0 −1
3 3 1 0 3 3 1 0

28