PUERTA | PUERTA-CS-2009 | Pregunta 53

Una subsecuencia de una secuencia dada es solo la secuencia dada con algunos elementos (posiblemente ninguno o todos) omitidos. Nos dan dos secuencias X[m] e Y[n] de longitudes m y n respectivamente, con índices de X e Y a partir de 0.
Deseamos encontrar la longitud de la subsecuencia común más larga (LCS) de X[ m] e Y[n] como l(m,n), donde a continuación se proporciona una definición recursiva incompleta de la función l(i,j) para calcular la longitud del LCS de X[m] e Y[n]:

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] 

(A) expr1 ≡ l(i-1, j) + 1
(B) expr1 ≡ l(i, j-1)
(C) expr2 ≡ max(l(i-1, j), l(i, j- 1))
(D) expr2 ≡ max(l(i-1,j-1),l(i,j))

Respuesta: (C)
Explicación: En el problema de la subsecuencia común más larga , hay dos casos para X[0. .i] y Y[0..j]

1) The last characters of two strings match. 
   The length of lcs is length of lcs of X[0..i-1] and Y[0..j-1]
2) The last characters don't match.
   The length of lcs is max of following two lcs values
   a) LCS of X[0..i-1] and Y[0..j]
   b) LCS of X[0..i] and Y[0..j-1]

Cuestionario de esta pregunta