Finding the longest common subsequence from two strings, is one of the
example in Dynamic Programming Chapter in INTRODUCTION ALGORITHMS by
Cormen.
It can be solved using a tabular and bottom-up approach:
LCS-LENGTH(X, Y)
m <- length[X]
n <- length[Y]
for i <- 1 to m
do c[i, 0] <- 0
for j <- 1 to n
do c[0, j] <- 0
for i <- 1 to m
do for j <- 1 to n
do if X[i] = Y[j]
then c[i, j] <- c[i - 1, j - 1] + 1
b[i, j] <- "NORTHWEST"
else if c[i - 1, j] >= c[i, j - 1]
then c[i, j] <- c[i - 1, j]
b[i, j] <- "NORTH"
else c[i, j] <- c[i, j - 1]
b[i, j] <- "WEST"
return c and b
c[i, j] is the length of an LCS of the sequences Xi and Yj( we define
Xi like this: e.g. if X = <A,B,D,C,A>, and i = 4 then Xi = <A,B,D,C> )
b[i, j] is the side-effect of the algorithm LCS-LENGTH(X, Y), from
which the LCS can be derived like this:
PRINT-LCS(b, X, i, j)
if i = 0 or j = 0
then return
if b[i, j] = "NORTHWEST"
then PRINT-LCS(b, X, i - 1, j - 1)
print X[i]
else if b[i, j] = "NORTH"
then PRINT-LCS(b, X, i - 1, j)
else PRINT-LCS(b, X, i, j - 1)
some may say, "you can eliminate the b table altogether, because each
c[i, j] entry depends on only three other c table entries: c[i - 1, j -
1], c[i - 1, j], c[i, j - 1]". But that's not my problem. My problem
is: how can I solve it using the memoization style i.e. the top-down
strategy, the recursive approach with a storage table with which
overlapped subproblems need only one computation?
Or, for simplicity, you may use a RECURSIVE-LCS-LENGTH algorithm, but
you should get the correct b table which is more important to this
problem.
Thank you.
