Why does this DP solution for longest common subsequence work correctly?

Question

Concerning the longest common subsequence problem, the basic algorithm as presented in all online resources is clear to me. This algorithm is described here:

What I am not clear is the algorithm presented for the dynamic programming version of the algorithm which is everywhere as follows:

function LCSLength(X[1..m], Y[1..n])  
    C = array(0..m, 0..n)  
    for i := 0..m  
       C[i,0] = 0  
    for j := 0..n  
       C[0,j] = 0  
    for i := 1..m  
        for j := 1..n  
            if X[i] = Y[j]  
                C[i,j] := C[i-1,j-1] + 1  //Here shouldn't we change i?
            else  
                C[i,j] := max(C[i,j-1], C[i-1,j])  
    return C[m,n]   

But I don't see how the DP version is equivalent. What troubles me is the fact that in the DP version when we find that X[i] == Y[j] in the inner loop, we continue calculating the DP with the same i; i.e. the rest of the inner loop keep comparing with the same X[i]. Since the recursive algorithm says that we should evaluate C[i - 1, j - 1], shouldn't we continue on to the next i?

Answer 1

The idea behind dynamic programming is to evaluate the recursive function in reverse, starting with the base cases and iteratively building up the answer for larger and larger sub problems until the answer has been computed for the overall input problem.

If you were evaluating this function recursively, then you would absolutely recurse in the case you've mentioned by decrementing i and j. However, in the dynamic programming version, you aren't starting with LCS[i, j] and trying to evaluate it by evaluating LCS[i-1, j-1]. You're starting with LCS[i-1, j-1] and using it to evaluate LCS[i, j].

Specifically, what this code is doing is first computing LCS[i, 0] and LCS[0, j] for all i and j by directly using the base case solution. Next, it's using the fact that LCS[0, j] is known for all j to compute LCS[1, j] for all j. Then it uses the fact that LCS[1, j] is known for all j to compute LCS[2, j] for all j, and so on and so forth.

As a result, then it comes time to compute LCS[i, j] and your particular case applies, the algorithm doesn't need to decrement i or j and recursively descend downward. It's already computed LCS[i-1, j-1], so it can just read off the value and keep building up the rest of the values in the table.

It might be easiest to see this visually. Let's suppose that you want to find the LCS of the strings "canon" and "annie". We start off with this 2D table:

    A N N I E
  . . . . . .
C . . . . . .
A . . . . . .
N . . . . . .
O . . . . . .
N . . . . . .

Initially, we set LCS[0, j] = LCS[i, 0] = 0 for all i and j:

    A N N I E
  0 0 0 0 0 0
C 0 . . . . .
A 0 . . . . .
N 0 . . . . .
O 0 . . . . .
N 0 . . . . .

Now, we're going to go row-by-row through this table and fill in the missing entries using the recurrence described in your original question. When going through the first row, we will be comparing the letter C against all the letters in the word "ANNIE." We never find a match, so we always use the recurrence LCS[i, j] = max(LCS[i - 1, j] + LCS[i, j - 1]). This always evaluates to zero, so we get this:

    A N N I E
  0 0 0 0 0 0
C 0 0 0 0 0 0
A 0 . . . . .
N 0 . . . . .
O 0 . . . . .
N 0 . . . . .

This makes sense, since the first row of this table represents the length of the LCS of the string C and all prefixes of ANNIE.

In the next row, we're going to try to find the LCS of the string CA and all suffixes of ANNIE. The first entry we consider matches A against A. Since this is a match, we use the recurrence LCS[i, j] = 1 + LCS[i - 1, j - 1], which evaluates to 1:

    A N N I E
  0 0 0 0 0 0
C 0 0 0 0 0 0
A 0 1 . . . .
N 0 . . . . .
O 0 . . . . .
N 0 . . . . .

Again, we can sanity-check this by noting that the LCS of "CA" and "A" is the sequence A, which has length 1.

The important detail here is that we do not decrement i or j here. We still need to fill in the rest of this row, and so we're going to continue onward.

For the rest of the entries of this row, we're going to compare the A against every character of ANNIE and find that it doesn't match. Accordingly, we'll use the recurrence LCS[i, j] = max(LCS[i-1, j], LCS[i, j-1]), which will always evaluate to 1 by picking up the 1 from the rest of the row. This is shown here:

    A N N I E
  0 0 0 0 0 0
C 0 0 0 0 0 0
A 0 1 1 1 1 1
N 0 . . . . .
O 0 . . . . .
N 0 . . . . .

Carrying onward to the next row gives us the following:

    A N N I E
  0 0 0 0 0 0
C 0 0 0 0 0 0
A 0 1 1 1 1 1
N 0 1 2 2 2 2
O 0 . . . . .
N 0 . . . . .

Again, this makes sense. The LCS of "CAN" and "A" is just "A," the LCS of "CAN" and "AN" is "AN", etc.

We can repeat this through the rest of the table to find this resulting table:

    A N N I E
  0 0 0 0 0 0
C 0 0 0 0 0 0
A 0 1 1 1 1 1
N 0 1 2 2 2 2
O 0 1 2 2 2 2
N 0 1 2 3 3 3

And we have that the LCS has length 3, which is correct.

Hope this helps!

Answer 2

The value of C[i][j] only depends on C[i][j-1], C[i-1][j] and C[i-1][j-1]. Thus, when we get the value of C[i][j] in the inner loop, we could continue to calculate C[i][j+1] because C[i][j] and C[i-1][j+1] and C[i-1][j] are all already been calculated.