Chapter 5 – Dynamic

Programming
Adama Science and Technology University
School of Electrical Engineering and Computing
Department of CSE
Dr. Mesfin Abebe Haile (2024)
 Outline

 Dynamic Programming:
 Longest Common Subsequence,
 Optimal Substructure,
 Overlapping Subproblems.

11/14/25 2
 Dynamic
Programming
 Dynamic programming is like the divide-and-conquer method. It
solves problems by combining the solutions of the subproblems.
 Divide-and-conquer algorithms partition the problem into
disjoint subproblems, solve the subproblems recursively, and
then combine their solutions.

 Dynamic programming applies when the subproblems overlap

that meas subproblems share subsubproblems.
 Dynamic
Programming
 Dynamic programming (DP) typically applies to optimization
problems that have many possible solution. (it also used in combinatorial)
 Each solution has a value, and we want to find a solution with
the optimal value (minimum or maximum).
 The key strategy is to store the solution to each such subproblem
rather than recompute it.
 This simple idea can sometimes transform exponential-time
algorithms into polynomial-time algorithms.
 Dynamic
Programming
 To develop a dynamic-programming algorithm, follow the
following of four steps:
 Characterize the structure of an optimal solution.
 Recursively define the value of an optimal solution.
 Compute the value of an optimal solution, typically in a bottom-up
fashion.
 Construct an optimal solution from computed information.
Dynamic Programming
 Dynamic
Programming
 When should we look for a dynamic-programming solution to
a problem?
 There are two key ingredients that an optimization problem must
have in order to apply dynamic programming :
Optimal substructure and
Overlapping subproblems.
 Dynamic
Programming

 Example: 1 + 2 + 3 + 4 + 5 … + n (arithmetic series). What is the

sum of the n elements.
 F(1) = 1
 F(2) = F(1) + 2 = 1 + 2 = 3
 F(3) = F(2) + 3 = 3 + 3 = 6
.....
.....
 F(n) = F(n-1) + n
 Dynamic
Programming

 Example: Longest Common Subsequence (LCS)

 Given two sequences x[1 . . m] and y[1 . . n], find a longest
subsequence common to them both.
 To determine the similarity of the two sequences and to measure
how they are related:
If one is the substring of the other,
If the number of changes needed to turn one into the other is small.
By finding a third sequences which consist of the common
elements of the two (the same order).
 Dynamic
Programming

 Design technique, like divide-and-conquer to solves problems by

combining the solutions to subproblems.
 Example: Longest Common Subsequence (LCS)
 Given two sequences x[1 . . m] and y[1 . . n], find a longest
subsequence common to them both.
“a” not “the”
 Dynamic
Programming

 Design technique, like divide-and-conquer to solves problems by

combining the solutions to subproblems.
 Example: Longest Common Subsequence (LCS)
 Given two sequences x[1 . . m] and y[1 . . n], find a longest
subsequence common to them both.
“a” not “the”

x: A B C B D A B
y: B D C A B A
 Dynamic
Programming

 Design technique, like divide-and-conquer.

 Example: Longest Common Subsequence (LCS)
 Given two sequences x[1 . . m] and y[1 . . n], find a longest
subsequence common to them both. “a” not “the”

x: A B C B D A B
BCBA =
LCS(x, y)
y: B D C A B A
Functional notation, but not a function
 Brute-force LCS
Algorithm

 Check every subsequence of x[1 . . m] to see if it is also a

subsequence of y[1 . . n].
 Given two sequences X and Y , we say that a sequence Z is a
common subsequence of X and Y if Z is a subsequence of both
X and Y.
 For example, if X = {A;B;C;B;D;A;B} and Y = {B;D;
C;A;B;A}, the sequence {B;C;A} is a common subsequence of
both X and Y.
 The sequence {B; C; A} is not a longest common subsequence
(LCS) of X and Y , since it has length 3. {B; C; B; A} = 4.
 Brute-force LCS
Algorithm
 Check every subsequence of x[1 . . m] to see if it is also a
subsequence of y[1 . . n].
 Analysis:
 Checking = O(n) time per subsequence.
 2m subsequences of x (each bit-vector of length m determines
a distinct subsequence of x). (Brute-force approach)
 Worst-case running time = O(n2m)
= exponential time, makes it
impractical for long sequences.
 Towards a Better
Algorithm
 Simplification:

 Look at the length of a longest-common subsequence.

 Extend the algorithm to find the LCS itself.
 Towards a Better
Algorithm
 Simplification:
 Look at the length of a longest-common subsequence.
 Extend the algorithm to find the LCS itself.
 Notation: Denote the length of a sequence s by | s |.
 Towards a Better
Algorithm
 Simplification:
 Look at the length of a longest-common subsequence.
 Extend the algorithm to find the LCS itself.
 Notation: Denote the length of a sequence s by | s |.
 Strategy: Consider prefixes of x and y.
 Define c[i, j] = | LCS(x[1 . . i], y[1 . . j]) |.
 Then, c[m, n] = | LCS(x, y) |.
 Recursive
Formulation
 Theorem:
c[i–1, j–1] + 1 if x[i] = y[j],
c[i, j] = max{c[i–1, j], c[i, j–1]} otherwise.
 Recursive Formulation
 Theorem:
c[i–1, j–1] + 1 if x[i] = y[j],
c[i, j] = max{c[i–1, j], c[i, j–1]} otherwise.

 Proof: Case x[i] = y[ j]:

1 2 m
x: i L
= j
1 2 n
y: L
 Recursive Formulation
 Theorem.
c[i–1, j–1] + 1 if x[i] = y[j],
c[i, j] = max{c[i–1, j], c[i, j–1]} otherwise.

 Proof. Case x[i] = y[ j]:

1 2 m
x: i L
1 2 = j n
y: L

 Let z[1 . . k] = LCS(x[1 . . i], y[1 . . j]), where c[i, j]= k. Then, z[k] = x[i], or else
z could be extended. Thus, z[1 . . k–1] is CS of x[1 . . i–1] and y[1 . . j–1].
 Proof (Continued)

 Claim: z[1 . . k–1] = LCS(x[1 . . i–1], y[1 . . j–1]).

 Suppose w is a longer CS of x[1 . . i–1] and y[1 . . j–1], that is, |
w | > k–1.
 Then, cut and paste: w || z[k] (w concatenated with z[k]) is a
common subsequence of x[1 . . i] and y[1 . . j] with | w || z[k] |
> k. Contradiction, proving the claim.
 Proof (Continued)

 Claim: z[1 . . k–1] = LCS(x[1 . . i–1], y[1 . . j–1]).

 Suppose w is a longer CS of x[1 . . i–1] and y[1 . . j–1], that is, | w
| > k–1.
 Then, cut and paste: w || z[k] (w concatenated with z[k]) is a
common subsequence of x[1 . . i] and y[1 . . j] with | w || z[k] | > k.
Contradiction, proving the claim.
 Thus, c[i–1, j–1] = k–1, which implies that c[i, j] = c[i–1, j–1] + 1.
 Other cases are similar.
Dynamic-Programming
Hallmark #1

Optimal substructure
An optimal solution to a problem (instance)
contains optimal solutions to subproblems.
 Dynamic-Programming
Hallmark #1

Optimal substructure
An optimal solution to a problem (instance)
contains optimal solutions to subproblems.

If z = LCS(x, y), then any prefix of z is an LCS of a prefix of

x and a prefix of y.
Recursive Algorithm for
LCS

LCS(x, y, i, j)
if x[i] = y[ j]
then c[i, j]  LCS(x, y, i–1, j–1) + 1
else c[i, j]  max{LCS(x, y, i–1, j),
LCS(x, y, i, j–1)}
 Recursive Algorithm for
LCS

LCS(x, y, i, j)
if x[i] = y[ j]
then c[i, j]  LCS(x, y, i–1, j–1) + 1
else c[i, j]  max{LCS(x, y, i–1, j),
LCS(x, y, i, j–1)}

Worst-case: x[i]  y[j], in which case the algorithm

evaluates two subproblems, each with only one parameter
decremented.
Recursion Tree
 Recursion Tree

m+n

 Height = m + n  work potentially exponential.

 Recursion Tree

m+n

 Height = m + n  work potentially exponential., but we’re

solving subproblems already solved!
Dynamic-Programming
Hallmark #2

Overlapping subproblems
A recursive solution contains a “small” number
of distinct subproblems repeated many times.
Dynamic-Programming
Hallmark #2

Overlapping subproblems
A recursive solution contains a “small” number
of distinct subproblems repeated many times.

The number of distinct LCS subproblems for two strings of

lengths m and n is only mn.
 Memoization Algorithm

 Memoization: After computing a solution to a

subproblem, store it in a table. (to improve recursion)
 Subsequent calls check the table to avoid redoing work.
 Memoization Algorithm

 Memoization: After computing a solution to a

subproblem, store it in a table.
 Subsequent calls check the table to avoid redoing work.

LCS(x, y, i, j)
if c[i, j] = NIL
then if x[i] = y[j]
then c[i, j]  LCS(x, y, i–1, j–1) + 1 Same
else c[i, j]  max{LCS(x, y, i–1, j), as
LCS(x, y, i, j–1)} before
 Memoization Algorithm
 Memoization: After computing a solution to a
subproblem, store it in a table.
 Subsequent calls check the table to avoid redoing work.
LCS(x, y, i, j)
if c[i, j] = NIL
then if x[i] = y[j]
then c[i, j]  LCS(x, y, i–1, j–1) + 1 Same
else c[i, j]  max{LCS(x, y, i–1, j), as
LCS(x, y, i, j–1)} before
 Time = (mn) = constant work per table entry.
 Space = (mn).
 Dynamic-Programming
Algorithm
IDEA:
Compute the table
bottom-up.
 Dynamic-Programming
Algorithm
IDEA:
Compute the table
bottom-up.
Time = (mn).
 Dynamic-Programming
Algorithm
IDEA:
Compute the table
bottom-up.
Time = (mn).
Reconstruct LCS by
tracing backwards.
 Dynamic-Programming
Algorithm
IDEA:
Compute the table
bottom-up.
Time = (mn).
Reconstruct LCS by
tracing backwards.
Space = (mn).
Dynamic-Programming
Algorithm
 Question & Answer

11/14/25 40
 Thank You !!!

11/14/25 41
 Exercises - 5

 Determine an LCS of x = (1; 0; 0; 1; 0; 1; 0; 1) and y = (0; 1;

0; 1; 1; 0; 1; 1; 0). Use tabulation (bottom- up) approach.

11/14/25 42