A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences $X[m]$ and $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$.
We wish to find the length of the longest common sub-sequence (LCS) of $X[m]$ and $Y[n]$ as $l(m, n)$, where an incomplete recursive definition for the function $I(i, j)$ to compute the length of the LCS of $X[m]$ and $Y[n]$ is given below:
l(i,j) = 0, if either i = 0 or j = 0
= expr1, if i,j > 0 and X[i-1] = Y[j-1]
= expr2, if i,j > 0 and X[i-1] ≠ Y[j-1]
Which one of the following options is correct?
-
$\text{expr1} = l\left(i-1, j\right) +1$
-
$\text{expr1} = l\left(i, j-1\right)$
-
$\text{expr2} = \max\left(l\left(i-1, j\right), l\left(i,j-1\right)\right)$
-
$\text{expr2} = \max\left(l\left(i-1, j-1\right), l\left(i,j\right)\right)$