Data Structures and Algorithms
|Longest Common Subsequence
Another problem that has a dynamic solution is that
of finding the longest common subsequence.
Given two sequences of symbols, X and Y,
determine the longest subsequence of symbols that appears
in both X and Y.
Cormen, Section 16.3
Lecture notes by Kirk Pruhs, University of Pittsburgh
Pseudo-code from John Stasko's notes for CS3158 at Georgia Tech
- optimal sub-structure
- a property of optimisation problems in which the sub-problems
which constitute the solution to the problem itself are themselves
optimal solutions to those sub-problems.
This property permits the construction of dynamic algorithms to
solve the problem.
© John Morris, 1998