Longest Common Subsequence

Longest Common Subsequence

• How similar are these two species?

DNA: DNA:
AGCCCTAAGGGCTACCTAGCTT GACAGCCTACAAGCGTTAGCTTG
 Longest Common Subsequence

• How similar are these two species?

DNA: DNA:
AGCCCTAAGGGCTACCTAGCTT GACAGCCTACAAGCGTTAGCTTG
• Pretty similar, their DNA has a long common subsequence:

AGCCTAAGCTTAGCTT
Longest Common Subsequence

• Subsequence:
• BDFH is a subsequence of ABCDEFGH
• If X and Y are sequences, a common subsequence
• is a sequence which is a subsequence of both.
• BDFH is a common subsequence of ABCDEFGH and of
ABDFGHI
• A longest common subsequence…
• …is a common subsequence that is longest.
• The longest common subsequence of ABCDEFGH and
ABDFGHI is ABDFGH.
Steps for applying Dynamic Programming
• Step 1: Identify optimal substructure.
• Step 2: Find a recursive formulation for the
length of the longest common subsequence.
• Step 3: Use dynamic programming to find
the length of the longest common
subsequence.
• Step 4: If needed, keep track of some additional
info so that the algorithm from Step 3 can find
the actual LCS.
Step 1: Optimal substructure
Prefixes:

X A C G G T

Y A C G C T T A

Notation: denote this prefix ACGC by Y4

• Our sub-problems will be finding LCS’s of prefixes to X and Y.

• Let C[i,j] = length_of_LCS( Xi, Yj )
Examples: C[2,3] = 2
C[4,4] = 3
Optimal substructure ctd.

• Subproblem:
• finding LCS’s of prefixes of X and Y.

• Why is this a good choice?

• As we will see, there’s some relationship between LCS’s
of prefixes and LCS’s of the whole things.
• These subproblems overlap a lot.
Steps for applying Dynamic Programming
• Step 1: Identify optimal substructure.

• Step 2: Find a recursive formulation for the

length of the longest common subsequence.
• Step 3: Use dynamic programming to find
the length of the longest common
subsequence.
• Step 4: If needed, keep track of some additional
info so that the algorithm from Step 3 can find
the actual LCS.
Goal

• Write C[i,j] in terms of the solutions to smaller subproblems

i

Xi A C G G A
j

Yj A C G C T T A

C[i,j] = length_of_LCS( Xi, Yj )

 • Our sub-problems will be finding
Two cases LCS’s of prefixes to X and Y.
• Let C[i,j] = length_of_LCS( Xi, Yj )
Case 1: X[i] = Y[j]
i These are
the same

Xi A C G G A
j

Yj A C G C T T A

• Then C[i,j] = 1 + C[i-1,j-1].

• because LCS(Xi,Yj) = LCS(Xi-1,Yj-1) followed by A
 • Our sub-problems will be finding
Two cases LCS’s of prefixes to X and Y.
• Let C[i,j] = length_of_LCS( Xi, Yj )
Case 2: X[i] != Y[j]
i These are
not the
same
Xi A C G G T
j

Yj A C G C T T A

• Then C[i,j] = max{ C[i-1,j], C[i,j-1] }.

• either LCS(Xi,Yj) = LCS(Xi-1,Yj) and T is not involved,
• or LCS(Xi,Yj) = LCS(Xi,Yj-1) and A is not involved,
• (maybe both are not involved, that’s covered by the “or”)
 Recursive formulation of the optimal solution
X0
Yj A C G C T T A

Case 0
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0

Case 1 Case 2

Xi A C G G A Xi A C G G T

Yj A C G C T T A Yj A C G C T T A
Steps for applying Dynamic Programming
• Step 1: Identify optimal substructure.
• Step 2: Find a recursive formulation for the
length of the longest common subsequence.

• Step 3: Use dynamic programming to find

the length of the longest common
subsequence.
• Step 4: If needed, keep track of some additional
info so that the algorithm from Step 3 can find
the actual LCS.
LCS DP
• LCS(X, Y):
• C[i,0] = C[0,j] = 0 for all i = 0,…,m, j=0,…n.
• For i = 1,…,m and j = 1,…,n:
• If X[i] = Y[j]:
• C[i,j] = C[i-1,j-1] + 1
• B[i,j] = “ ”
• Else:
• If C[i-1, j] >= C[i, j-1]
• C[i, j] = C[i-1, j]
• B[i, j] = “ ”
• Else:
• C[i,j] = C[i, j-1]
• B[i,j] = “ ”

• Return C and B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
LCS DP
• LCS(X, Y):
• C[i,0] = C[0,j] = 0 for all i = 0,…,m, j=0,…n.
• For i = 1,…,m and j = 1,…,n:
• If X[i] = Y[j]:
• C[i,j] = C[i-1,j-1] + 1
• B[i,j] = “ ”
• Else:
• If C[i-1, j] >= C[i, j-1]
• C[i, j] = C[i-1, j]
• B[i, j] = “ ”
• Else:
• C[i,j] = C[i, j-1]
• B[i,j] = “ ”

• Return C and B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

A A

C C

X G X G

G G

A A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 A

C 0 C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 A

C 0 C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 A

C 0 C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 A

C 0 C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 A

C 0 C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 A

C 0 C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 A

C 0 C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 A

C 0 C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 A

C 0 C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 A

C 0 C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

C 0 C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

C 0 C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 C
C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 C
C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 2 C
C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 2 C
C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 2 2 C
C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 2 2 C
C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 2 2 C
C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 2 2 2 C
C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 2 2 2 C
C

X G 0 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 2 2 2 C
C

X G 0 1 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 2 2 2 C
C

X G 0 1 2 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 2 2 2 C
C

X G 0 1 2 2 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 2 2 2 C
C

X G 0 1 2 2 2 X G

G 0 G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 2 2 2 C
C

X G 0 1 2 2 2 X G
0 1 2 2
G G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 2 2 2 C
C

X G 0 1 2 2 2 X G
0 1 2 2 3
G G

A 0 A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 2 2 2 C
C

X G 0 1 2 2 2 X G
0 1 2 2 3
G G

0 1
A A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Example X A C G G A Y A C T G

Y Y
A C T G A C T G

0 0 0 0 0

A 0 1 1 1 1 A

0 1 2 2 2 C
C

X G 0 1 2 2 2 X G
0 1 2 2 3
G G

0 1 2 2 3
A A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Steps for applying Dynamic Programming
• Step 1: Identify optimal substructure.
• Step 2: Find a recursive formulation for the
length of the longest common subsequence.
• Step 3: Use dynamic programming to find
the length of the longest common
subsequence.

• Step 4: If needed, keep track of some

additional info so that the algorithm from Step
3 can find the actual LCS.
Example X A C G G A Y A C T G

Y
A C T G

X G

Table B
Example X A C G G A Y A C T G

Y
A C T G

X G

Table B
Example X A C G G A Y A C T G

Y
A C T G

X G

Table B
Example X A C G G A Y A C T G

Y
A C T G

G A

X G

Table B
Example X A C G G A Y A C T G

Y
A C T G

G A

X G

Table B
Example X A C G G A Y A C T G

Y
A C T G

G A

X G

Table B
Example X A C G G A Y A C T G

Y
A C T G

G A

X G

Table B
Example X A C G G A Y A C T G

Y
A C T G

C G A

X G

Table B
Example X A C G G A Y A C T G

Y
A C T G

C G A

X G

Table B
Example X A C G G A Y A C T G

Y
A C T G

A C G A

X G

Table B
Example2 X A B C B D A B Y B D C A B A
Example2 X A B C B D A B Y B D C A B A

B D C A B A B D C A B A

Table C Table B
0 𝑖𝑓 𝑖 = 0 𝑜𝑟 𝑗 = 0
𝐶 𝑖, 𝑗 = ൞𝐶 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑋 𝑖 = 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖, 𝑗 − 1 𝑖𝑓𝑋 𝑖 ≠ 𝑌 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 > 0
Steps for applying Dynamic Programming
Step 4: If needed, keep track of some additional info so that
the algorithm from Step 3 can find the actual LCS.

Algorithm

PRINT-LCS(𝐵, 𝑋, 𝑖, 𝑗)
1 if 𝑖 == 0 or 𝑗 == 0
2 return // the LCS has length 0
3 if 𝐵 𝑖, 𝑗 == “ ”
4 PRINT-LCS(𝐵, 𝑋, 𝑖, −1 𝑗 − 1)
5 print 𝑋[𝑖] // same as 𝑌[𝑗]
6 elseif 𝐵 𝑖, 𝑗 == “↑”
7 PRINT-LCS(𝐵, 𝑋, 𝑖, −1 𝑗)
8 else
9 PRINT-LCS(𝐵, 𝑋, 𝑖, 𝑗 − 1)