### USACO — Dynamic Programming — Longest Common Subsequence

Posted:

**Wed Nov 14, 2012 3:12 pm**I've used this recursive relation to solve this classic problem. Here it is:

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

It it a bit different with my solution. Instead of , it's used below code.

Why this solution just checks and doesn't check ?

Does this solution guarantee to find the correct answer?

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

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]);
```

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
```

Code: Select all

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

Code: Select all

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

Code: Select all

`length[loc+1,element]`

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...