there is a quiz about the running time of dynamic program, and there is one choice I find the explanation seemed to be incorrect.
The question is:
The following problems all take as input two strings X and Y, of length m and n, over some alphabet Σ. Which of them can be solved in O(mn) time? [Check all that apply.]
and the choice I have doubt is
Compute the length of a longest common subsequence of X and Y. (Recall a subsequence need not be consecutive. For example, the longest common subsequence of "abcdef" and "afebcd" is "abcd".)
the explanation for it is
Similar dynamic programming to sequence alignment, with one subproblem for each X_i and Y_j. Alternatively, this reduces to sequence alignment by setting the gap penalty to 1 and making the penalty of matching two different characters to be very large.
it says commputing the lenght of a longest common subsequence can be solved by using dynamic programming for sequence alignment by setting the gap penalty to be 1 and the mismatch penalty to be very large. Then suppose I have string X and Y as following:
string X: ABCDEFGGGGABCDE
string Y: ABCDEGGGGABCDEF
by using the dynamic programming for sequence alignment, as we don't want mismatch, the result would be
string X: ABCDE F GGGGABCDE (gap)
string Y: ABCDE (gap)GGGGABCDE F
which would miss the 'F' for the subsequent right?