USACO — Dynamic Programming — Longest Common Subsequence

[Blackwizard]

I've used this recursive relation to solve this classic problem. Here it is:

Code: Select all

if (I == n || J == m)
        dp[I][J] = 0;
else if (x[I] == y[J])
        dp[I][J] = dp[I+1][J+1] + 1;
else
        dp[I][J] = max (dp[I+1][J], dp[I][J+1]);

but I've seen the USACO TEXT about Dynamic Programming, that it used this pseudocode for this problem:

Code: Select all

   # the tail of the second sequence is empty
 1   for element = 1 to length1
 2     length[element, length2+1] = 0

    # the tail of the first sequence has one element
 3   matchelem = 0
 4   for element = length2 to 1
 5     if list1[length1] = list2[element]
 6       matchelem = 1
 7     length[length1,element] = nmatchlen

    # loop over the beginning of the tail of the first sequence
 8   for loc = length1-1 to 1
 9     maxlen = 0
10     for element = length2 to 1

    # longest common subsequence doesn't include first element
11       if length[loc+1,element] > maxlen
12         maxlen = length[loc+1,element]

    # longest common subsequence includes first element
13       if list1[loc] = list2[element] &&
14                       length[loc+1,element+1]+1 > maxlen
15           maxlen = length[loc,element+1] + 1

16     length[loc,element] = maxlen

It it a bit different with my solution. Instead of

Code: Select all

dp[I][J] = max (dp[I+1][J], dp[I][J+1]);

, it's used below code.

Code: Select all

    # longest common subsequence doesn't include first element
11       if length[loc+1,element] > maxlen
12         maxlen = length[loc+1,element]

Why this solution just checks

Code: Select all

length[loc+1,element]

and doesn't check

Code: Select all

length[loc,element+1]

?
Does this solution guarantee to find the correct answer?

Please guide me to get this point! Thanks for you help...

[brianfry713]

en.wikipedia.org/wiki/Longest_common_subsequence_problem

[Blackwizard]

Thank for replying and good link!
I know this solution and It is like my solution.It iterate on the X and Y from the first to last, but my solution iterate on X and Y from the last to first!
Here it is the solution:



But in the usaco pseudocode, if "X_i != Y_i", it don't choose "longest(LCS(X_i, Y_j-1), LCS(X_i-1, Y_j))", It just choose "LCS(X_i-1, Y_j)"!
Here is the pseudocode for this part:

Code: Select all

    # longest common subsequence doesn't include first element
11       if length[loc+1,element] > maxlen
12         maxlen = length[loc+1,element]