Recursive Formula
Let
c
[
i
,
j
] be the length of the LCS of
X
i
and
Y
j
(prefixes).
Next:
Algorithm
Up:
LONGEST COMMON SUBSEQUENCE
Previous:
Optimal Substructure Theorem
![\begin{displaymath}
c[i,j] = \left\{ \begin{array}
{ll}
0 & \mbox{if $i=0$ or $...
...max(c[i,j-1],c[i-1,j]) & \mbox{otherwise}.
\end{array} \right.\end{displaymath}](img11.gif)
