資料結構與演算法

(4 points) Let $X[1 \dots m]$ and $Y[1 \dots n]$ be two sequences. Let $L[i][j]$ denote the length of the longest common subsequence (LCS) of the prefixes $X[1 \dots i]$ and $Y[1 \dots j]$, and let $C[i][j]$ denote the number of distinct LCSs (distinct sequences, not dynamic programming paths or alignments) of these prefixes. Let $C[i][0] = C[0][j] = 1$, since the empty sequence is the unique LCS in these cases. Which of the following recurrences correctly computes $C[i][j]$ without double counting identical LCS sequences?

Here, "without double counting" means that each distinct LCS sequence is counted exactly once, even if it can be obtained from multiple dynamic programming subproblems or alignments. In particular, when multiple subproblems yield LCSs of the same optimal length, any LCS sequence that appears in more than one subproblem must be counted only once.