Q54

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] The value of $l(i,j)$ could be obtained by dynamic programming based on the correct recursive definition of $l(i,j)$ of the form given above, using an array $L[M,N]$, where $M = m+1$ and $N = n+1$, such that $L[i, j] = l(i, j)$. Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of $l(i, j)$?