If the last characters of strings X and Y are equal, LCS recurrence says
ALCS(X, Y) = max(LCS(X without last, Y), LCS(X, Y without last))
BLCS(X, Y) = LCS(X without last, Y without last) + that character
CLCS(X, Y) = LCS(X without last, Y without last) (skipping the character)
DLCS(X, Y) = the empty string
Answer & Solution
Correct answer: B. LCS(X, Y) = LCS(X without last, Y without last) + that character
When x_m = y_n, that character is guaranteed in the LCS, and the rest of the LCS comes from the LCS of the two strings minus their last characters. Hence LCS(X, Y) = LCS(X_{m-1}, Y_{n-1}) + x_m. The max-of-two formula is for the case x_m ≠ y_n; skipping the matching character or returning empty is wrong.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for